考试（Exams）（2021 CoE III 附加）

题目简述

设有 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 分。

#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 分。

#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 分。

代码：

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

特别鸣谢

感谢 曾铭豪 大佬对这道题解法、标程、数据等多方面的建议、启发和指导。