题目链接
http://codeforces.com/contest/1205/problem/C
题解
菜鸡永远做着变巨的梦
然而依然连div1BC题都不会做
要是那天去打cf怕是又要1题滚粗了。。。。
首先第一步显然是对于所有(i+j)为偶数的点(下称“偶点”)求出(a_{i,j})的值，对于所有(i+j)为奇数的点(下称“奇点”)求出它们之间的相对关系。也就相当于强行令(a_{1,2}=x)之后求出所有奇点是(x)还是(x ext{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 ext{xor} c_4=c_2 ext{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
",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(":
");
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;
}