自动搬运

查看原文

来自洛谷，原作者为

	入门题杀手 *　*

搬运于2025-08-24 22:23:21，当前版本为作者最后更新于2020-12-02 13:59:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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$

$A_i$ 、 $A_j$ 为输入（已知）的， $R_i$ 、 $R_j$ 可转化为 $R_1$ 、 $R_2$ 、 $R_3$ 中的两个，

那么此时的$R_k$可求，同理可求出 $R_1$ 、 $R_2$ 、 $R_3$ 。

---

代码实现.cpp：

第一次询问 $0$ ，记录 $M[R[0]]$ 的值：

	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]$ 也可以在这个时候顺便求出来。

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()！

详细实现代码附上：

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