自动搬运

查看原文

来自洛谷，原作者为

	andychen_2012 **

搬运于2025-08-24 23:07:44，当前版本为作者最后更新于2025-02-19 09:54:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提交通道：IP over Avian Carrier - Problem - QOJ.ac

我一开始的想法是，将连续 $C$ 个字符拼起来，变成一个 $[0,2^C)$ 内的数，记 $[0,2^K)$ 内 $\mathrm{popcount}=C$ 的数构成的集合为 $T$，而后设计一个函数 $f(x):[0,2^C) \to T$，使得该函数为双射关系。但是随后我发现只有 $C=3,K=4$ 的时候才可以设计出这样的函数。因此我不得不重新思考。

我们首先将串 $X$ 按顺序拆分为 $C$ 个长为 $N$ 的串 $a,b,c,\cdots$。

当 $C=3,K=4$ 的时候，我们可以自然的想到四个串分别为 $a,b,c,a \oplus b \oplus c$，解码是自然的。

当 $C=2,K=4$ 的时候，我们考虑前三个分别是 $a,b,a \oplus b$，对于第四个串，其需要能通过 $a \oplus b$ 解出 $a,b$，因此可以考虑 $s_i=a_i \oplus b_i \oplus x$，其中 $x$ 是 $a_{i+t}$ 或 $b_{i+t}$，而由于其又需要能够通过 $a$ 或 $b$ 解码，那就应该是 $a_{i+t}$ 与 $b_{i+t}$ 交替放置，我们可以使 $t=1$，那么有奇数位 $s_i=a_i \oplus b_i \oplus a_{(i+1) \bmod n}$，偶数位 $s_i=a_i \oplus b_i \oplus b_{(i+1) \bmod n}$，反过来是一样的。解码时有两种情况：给出 $a$ 或 $b$ 与 $s$，假设给定了 $a$，此时考虑奇数位上 $s_i \oplus a_i \oplus a_{(i+1) \bmod n}=b_i$，求完奇数位的 $b$ 后，对于偶数位有 $b_i=s_i \oplus a_i \oplus b_{(i+1) \bmod n}$，因此 可以得到完整的 $b$，对于给定 $b,s$ 同理。当给定 $a \oplus b,s$ 时，我们可以得知偶数位的 $a$ 与奇数位的 $b$，由 $a \oplus b$ 就可以得到偶数位的 $b$ 与奇数位的 $a$。因此这种构造是可行的。

当 $C=3,K=5$ 时，我们考虑设计 $a,b,c, a\oplus b \oplus c$，但此时我们就需要另外一个同时设计 $a,b,c$ 的函数，有点困难。我们不妨设上面那种情况的 $s=f(a,b)$，那么可以考虑 $a \oplus c,b \oplus c,a \oplus b \oplus c,c,f(a,b)$，这样无论选择哪三种，我们都可以解码出 $a,b,c$。

核心代码如下，其中 $f$ 为编码，$g$ 为 $f$ 的解码。

bitset<M> f(int N,bitset<M> x,bitset<M> y){
	bitset<M> z;
	z.reset();
	for(int i=0;i<N;++i) z[i]=x[i]^y[i]^((i&1)?y[(i+1)%N]:x[(i+1)%N]);
	return z;
}
string g(int N,bitset<M> A[6],bool vis[5]){
	string code(2*N,'0');
	if(vis[0]){
		if(vis[2])
			A[1]=A[0]^A[2];
		if(vis[3]){
			for(int i=0;i<N;i+=2) A[1][i]=(A[3][i]^A[0][i]^A[0][(i+1)%N]);
			for(int i=1;i<N;i+=2) A[1][i]=(A[3][i]^A[0][i]^A[1][(i+1)%N]);
		}
	}
	else if(vis[1]){
		if(vis[2])
			A[0]=A[1]^A[2];
		if(vis[3]){
			for(int i=1;i<N;i+=2) A[0][i]=(A[3][i]^A[1][i]^A[1][(i+1)%N]);
			for(int i=0;i<N;i+=2) A[0][i]=(A[3][i]^A[1][i]^A[0][(i+1)%N]);
		}
	}
	else if(vis[2]){
		for(int i=0;i<N;++i) A[(i&1)][(i+1)%N]=A[2][i]^A[3][i];
		for(int i=0;i<N;++i) A[((i&1)^1)][(i+1)%N]=A[2][(i+1)%N]^A[(i&1)][(i+1)%N];
	}
	for(int i=0;i<N;++i) code[i]=(char)A[0][i]+'0';
	for(int i=0;i<N;++i) code[i+N]=(char)A[1][i]+'0';
	return code;
}
string decode(int C, int K, int N, vector<string> Y, vector<int> I) {
	bitset<M> A[6];
	string code(C*N, '0');
	for(int i=0;i<C;++i){
		for(int j=i+1;j<C;++j){
			if(I[i]>I[j]){
				swap(I[i],I[j]);
				swap(Y[i],Y[j]);
			}
		}
	}
	bool vis[5]={0};
	for(int i=0;i<C;++i) vis[I[i]]=1;
	#define setA for(int i=0;i<K;++i) A[i].reset();\
	for(int j=0;j<C;++j) for(int i=0;i<N;++i) A[I[j]][i]=Y[j][i]-'0';
	setA
	if(C==3&&K==4){
		if(I[2]==3){
			bitset<M> s;
			s=A[0]^A[1]^A[2]^A[3];
			for(int i=0;i<3;++i){
				if(vis[i]) continue;
				A[i]=s;
				break;
			}
		}
		for(int i=0;i<3;++i){
			for(int j=0;j<N;++j)
				code[i*N+j]=(char)A[i][j]+'0';
		}
	}
	else if(C==2&&K==4)
		return g(N,A,vis);
	else{
		if(vis[4]){
			bitset<M> s=A[4];
			for(int i=0;i<3;++i){
				if(vis[i]) A[i]^=s;
			}
			code.clear();
			code=g(N,A,vis);
			code+=Y[2];
		}
		else if(vis[3]){
			if(vis[0]&&vis[1]) A[2]=A[0]^A[1];
			else if(vis[0]&&vis[2]) A[1]=A[0]^A[2];
			else if(vis[1]&&vis[2]) A[0]=A[1]^A[2];
			for(int i=0;i<3;++i) vis[i]=!vis[i];
			code.clear();
			code=g(N,A,vis);
			setA;
			if(!vis[0]){
				string y;
				for(int i=0;i<N;++i) y.push_back((A[0][i]^(code[i]-'0'))+'0');
				code+=y;
			}
			else if(!vis[1]){
				string y;
				for(int i=0;i<N;++i) y.push_back((A[1][i]^(code[i+N]-'0'))+'0');
				code+=y;
			}
		}
		else{
			code.clear();
			code+=change(N,A[1]^A[2]);
			code+=change(N,A[0]^A[2]);
			code+=change(N,A[0]^A[1]^A[2]);
		}
	}
	return code;
}