OR

題意：

給你一個(gè)數(shù)組b和c(數(shù)值位于下標(biāo)2到n)
問是否存在一個(gè)a序列，$bi=a_{i?1}or{a}_i$ , $c_i=a_{i?1}+a_i$

題解：

我是這樣想的，對于每一個(gè)bi和ci(i從2開始)，都可以確定ai的取值情況，然后我們再計(jì)算bi+1和ci+1時(shí)，可以根據(jù)上一輪ai得到的情況來確定本輪ai+1的情況。
如何通過bi和ci確定ai的取值呢？
我們利用二進(jìn)制來判斷，對于bi和ci的每一位分析，從第0位到第31位依次分析，

考慮第j位時(shí),f表示當(dāng)前是否有進(jìn)位

如果b=0,c=0,f=0,那么ai,ai-1的第j位為0

如果b=1,c=1,f=1,那么ai,ai-1為1

如果b=1,c=1,f=1,那么ai和ai-1一個(gè)為0，一個(gè)為1

如果b=1,c=0,f=1,那么ai和ai-1一個(gè)為0

如果b=1,c=0,f=0，那么ai,ai-1為1，且會產(chǎn)生進(jìn)位f=1

如果b=0,c=1,f=1,那么ai,ai-1為0，進(jìn)位在此處用掉，進(jìn)位消失，f=0

不滿足上列情況，a無法取到值

F[i]表示第i個(gè)位置的情況
F[i]=2表示第i個(gè)位置有兩個(gè)值可以取，如果ai取1，則ai-1取0，反之（初始化為-1）
F[i]=1/0:分別表示當(dāng)前位置取1或0
F[i]=-1:說明當(dāng)前位置無法取到值
F[i]會不斷更新，F[i]的作用相當(dāng)于將Ai的取值情況與Ai-1相連(Ai-1的情況就是通過F[i]來表示)，完事后并更新F[i],給后面Ai+1接著使用
w表示當(dāng)前第j位的取值情況

如果w=-1，則F[i]=-1

如果w=0/1&&F[j]==2,則F[j]=w

如果w=2&&F[j]!=2,則F[j]=F[j] ^ 1(ai-1這一個(gè)位置取w(0或1)，而ai與ai-1是兩種取值，ai的取值是w ^ 1)

如果w=0&&F[j]=1，則F[j]=-1;

如果w=1&&F[j]=0，則F[j]=-1;

然后更新答案
詳細(xì)看代碼

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); using namespace std; typedef long long ll; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime = clock(); //計(jì)時(shí)開始freopen("in.txt","r",stdin);#endif } void Time_test(){#ifdef ONLINE_JUDGE#elseendTime = clock(); //計(jì)時(shí)結(jié)束printf("\n運(yùn)行時(shí)間為:%lfs\n",(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif } const int maxn=2e5+9; ll b[maxn],c[maxn],F[maxn]; int main() {//rd_test();int n;cin>>n;ll sum=1e11;for(int i=2;i<=n;i++){cin>>b[i];}for(int i=2;i<=n;i++){cin>>c[i];}for(int i=0;i<=33;i++)F[i]=2; for(int i=2;i<=n;i++){ll tot=1;ll w=0;int f=0;for(int j=0;j<=31;j++){int x=((b[i]>>j)&1);int y=((c[i]>>j)&1);if(x==0&&y==0&&f==0)w=0;else if(x==1&&y==1){if(f==1){w=1;}else w=2;}else if(x==1&&y==0){if(f==1){w=2;f=1;}else{w=1;f=1;} }else if(x==0&&y==1&&f==1){f=0;w=0;}else {w=-1;}if(w==-1)F[j]=-1;else if(F[j]==2&&w!=2) F[j]=w;else if(w==2&&F[j]!=2)F[j]=F[j]^1;else if(F[j]==1&&w==0)F[j]=-1;else if(F[j]==0&&w==1) F[j]=-1;if(F[j]==1)tot=1ll*tot*1;else if(F[j]==0)tot=1ll*tot*1;else if(F[j]==2)tot=1ll*tot*2;else if(F[j]==-1)tot=1ll*tot*0;}if(f==1)tot=0;sum=min(sum,tot);}cout<<sum;//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的OR(牛客第八场)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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