題目鏈接：點(diǎn)擊查看

題目大意：給出一個整數(shù)集合B，現(xiàn)在可以根據(jù)集合B構(gòu)造一個無向圖，規(guī)定所有的整數(shù)(無窮無盡)為頂點(diǎn)，若兩個整數(shù)i和j滿足abs(i - j)在集合B中，則 i 和 j 之間可以連一條邊，現(xiàn)在問最少從集合B中刪掉多少個元素，滿足構(gòu)成的圖為一個二分圖

題目分析：二分圖的定義是不存在奇環(huán)，那么在這個題目中什么時候會出現(xiàn)奇環(huán)呢？因?yàn)轫旤c(diǎn)的范圍是全部整數(shù)，最好想法的就是將奇數(shù)和偶數(shù)分開來，這樣就是一張完美的二分圖了，既然從奇偶出發(fā)，因?yàn)槭菭砍兜絘bs(i - j)與集合B的關(guān)系，所以我們首先需要知道：

奇數(shù)+奇數(shù)=偶數(shù)

奇數(shù)+偶數(shù)=奇數(shù)

偶數(shù)+偶數(shù)=偶數(shù)

如果我們想要將其分為奇偶兩部分的話，顯然必須令集合B中只剩下奇數(shù)才行，因?yàn)槠鏀?shù)和偶數(shù)作差只會出現(xiàn)奇數(shù)，因此剛好可以連邊，而后考慮一下奇數(shù)和偶數(shù)都存在的情況，可以證明一定會存在奇環(huán)：

• 假設(shè)奇數(shù)為x，偶數(shù)為y，則點(diǎn)0到點(diǎn)x*y一定有奇環(huán)：因?yàn)辄c(diǎn)0可以和點(diǎn)x建邊，因?yàn)閍bs(x-0)=x，點(diǎn)x可以和點(diǎn)2*x建邊，因?yàn)閍bs(2*x-x)=x，以此類推，點(diǎn)0到點(diǎn)x*y之間可以通過x傳遞建立y條邊，點(diǎn)0到點(diǎn)x*y之間可以通過點(diǎn)y傳遞建立x條邊，也就是由點(diǎn)0->點(diǎn)x*y->點(diǎn)0這個環(huán)中共有x+y條邊，通過上面的前提我們可以得證，x+y是奇數(shù)，故一定存在奇環(huán)，證畢

若集合中有奇數(shù)有偶數(shù)是肯定不符合題意的，那么全部都是偶數(shù)的情況呢？因?yàn)槿绻现械臄?shù)全是偶數(shù)，我們可以發(fā)現(xiàn)，所有的奇數(shù)和奇數(shù)連成了一個小集合，而所有的偶數(shù)和偶數(shù)也都連成了一個小集合，也就是說奇數(shù)和偶數(shù)互不干涉，所以我們需要想辦法將其集合中的數(shù)轉(zhuǎn)換為奇數(shù)的情況就能豁然開朗了，這里可以讓集合B中所有的偶數(shù)同時除以2，直到出現(xiàn)至少一個奇數(shù)為止，這個操作該如何解釋呢？因?yàn)楝F(xiàn)在已經(jīng)是奇數(shù)點(diǎn)在一個集合中，偶數(shù)點(diǎn)在一個集合中了，我們可以對其重新編號，也就是讓奇數(shù)所在的集合中等量出現(xiàn)奇數(shù)和偶數(shù)，偶數(shù)亦然，此時就相當(dāng)于將整個集合的編號除以2了，同樣集合B中的元素也需要對應(yīng)除以2，根據(jù)題意保留的元素大概是這樣的：

保留全部奇數(shù)

刪除掉①中所有的奇數(shù)后，全部偶數(shù)除以2后，保留全部奇數(shù)

刪除掉②中所有的奇數(shù)后，全部偶數(shù)除以2后，保留全部奇數(shù)

如此往復(fù)

到此為止，我們發(fā)現(xiàn)可以將所有的數(shù)按照二的冪次分成不同的集合中去，也就是說在題目給出的集合B中，我們可以選擇任意一個二的冪次的集合進(jìn)行保留，那么因?yàn)轭}目要求我們刪除掉最少的元素，所以我們選擇最大的那個集合保留即可

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;LL a[N];int num[N],cnt[100];int get_num(LL x) {int ans=0;while(x%2==0){x>>=1;ans++;}return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",a+i);num[i]=get_num(a[i]);cnt[num[i]]++;}int mmax=*max_element(cnt,cnt+100);printf("%d\n",n-mmax);for(int i=0;i<100;i++)if(mmax==cnt[i]){for(int j=1;j<=n;j++)if(num[j]!=i)printf("%lld ",a[j]);break;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1220D Alex and Julian(思维+数论)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。