题目大意
交互库有一个 \(3\times 3\) 的 01 矩阵 \(a\)，每次询问一个 \(n\times n\) 的 01 矩阵 \(b\)，交互库会返回一个 \((n-2)\times (n-2)\) 的 01 矩阵 \(c\)，满足：
\[c_{x,y} = \bigoplus\limits_{1 \le i,j \le 3} \left ( a_{i,j} \operatorname{AND} b_{x+i-1,y+j-1} \right ) \]如果一次询问后 \(c\) 矩阵内所有元素全都是 \(1\)，你就获胜了。否则，交互库会告诉你 \(c\) 矩阵。保证 \(n\) 是奇数。
题解
因为平均下来一组数据只有 \(3\) 次询问，所以我们不能太依赖于交互库，考虑直接把 \(a\) 求出，然后构造矩阵 \(b\)。
如何得到矩阵 \(a\)？可以在 \(b\) 的某个位置填 \(1\)，这样就可以得到 \(a\) 哪些位置为 \(1\)。
具体地，对于 \(n\ge 5\)，我们可以构造一个矩阵 \(b\) 满足 \(b_{3,3}=1\)，其余位置为 \(0\)。那么得到的矩阵 \(c\) 就有 \(c_{i,j}=a_{3-i+1,3-j+1}=a_{4-i,4-j}\)，这样就通过一次询问求出了 \(a\)。
然后需要根据 \(a\) 来构造 \(b\)。我们找到最大的 \(x,y\) 使得 \(a_{x,y}=1\)（满足 \(a_{x,y}\) 的右下部分没有 \(1\) 即可）。然后从左上到右下枚举 \(b_{i,j}\)，对于一个位置 \(b_{i,j}\)，若生成的 \(c_{i,j}=0\)，就将 \(b_{i+x-1,j+y-1}\) 取反，就能使 \(c_{i,j}=1\)，且不会影响 \(c_{i,j}\) 左上角的数。
因为不同的 \(b_{i,j}\) 对应的 \(b_{i+x-1,j+y-1}\) 肯定是不同的，所以这样子依次改下去，就能使整个 \(b\) 符合条件。
对于 \(n<5\)，即 \(n=3\) 时，返回值只有 \(1\) 个数，不能得到很好的信息。所以可以考虑直接随机，因为只有 \(0\) 和 \(1\) 两种可能，所以随机的正确率为 \(\frac 1 2\)。
对于 \(n \ge 5\) 的情况，共需要 \(2\) 次询问。而 \(n=3\) 时，期望用 \(2\) 次询问，所以 \(999\) 次询问时绰绰有余的。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <random>
#define ll long long
using namespace std;
const int N = 40;
int a[4][4],b[N][N],c[N][N],n;
mt19937 rnd(114514);
bool pri()
{
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)cout << b[i][j];
cout << endl;
}
string s;cin >> s;
return s[0]=='C';
}
int get(int i,int j)
{
bool sum = 0;
for(int x = 1;x <= 3;x++)for(int y = 1;y <= 3;y++)
sum ^= a[x][y]&b[i+x-1][j+y-1];
return sum;
}
inline int rd()
{
char c;int f = 1;
while(!isdigit(c = getchar()))if(c=='-')f = -1;
int x = c-'0';
while(isdigit(c = getchar()))x = x*10+(c^48);
return x*f;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int t = 333;
while(t--)
{
memset(a,0,sizeof a);memset(b,0,sizeof b);
n = rd();
if(n == 3)
{
while(1)
{
for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)
b[i][j] = rnd()&1;
if(pri())break;else rd();
}
continue;
}
b[3][3] = 1;
if(pri())continue ;
for(int i = 1;i <= n-2;i++)
{
string s;cin >> s;
if(i <= 3)
for(int j = 1;j <= 3;j++)
a[4-i][4-j] = s[j-1]-'0';
}
int x = 0,y = 0;
for(int i = 1;i <= 3;i++)for(int j = 1;j <= 3;j++)
if(a[i][j])x = i,y = j;
for(int i = 1;i <= n-2;i++)for(int j = 1;j <= n-2;j++)
if(!get(i,j))b[i+x-1][j+y-1] ^= 1;
pri();
}
return 0;
}