考试（Exams）（2021 CoE III 附加）
Terraria
2021-05-27 18:58:13
## 题目简述
设有 $n$ 道题目，$q$ 个询问，且
- 第 $i$ 次询问为 $x_{i, j} (1 \leq i \leq q, 1 \leq j \leq n, x_{i, j} \in \{0, 1\})$；
- 第 $j$ 题的答案为 $c_j (1 \leq j \leq n, c_j \in \{0, 1\})$。
则需要从 $\sum \limits_{j=1}^{n} x_{i,j} \oplus c_j$ 中恢复 $c_j$ 的值。
---
## 问题的转换
首先，可以从 $\sum \limits_{i=1}^{n} x_{i,j} \oplus c_j$ 中得到 $\sum \limits_{i=1}^{n} x_{i,j} \times c_j$ 的值。
枚举 $x_{i, j}$ 和 $c_{j}$ 的值：
| $x_{i, j}$ | $c_j$ | $x_{i, j} \oplus c_j$ | $x_{i, j} \times c_j$ |
| :-: | :-: | :-: | :-: |
| $0$ | $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ | $0$ |
| $1$ | $0$ | $1$ | $0$ |
| $1$ | $1$ | $0$ | $1$ |
可以得到 $x_{i, j} \oplus c_j = x_{i, j} + c_j - 2 \times x_{i, j} \times c_j$，
从而 $x_{i, j} \times c_j = \dfrac{x_{i, j} + c_j - (x_{i, j} \oplus c_j)}{2}$。
从而 $\sum \limits_{i=1}^{n} x_{i, j} \times c_j = \dfrac{1}{2} \left ( \sum \limits_{i=1}^{n} x_j + \sum \limits_{i=1}^{n} c_j - \sum \limits_{i=1}^{n} x_{i, j} \oplus c_j \right )$。
其中 $\sum \limits_{i=1}^{n} c_j$ 的值可以令 $x_{0, j} = 0$，用一个额外的询问得到。
接下来问题就是从 $\sum \limits_{i=1}^{n} x_{i,j} \times c_j$ 中恢复 $c_j$ 的值。
这可以通过高斯消元解决。
询问次数：$q \approx n$。
当然对于这一部分分可以采取无脑暴力，即每次改一道题目的答案，判断返回的正确题目数量与原有的正确题目数量的大小。这里不过多赘述。
期望得分：$20$ 分。
---
## 解法 $0$
当 $q = 3, n = 4$ 时，以下的 $x_{i, j}$ 可以区分出 $2^4$ 种不同的 $c_j$。
```
1110
1011
1101
```
即可以用 $3$ 次询问获取 $4$ 道题目的答案。
询问次数：$q \approx 0.75n$。
期望得分：$60$ 分。
- $q \approx0.75n$ 解法的代码：
```cpp
#include<bits/stdc++.h>
#define check(cnt) if(cnt==n) {print();return 0;}
using namespace std;
char a[10009];
char b[10009];
int cnt1,cnt2;
int n,lim,k,t;
int now=1;
void print(){
for(int i=1;i<=n;i++) cout<<b[i];
cout<<'\n';
cout.flush();
}
void prin(){
for(int i=1;i<=n;i++) cout<<a[i];
cout<<'\n';
cout.flush();
}
int ft(){
int cnt=0;
for(int i=1;i<=now-1;i++){
if(b[i]=='Y') cnt++;
}
return cnt;
}
void doit(){
for(int i=1;i<=n;i++) a[i]='Y';
}
int main(){
cin>>n>>lim;
for(int i=1;i<=n;i++) b[i]=a[i]='Y';
prin();
cin>>t;
//check(t);
while(now<=n){
doit();
a[now]=a[now+1]='N';
prin();
cin>>cnt1;
//check(cnt1);
if(cnt1==t-2||cnt1==t+2){
if(cnt1==t-2) b[now]=b[now+1]='Y';
else b[now]=b[now+1]='N';
now+=2;
if(now==n+1) break;
if(now>n){
now-=2;
break;
}
continue;
}
a[now]='Y',a[now+1]=a[now+2]=a[now+3]='N';
prin();
cin>>cnt1;
//check(cnt1);
a[now]=a[now+2]='N',a[now+1]=a[now+3]='Y';
prin();
cin>>cnt2;
//check(cnt2);
if(cnt1==t-3){
b[now]='N',b[now+1]=b[now+2]=b[now+3]='Y';
}
else if(cnt1==t-1){
if(cnt2==t-2) b[now]=b[now+2]=b[now+3]='Y',b[now+1]='N';
if(cnt2==t) b[now]=b[now+3]='N',b[now+1]=b[now+2]='Y';
if(cnt2==t+2) b[now]=b[now+2]='N',b[now+1]=b[now+3]='Y';
}
else if(cnt1==t+1){
if(cnt2==t-2) b[now]=b[now+2]='Y',b[now+1]=b[now+3]='N';
if(cnt2==t) b[now]=b[now+3]='Y',b[now+1]=b[now+2]='N';
if(cnt2==t+2) b[now]=b[now+2]=b[now+3]='N',b[now+1]='Y';
}
else if(cnt1==t+3){
b[now]='Y',b[now+1]=b[now+2]=b[now+3]='N';
}
now+=4;
if(now==n+1) break;
if(now>n){
now-=4;
break;
}
}
int rest=n-now+1,k=ft();
if(rest==1){
if(k==t) b[n]='N';
else b[n]='Y';
}
else if(rest==2){
if(k==t){
b[n-1]=b[n]='N';
}
else if(k==t-2){
b[n-1]=b[n]='Y';
}
else{
b[n-1]='Y',b[n]='N';
print();
cin>>cnt1;
check(cnt1);
b[n-1]='N',b[n]='Y';
print();
cin>>cnt1;
check(cnt1);
return 0;
}
}
else if(rest==3){
if(k==t){
b[n-2]=b[n-1]=b[n]='N';
}
else if(k==t-3){
b[n-2]=b[n-1]=b[n]='Y';
}
else if(k==t-1){
b[n-2]=b[n-1]=b[n]='N';
b[n-2]='Y',print();
cin>>cnt1;
check(cnt1);
b[n-2]=b[n-1]=b[n]='N';
b[n-1]='Y',print();
cin>>cnt1;
check(cnt1);
b[n-2]=b[n-1]=b[n]='N';
b[n]='Y',print();
cin>>cnt1;
check(cnt1);
}
else if(k==t-2){
b[n-2]=b[n-1]=b[n]='Y';
b[n-2]='N',print();
cin>>cnt1;
check(cnt1);
b[n-2]=b[n-1]=b[n]='Y';
b[n-1]='N',print();
cin>>cnt1;
check(cnt1);
b[n-2]=b[n-1]=b[n]='Y';
b[n]='N',print();
cin>>cnt1;
check(cnt1);
}
}
print();
return 0;
}
```
【附】这个代码的思路：
记 $t$ 为所有题目中答案为 `Y` 的个数，即先用一次提交得到 $t$，然后每次进行 $3$ 次提交得到 $4$ 道题的答案。
令 $k$ 表示目前在第 $k$ 道题。
1. 把第 $k,k+1$ 道题改为 `N`，如果得到的正确答案数量为 $cnt=t+2$ 或 $cnt=t-2$ 即可确定这两道题的答案。
2. 如果返回的是第 $cnt=t$，则：
> 把 $k,k+1,k+2,k+3$ 道题依次改为 `YNNN`，返回 $m_1$。
> 把 $k,k+1,k+2,k+3$ 道题一次改为 `NYNY`，返回 $m_2$。
可以根据 $m_1$ 和 $m_2$ 得到这四道题的答案。
至于如何得到答案，具体可以参见上面代码，这里不过多赘述。
---
当 $q = 7, n = 10$ 时，以下的 $x_{i, j}$ 可以区分出 $2^{10}$ 种不同的 $c_j$。
```
1011111100
0010100010
1110000101
1101100011
1100101100
1111100101
0101001101
```
即可以用 $7$ 次询问获取 $10$ 道题目的答案。
询问次数：$q \approx 0.7n$。
期望得分：$70$ 分。
- $q \approx0.7n$ 解法的代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int magic[7] = {
0b1011111100,
0b0010100010,
0b1110000101,
0b1101100011,
0b1100101100,
0b1111100101,
0b0101001101,
};
map < vector <int>, int > mp;
void init() {
for (int i = 0; i < (1 << 10); i++) {
vector <int> t;
for (int j = 0; j < 7; j++)
t.push_back(__builtin_popcount(i & magic[j]));
mp[t] = i;
}
}
int n;
int query(vector <int> A) {
string S;
for (int i = 0; i < n; i++)
S += 'Y';
for (int i = 0; i < (int)A.size(); i++)
if (A[i] < n) S[A[i]] = 'N';
printf("%s\n", S.c_str());
fflush(stdout);
int res;
scanf("%d", &res);
if (res == n) exit(0);
return res;
}
int K;
vector <int> ans;
int main() {
init();
cin >> n >> K;
int lst = query({});
for (int i = 0; i < n; i += 10) {
vector <int> t;
for (int j = 0; j < 7; j++) {
vector <int> tmp;
for (int k = 0; k < 10; k++)
if (magic[j] >> k & 1)
if (i + k < n)
tmp.push_back(i + k);
t.push_back((query(tmp) - lst + (int)tmp.size()) / 2);
}
int f = mp[t];
for (int k = 0; k < 10; k++)
if (f >> k & 1) ans.push_back(i + k);
}
query(ans);
return 0;
}
```
---
## 解法 $1$
题目要求 $x_{i, j} \in \{0, 1\}$，先考虑弱化版的问题，即只要求 $x_{i, j} \in \{-1, 0, 1\}$。
首先，当 $q = 1$ 时，$n = 1, x_{1, 1} = 1$ 满足条件。
接下来，我们用 $q \times n$ 的询问矩阵 $X = x_{i, j}$ 构造 $2q \times (2n + q)$ 的询问矩阵 $X' = x'_{i, j}$：
$$X \to X' = \begin{pmatrix}X & -X & I \\ X & X & 0\end{pmatrix}$$
时间复杂度：$1 \times 1 \to 2 \times 3 \to 4 \times 8 \to 8 \times 20 \to \cdots$，即 $q \approx O(\dfrac{n}{\log n})$。
**证明**
可以证明这个矩阵满足条件。
设 $cnt_i = \sum \limits_{i=1}^{2n+q} x'_{i,j} \times c_j (1 \leq i \leq 2q)$，则
$$cnt_i = \sum \limits_{i=1}^{n}x_{i, j}c_j - \sum \limits_{i=1}^{n}x_{i, j}c_{n + j} + c_{2n + i} (1 \leq i \leq q)$$
$$cnt_{i + q} = \sum \limits_{i=1}^{n}x_{i, j}c_j + \sum \limits_{i=1}^{n}x_{i, j}c_{n + j} (1 \leq i \leq q)$$
那么根据奇偶性，$c_{2n + i} = (cnt_i + cnt_{i + q}) \bmod 2 (1 \leq i \leq q)$。
接下来可以解方程组得出 $\sum \limits_{i=1}^{n}x_{i, j}c_j(1 \leq j \leq n)$ 和 $\sum \limits_{i=1}^{n}x_{i, j}c_{n + j}(1 \leq j \leq n)$ 的值。
于是得到两个 $q \times n$ 的子问题，可以递归解决。
**原问题**
因为 $-1, 0, 1$ 都可以表示为 $0, 1$ 的差（$-1 = 0 - 1, 0 = 0 - 0, 1 = 1 - 0$），所以每个 $x_{i, j} \in \{-1, 0, 1\}$ 的询问都可以表示为两个 $x_{i, j} \in \{0, 1\}$ 的询问的差。
期望得分：$80$ 分。
但是这样仍然不够优秀，我们可以——
## 解法 $2$
为做出区分，令 $x_{i, j}$ 和 $y_{i, j}$ 分别为解法 $1$ 和解法 $2$ 的询问矩阵。
现在要求 $y_{i, j} \in \{0, 1\}$。
首先，当 $q = 2$ 时，$n = 1, y_{1, 1} = 1, y_{2, 1} = 0$ 满足条件。
接下来，我们用 $q \times n$ 的询问矩阵 $Y = y_{i, j}$ 和解法 $1$ 中 $q \times n'$ 的询问矩阵 $X = x_{i, j}$ 构造 $2q \times (n + n')$ 的询问矩阵 $Y' = y'_{i, j}$：
$$X, Y \to Y' = \begin{pmatrix}Y & X_1 \\ Y & X_2 \end{pmatrix}$$
其中将 $X$ 表示为两个询问的差 $X = X_1 - X_2$。
**证明**
可以证明这个矩阵满足条件。
设 $cnt_i = \sum \limits_{i=1}^{n+n'} y'_{i,j} \times c_j (1 \leq i \leq 2q)$，则
$$cnt_i = \sum \limits_{i=1}^{n}y_{i, j}c_j + \sum \limits_{i=1}^{n'}x_{1, i, j}c_{n + j} (1 \leq i \leq q)$$
$$cnt_{i + q} = \sum \limits_{i=1}^{n}y_{i, j}c_j + \sum \limits_{i=1}^{n'}x_{2, i, j}c_{n + j} (1 \leq i \leq q)$$
$$x_{i, j} = x_{1, i, j} - x_{2, i, j}$$
解方程组得 $\sum \limits_{i=1}^{n'}x_{i, j}c_{n + j} = cnt_i - cnt_{i + q}$，这是一个 $q \times n'$ 的子问题，可以递归解决；
再解方程组得出 $\sum \limits_{i=1}^{n}y_{i, j}c_j$ 的值，这是一个 $q \times n$ 的子问题，也可以递归解决。
时间复杂度：$2 \times 1 \to 4 \times 4 \to 8 \times 12 \to \cdots$，即 $q \approx O(\dfrac{n}{\log n})$，但是常数减少了约一半。
期望得分：$100$ 分。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0, _n = n; i < _n; i++)
#define pb push_back
typedef vector <int> vi;
typedef vector <vi> vii;
vii A[15];
void gA(int m) {
if (m == 0) {
A[0] = {{1}};
return ;
}
vii &L = A[m - 1], &R = A[m];
forn(i, L.size()) {
vi t;
forn(j, L[i].size()) t.pb(L[i][j]);
forn(j, L[i].size()) t.pb(-L[i][j]);
forn(j, L.size()) t.pb(i == j);
R.pb(t);
}
forn(i, L.size()) {
vi t;
forn(j, L[i].size()) t.pb(L[i][j]);
forn(j, L[i].size()) t.pb(L[i][j]);
forn(j, L.size()) t.pb(0);
R.pb(t);
}
}
vi operator + (vi x, vi y) {
x.insert(x.end(), y.begin(), y.end());
return x;
}
vi dA(int m, vi r) {
if (m == 0) {
return r;
}
int l = A[m - 1].size();
vi x, y, z;
for (int i = 0; i < l; i++) {
z.pb(((r[i] + r[l + i]) % 2 + 2) % 2);
x.pb((r[l + i] + (r[i] - z[i])) / 2);
y.pb((r[l + i] - (r[i] - z[i])) / 2);
}
return dA(m - 1, x) + dA(m - 1, y) + z;
}
vii B[15];
void gB(int m) {
if (m == 1) {
B[1] = {{1}, {0}};
return ;
}
vii &L = B[m - 1], &V = A[m - 1], &R = B[m];
forn(i, L.size()) {
vi t;
forn(j, L[i].size()) t.pb(L[i][j]);
forn(j, V[i].size()) t.pb(V[i][j] == 1);
R.pb(t);
}
forn(i, L.size()) {
vi t;
forn(j, L[i].size()) t.pb(L[i][j]);
forn(j, V[i].size()) t.pb(V[i][j] == -1);
R.pb(t);
}
}
vi dB(int m, vi r) {
if (m == 1) {
return {r[0]};
}
int l = B[m - 1].size();
vi x, y;
for (int i = 0; i < l; i++) {
x.pb(r[i] - r[l + i]);
}
x = dA(m - 1, x);
for (int i = 0; i < l; i++) {
int t = r[i];
for (int j = 0; j < (int)x.size(); j++) {
t -= x[j] * (A[m - 1][i][j] == 1);
}
y.pb(t);
}
y = dB(m - 1, y);
return y + x;
}
int n;
double K;
int query(vi A) {
string S;
for (int i = 0; i < n; i++)
S += "YN"[A[i]];
printf("%s\n", S.c_str());
fflush(stdout);
int res;
scanf("%d", &res);
if (res == n) exit(0);
return res;
}
int popcnt(vi x) {
int c = 0;
for (auto i : x) c += i;
return c;
}
int main() {
cin >> n >> K;
for (int i = 0; i < 11; i++) gA(i);
for (int i = 1; i < 11; i++) gB(i);
int c = 1;
while (B[c][0].size() < n) c++;
vi ret;
ret.clear();
for (int i = 0; i < B[c].size(); i++) {
ret.pb(query(B[c][i]));
}
int lst = ret.back();
for (int i = 0; i < B[c].size(); i++) {
ret[i] = (ret[i] - lst + popcnt(B[c][i])) / 2;
}
vi ans = dB(c, ret);
query(ans);
return 0;
}
```
**特别鸣谢**
感谢 [曾铭豪](https://www.luogu.com.cn/user/42299) 大佬对这道题解法、标程、数据等多方面的建议、启发和指导。