题目链接

http://codeforces.com/contest/1205/problem/C

题解

菜鸡永远做着变巨的梦
然而依然连div1BC题都不会做
要是那天去打cf怕是又要1题滚粗了。。。。

首先第一步显然是对于所有\(i+j\)为偶数的点(下称“偶点”)求出\(a_{i,j}\)的值，对于所有\(i+j\)为奇数的点(下称“奇点”)求出它们之间的相对关系。也就相当于强行令\(a_{1,2}=x\)之后求出所有奇点是\(x\)还是\(x\ \text{xor}\ 1\).
然后我们就是要确定\(x\)的值。

后面题解给了两种做法，在上面的基础上分别只多询问\(1\)次：

做法一

比较暴力的做法。
暴力枚举\(x=0\)和\(x=1\)的情况，因为有解所以这两种情况肯定存在一组询问\((x_1,y_1,x_2,y_2)\)满足此询问在两种情况下答案不同。
于是我们可以暴力DP求出所有询问的答案，然后找到不同的位置询问一次来确定。
(果然是大力出奇迹啊)

做法二

这是我的最初想法，但是最终还是失败了。
对于任何联通的四个格\(c_1,c_2,c_3,c_4\) (注意只需联通即可，不一定非要在一条直线上)，如果\(c_1\ \text{xor}\ c_4=c_2\ \text{xor}\ c_3\)，那么询问\(c_1\)和\(c_4\)两点可以确定答案。因为如果\(c_1=c_4\)则\(c_2=c_3\)一定存在，否则一定不存在。
注意到题目里的限制\(a_{1,1}=1,a_{n,n}=0\), 可以证明一定存在连续的\(4\)个格使得这四个格上数异或和为\(0\). 证明: 假设不存在，那么考察一条\((1,1)\)到\((n,n)\)的NE Lattice Path, 其长度模\(4\)一定余\(1\), 且上面的数\(4\)个一循环，故有最后一个和第一个相等，矛盾。
于是随便找出一条\((1,1)\)到\((n,n)\)的异或和为\(0\)的四格连续路径，询问一下，做完了。

由于我太智障，思路一直局限在一条直线上的四个格，于是欢乐滚大粗……

代码

做法二

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
using namespace std;

void read(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

const int N = 50;
int a[N+3][N+3];
vector<int> pth;
int n,ans;

int query(int lx,int ly,int rx,int ry)
{
    printf("? %d %d %d %d\n",lx,ly,rx,ry); fflush(stdout);
    int ret; scanf("%d",&ret); return ret;
}

int main()
{
    scanf("%d",&n);
    a[1][1] = 1; a[n][n] = 0;
    for(int i=1; i<=n; i++)
    {
        if(i&1)
        {
            if(i!=1) {a[i][1] = a[i-2][1] ^ query(i-2,1,i,1)^1;}
            for(int j=3; j<=n; j+=2)
            {
                if(i==n&&j==n) continue;
                a[i][j] = a[i][j-2] ^ query(i,j-2,i,j)^1;
            }
        }
        else
        {
            for(int j=2; j<=n; j+=2)
            {
                a[i][j] = a[i-1][j-1] ^ query(i-1,j-1,i,j)^1;
            }
        }
    }
    a[1][2] = 0;
    for(int i=4; i<=n; i+=2) {a[1][i] = a[1][i-2] ^ query(1,i-2,1,i)^1;}
    for(int i=3; i<=n; i+=2) {a[2][i] = a[1][i-1] ^ query(1,i-1,2,i)^1;}
    a[2][1] = a[2][3] ^ query(2,1,2,3)^1;
    for(int i=3; i<=n; i++)
    {
        if(i&1)
        {
            for(int j=2; j<=n; j+=2) {a[i][j] = a[i-2][j] ^ query(i-2,j,i,j)^1;}
        }
        else
        {
            for(int j=1; j<=n; j+=2) {a[i][j] = a[i-2][j] ^ query(i-2,j,i,j)^1;}
        }
    }
/*  printf(":\n");
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) printf("%d",a[i][j]);
        puts("");
    }
*/  for(int i=1; i<=n; i++) {pth.push_back(a[i][1]);}
    for(int i=2; i<=n; i++) {pth.push_back(a[n][i]);}
    int lx,rx,ly,ry;
    for(int i=3; i<=n+n-2; i++)
    {
        if((pth[i]^pth[i-1]^pth[i-2]^pth[i-3])==0)
        {
            lx = i-3<n ? i-3+1 : n;
            ly = i-3<n ? 1 : i-3-n+2;
            rx = i<n ? i+1 : n;
            ry = i<n ? 1 : i-n+2;
            break;
        }
    }
    if(query(lx,ly,rx,ry))
    {
        ans = a[rx][ry]^a[lx][ly];
    }
    else
    {
        ans = a[rx][ry]^1^a[lx][ly];
    }
    puts("!");
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) printf("%d",((i+j)&1)?(a[i][j]^ans):a[i][j]);
        puts("");
    }
    fflush(stdout);
    return 0;
}