题解 P6720
入门题杀手
·
·
题解
P6720
题面戳这里
block
异或的性质：
-
a⊕b=c$ → $a⊕c=b$ 且 $b⊕c=a
对于数列 R_n ，已知：
-
R_n$ = $R_{n-2}$ $\oplus $ $R_{n-1}
-
R_3$ = $R_2$ $\oplus $ $R_1
-
R_4$ = $R_3$ $\oplus $ $R_2$=$R_1
-
R_5$ = $R_4$ $\oplus $ $R_3$=$R_1$ $\oplus $ $R_3$ = $R_2
-
R_6$ = $R_5$ $\oplus $ $R_4$=$R_1$ $\oplus $ $R_2$ = $R_3
-
.......
即发现除 R_0 外，数列 R_n 呈周期性：
-
R_n$ = $R_{(n-1)\pmod 3+1}
且至多由 4 个元素组成： R_0 、 R_1 、 R_2 、 R_3 。
（ R_0 很特殊只在第一位出现，所以说放在最后处理）。
同时函数 M_{(n)} 是一个双射，即保证对于：
x\not=y$ ， $x =y$ → $M_{(x)}\not=M_{(y)}
若第 i+1 次询问与第 j+1 次询问返回的值 M_{k} 相同，
且此时的 R_i 与 R_j 的值不同，即是 ：
M(A_i \oplus R_i)$ = $M(A_j \oplus R_j)
则可知：
A_i \oplus R_i$ = $A_j \oplus R_j
移项可得：
A_i \oplus A_j$ = $R_i \oplus R_j =R_k
那么此时的$R_k$可求，**同理**可求出 $R_1$ 、 $R_2$ 、 $R_3$ 。
------------
## 代码实现.cpp：
第一次**询问** $0$ ，记录 $M[R[0]]$ 的值：
```cpp
printf("0\n");
cout.flush();
int TMP;
scanf("%d",&TMP);
```
当 $R[x]$ **不确定**时，第 $i$ 次询问 **询问次数** $-2$ 即 $(i-2)$ ，
数组 $R$ 的**脚标**可表示为: $i$ $mod$ $3+1$ 。
定义值域数组 $pos[j]$ 表示当 $M[x]$ 为 $j$ 时的**询问次数** $-2$ 即为 $(i-2)$ 。
```
for(int i=0; i<256; i++) {
printf("%d\n",i);
cout.flush();
scanf("%d",k+i);
if(pos[k[i]]!=-1)//表示大小为k[i]的值已经出现过了
R[find(i%3+1,pos[k[i]]%3+1)]=(i^(pos[k[i]]));
// R[k]=R[i]^R[j]=A[i]^A[j]
pos[k[i]]=i;
tot=i;
if(check()) break;
}
```
如果 $R[1]$ 、 $R[2]$ 、 $R[3]$ 中已知**两个**，就可以**异或**起来推出另一个，退出循环；
此时就可以**构造**出函数 $M_{(x)}$ 的脚标，**定向**求出未知的 $M_{(x)}$ ：
~~之前忽略的 $R[0]$ 也可以在这个时候顺便求出来。~~
```cpp
for(int i=0; i<256; i++) {
if(M[i]==-1) {//说明M[i]还未更新
tot++;
printf("%d\n",(R[tot%3+1]^i));
cout.flush();
scanf("%d",M+i);
}
if(M[i]==TMP) R[0]=i;
}
```
由**容斥原理**可证明，询问次数在 $256$ 次内一定可会有**重复**的数字出现，所以能够在要求的次数内询问得到答案。
~~最后**输出**的时候记得 `cout.flush()`！~~
详细实现**代码**附上：
```cpp
#include<bits/stdc++.h>
using namespace std;
int R[5]= {-1,-1,-1,-1},M[333];//RT
int pos[333],k[333],tot;
inline int find(int x,int y) {//输入1、2、3中的两个返回另一个
for(int i=1; i<=3; i++) if(i!=x&&i!=y) return i;
}
inline bool check() {//判断退出条件
int tmp=0;
for(int i=1; i<=3; i++) tmp+=(R[i]==-1);//判断R[]有几个已求出
if(tmp==1) {
if(R[1]==-1) R[1]=R[2]^R[3];//若有两个R[]已经求出，即可推出第三个R[]
if(R[2]==-1) R[2]=R[1]^R[3];
if(R[3]==-1) R[3]=R[1]^R[2];
}
return (tmp<=1);
}
int main() {
memset(M,-1,sizeof(M));//由于数据有0 需要初始化
memset(pos,-1,sizeof(pos));
printf("0\n");
cout.flush();
int TMP;
scanf("%d",&TMP);
for(int i=0; i<256; i++) {
printf("%d\n",i);
cout.flush();
scanf("%d",k+i);
if(pos[k[i]]!=-1)
R[find(i%3+1,pos[k[i]]%3+1)]=(i^(pos[k[i]]));
pos[k[i]]=i;
tot=i;
if(check()) break;
}
for(int i=0; i<=tot; i++) M[(i^R[i%3+1])]=k[i];
for(int i=0; i<256; i++) {
if(M[i]==-1) {
tot++;
printf("%d\n",(R[tot%3+1]^i));
cout.flush();
scanf("%d",M+i);
}
if(M[i]==TMP) R[0]=i;
}
printf("SOLUTION\n");
cout.flush();
for(int i=0; i<=2; i++) {
printf("%d\n",R[i]);
cout.flush();
}
for(int i=0; i<256; i++) {
printf("%d\n",M[i]);
cout.flush();
}
return 0;
}
```