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;
}