B.

解

把所有正數變為1，負數變為-1。然后如果-1有偶數個，那么把所有的0變為1；如果-1有奇數個，如果數列中存在0，把其中一個0變為-1，其余全變為1，否則把其中一個負數變為1。

Code

#include<bits/stdc++.h> using namespace std; int main(){int n,mo=0,cnt0=0;long long ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){long long x;scanf("%lld",&x);if(x>0)ans+=x-1;else if(x<0)ans+=-x-1,mo^=1;else ans++,cnt0++;}if(mo){if(!cnt0)ans+=2;}printf("%lld\n",ans);return 0; }

C.

解

瞎湊。

Code

#include<bits/stdc++.h> using namespace std; const int maxn=100003; int n; int main(){scanf("%d",&n);if(!(n%2)){printf("NO");return 0;}printf("YES\n1 ");for(int i=2,u=n*2,d=3;i<=n;i+=2,u-=2,d+=2){printf("%d %d ",u,d);}printf("2 ");for(int i=2,u=n*2-1,d=4;i<=n;i+=2,u-=2,d+=2){printf("%d %d ",u,d);}return 0; }

D.

解

前置知識：floyd求最小環
我們發現，如果存在一個bit，使得數列中至少3個數在這個bit上為1，那么答案就是3。
否則把沒有邊的節點去掉，這張圖就最多只有120個節點。
因此使用floyd求最小環。

Code

#include<bits/stdc++.h> using namespace std; const int maxn=100003,maxm=303; int N,n,g[maxm][maxm],h[maxm][maxm],mp[maxm],cntmp; long long A[maxn]; int main(){scanf("%d",&N);for(int i=1;i<=N;i++)scanf("%lld",A+i);for(int i=0;i<=60;i++){int p[4],cnt=0;for(int j=1;j<=N;j++){if((A[j]>>i)&1){p[++cnt]=j;if(cnt==3){printf("3");return 0;}}}if(cnt==2){mp[++cntmp]=p[1],mp[++cntmp]=p[2];}}sort(mp+1,mp+cntmp+1);cntmp=unique(mp+1,mp+cntmp+1)-mp-1;for(int i=1;i<=cntmp;i++){for(int j=1;j<=cntmp;j++){if(i!=j){if(A[mp[i]]&A[mp[j]])g[i][j]=1;else g[i][j]=maxn;}h[i][j]=g[i][j];}}int ans=maxn;for(int k=1;k<=cntmp;k++){for(int i=1;i<k;i++){for(int j=1;j<k;j++){if(i!=j&&j!=k&&i!=k)ans=min(ans,h[i][j]+g[i][k]+g[k][j]);}}for(int i=1;i<=cntmp;i++){for(int j=1;j<=cntmp;j++){h[i][j]=min(h[i][j],h[i][k]+h[k][j]);}}}printf("%d",ans==maxn?-1:ans);return 0; }

E.

解

首先對表格黑白染色，左上角的格子是黑色。
那么我們可以用 \(n^2\) 不到一點 次詢問得到所有黑色節點的值，以及白色節點相對于節點 \((1,2)\) 的值。
然后我們對于 \((1,2)\) 的值是0或1分別 \(O(n^4)\) dp出所有的詢問值，由于必定有解，所以必然存在一對節點使得在 \((1,2)\) 的值不同時它們的詢問值不同。找出這對節點，再詢問一次即可。

Code

#include<bits/stdc++.h> using namespace std; const int maxn=53; int a[maxn][maxn],n,dp[2][maxn][maxn][maxn][maxn]; struct T{int x,y,step;T(){}T(int _x,int _y,int _s):x(_x),y(_y),step(_s){} }; struct QQ{int sx,sy,x,y;QQ(){}QQ(int _sx,int _sy,int _x,int _y):sx(_sx),sy(_sy),x(_x),y(_y){} }; vector<QQ> v[maxn*2]; int query(int x1,int y1,int x2,int y2){printf("? %d %d %d %d\n",x1,y1,x2,y2);fflush(stdout);int ret;scanf("%d",&ret);if(ret==-1)exit(0);return ret; } int main(){scanf("%d",&n);a[1][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if((i==1&&j<=2)||(i==2&&j==1)||(i==n&&j==n))continue;int ii,jj;if(i==1)ii=i,jj=j-2;else if(i>2&&j==1)ii=i-2,jj=j;else ii=i-1,jj=j-1;a[i][j]=a[ii][jj]^query(ii,jj,i,j)^1;if(i==2&&j==3)a[2][1]=a[2][3]^query(2,1,2,3)^1;}}for(int sx=1;sx<=n;sx++){for(int sy=1;sy<=n;sy++){for(int x=sx;x<=n;x++){for(int y=sy;y<=n;y++){v[abs(sx-x)+abs(sy-y)].push_back(QQ(sx,sy,x,y));}}}}for(int b=0;b<=1;b++){for(int i=0;i<=n*2-2;i++){for(int j=0;j<int(v[i].size());j++){int sx=v[i][j].sx,sy=v[i][j].sy,x=v[i][j].x,y=v[i][j].y;if(sx==x&&sy==y)dp[b][sx][sy][x][y]=1;else if(x-sx+y-sy==1)dp[b][sx][sy][x][y]=(a[sx][sy]==a[x][y]);else{if(a[sx][sy]==a[x][y]){if(sx+2<=x)dp[b][sx][sy][x][y]|=dp[b][sx+1][sy][x-1][y];if(sx+1<=x&&sy+1<=y){dp[b][sx][sy][x][y]|=dp[b][sx+1][sy][x][y-1];dp[b][sx][sy][x][y]|=dp[b][sx][sy+1][x-1][y];}if(sy+2<=y)dp[b][sx][sy][x][y]|=dp[b][sx][sy+1][x][y-1];}}}}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if((i+j)&1)a[i][j]^=1;}int flag=-1;for(int sx=1;sx<=n;sx++){for(int sy=1;sy<=n;sy++){for(int x=sx;x<=n;x++){for(int y=sy;y<=n;y++){if(abs(sx-x)+abs(sy-y)>=2&&dp[0][sx][sy][x][y]!=dp[1][sx][sy][x][y]){flag=(query(sx,sy,x,y)==dp[1][sx][sy][x][y]);break;}}if(~flag)break;}if(~flag)break;}if(~flag)break;}puts("!");for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if((i+j)&1)a[i][j]^=flag;printf("%d",a[i][j]);}puts("");}return 0; }

轉載于:https://www.cnblogs.com/BlogOfchc1234567890/p/11440438.html

總結

以上是生活随笔為你收集整理的Codeforces 1206的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。