题解：P11481 [NordicOI 2017] IP over Avian Carriers（通信题无法评测）

· · 题解

提交通道：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;
}