CodeForces Round 730 D1. RPD and Rap Sheet (Easy Version)题解

Codeforces Round #730 (Div. 2)

题意:

t组数据,每组给一个n和k,(easy version里面k=2) 每一次系统会输入一个初始的密码(初始密码是一个在$[0,n-1]$的随机值),你可以最多输出n次询问,如果猜对了密码系统会输入1,否则输入0.但密码不是不变的,每次会根据如下公式变化
$$
旧密码\bigoplus新密码=询问值
$$

题解:

设初始密码为X,第i次询问值为$P_i$,新密码为Y

根据异或的交换律得到
$$
旧密码\bigoplus新密码=询问值\to 旧密码\bigoplus询问值=新密码\to X\bigoplus P_i=Y
$$
根据异或的结合律
$$
(((X\bigoplus P_1) \bigoplus P_2 )\bigoplus … P_i)=X\bigoplus (P_1 \bigoplus P_2 \bigoplus … P_i)
$$
所以可以把初始密码每次异或一个询问值得到一个新密码简化为是在异或了一堆询问值后得到一个新密码.

现在我们假设$P_i=(i-1)\bigoplus P_1 \bigoplus P_2 \bigoplus … P_{i-1}$

可以得到
$$
P_{X+1}=X\bigoplus (P_1 \bigoplus P_2 \bigoplus … P_i\bigoplus… P_{X})
$$
我们惊奇的发现初始密码X异或上前X个询问的值就是
$$
X\bigoplus (P_1 \bigoplus P_2 \bigoplus … P_i\bigoplus… P_{X})
$$
所以询问到第X+1次时其询问值一定等于当前密码的值

还可以想到另一种
$$
P_1=0\P_i=(i-1)\bigoplus(i-2) \ 2<=i<=n
$$
因为
$$
第X+1次询问:P_{X+1}=X\bigoplus(X-1)\
而初始密码在经过X次询问等于X\bigoplus(0\bigoplus1\bigoplus 2\bigoplus1\bigoplus3\bigoplus2\bigoplus…X-1\bigoplus X-2)\to X\bigoplus(X-1)
$$
所以询问到第X+1次也可以得到当前密码值

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cmath>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
inline ll read();
int main() {
    int t = 1;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            if (i == 1)cout << 0 << '\n';
            else{
                cout<<((i-1)^(i-2))<<'\n';
            }
            int res;
            cin >> res;
            if (res == 1)
                break;
        }
    }
    return 0;
}


inline ll read() {
    char ch = getchar();
    ll p = 1, data = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')p = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        data = data * 10 + (ch ^ 48);
        ch = getchar();
    }
    return p * data;
}