The 2025 ICPC 德国 German Collegiate Programming Contest——J. Jumbled Packets（使用22作为分隔符，其他地方不能出现22这样子的分隔符）

题目大意

这是一道交互题，你的程序会对每个测试用例被运行两次。

编码阶段（Encode）：给你一个长度为 $n$ 的二进制串 $s$（仅含 0 和 1），你需要输出一个长度同为 $n$ 的三进制串（可使用 0、1、2）。

解码阶段（Decode）：你在编码阶段输出的三进制串会被做一次循环旋转（即取某个后缀拼上对应的前缀，也可能不旋转），然后作为输入给你。你需要根据这个被旋转过的三进制串，还原出编码阶段的原始二进制串。

换句话说，你需要设计一种编码方案，使得即使编码后的串被任意循环旋转，你仍然能唯一地解码出原始二进制串。编码串长度必须和原串相同，且只能使用三种字符。

数据范围：$1 \le n \le 10^5$。

样例 1：编码阶段，原始串为 001，编码输出 002。解码阶段，收到的是 002 循环旋转后的 200，需要还原出 001。

输入（编码阶段）：
Encode
3
001

输出：
002

输入（解码阶段）：
Decode
3
200

输出：
001

样例 2：编码阶段，原始串为 0100，编码输出 2100。解码阶段，收到的恰好没有旋转，仍为 2100，需要还原出 0100。

输入（编码阶段）：
Encode
4
0100

输出：
2100

输入（解码阶段）：
Decode
4
2100

输出：
0100

思路讲解

使用二二作为分隔符。其他地方不允许出现二二为分隔符的这个情况。

长度大于8位的时候，使用二二作为分隔符，把这个字符串，把二进制字符串的前8位转化为6位，然后前面添上二二。然后转换的这6位三进制字符串要求第一位 不能为二，最后一位不能为二，然后其中不能有二二这样子的字符。然后这样子转好以后，然后就好了。这样子转好以后呢，在解码的时候，我们就能够看到这个22的地方，然后我们知道我们的22都是放在开头的，我们就知道这个字符串它到底被循环移动了几位。

之所以不用二作为分隔符，就是不用一个二作为分隔符，是因为只用一个二的话，那么相当于你后面的就是二进制的字符串了，你后面就是一个二进制的字符串了，它造成了非常大量的信息的损失，所以我们就选用二二作为分隔符。当然你也可以用三个二，用四个二作为分隔符，但是那个可能会更加复杂。谢谢，但是意思反正是这个意思。

那么如果说长度小于8位的时候呢？长度小于8位的时候，我们是这样子做，就是直接暴力的进行双射就可以了。

包括长度大于8位，怎么把那6位给转回8位，我们也是用双设，就是直接我们下面放一个这个代码吧，就是非常暴力的。

const ll len2=8,len3=6;
vector<string> two_s;
// 生成该长度的二进制串
for (ll status=0;status<(1<<len2);++status) {
    string sta;
    ll op_status=status;
    while (true) {
        if (op_status==0) {
            break;
        }
        sta.push_back('0'+(op_status&1));
        op_status/=2;
    }
    sta.resize(len2,'0');
    two_s.push_back(sta);
}
ll idx=0;
for (ll status=0;status<pow_three[len3];++status) {
    string sta;
    ll op_status=status;
    while (true) {
        if (op_status==0) {
            break;
        }
        sta.push_back('0'+op_status%3);
        op_status/=3;
    }
    sta.resize(len3,'0');
    // 不允许开头为 2 ,这个是因为如果说开头为二的话，会造成一些问题。就是开头二如果连着前面那个二，然后就就，它会造成一个连接，能相当于又造出来一个二二，这个是会造成混乱的。
    if (!(sta.find("22")==-1 && sta.front()!='2')) {
        continue;
    }
    three_to_two[sta]=two_s[idx];
    two_to_three[two_s[idx]]=sta;
    ++idx;
    if (idx>=two_s.size()) {
        break;
    }
}

AC代码

AC
https://qoj.ac/submission/2031795
AC
https://codeforces.com/gym/106129/submission/362719223

源代码

/**
 * Problem: J. Jumbled Packets
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/J
 * Created: 2026-02-11 14:57:00
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
bool is_unique(const string &s,const map<string,string> &mp){
    for (int i=0;i<s.size();++i) {
        string ops=s;
        rotate(ops.begin(),ops.begin()+i+1,ops.end());
        if (mp.contains(ops)) {
            return false;
        }
    }
    return true;
}
string find_str(const string &s,const map<string,string> &mp) {
    for (int i=0;i<s.size();++i) {
        string ops=s;
        rotate(ops.begin(),ops.begin()+i+1,ops.end());
        auto it=mp.find(ops);
        if (it!=mp.end()) {
            return it->second;
        }
    }
    assert(true);
    return "Error";
}
void Solve() {
    string op;
    cin>>op;
    ll N;
    cin>>N;
    map<string,string> three_to_two;
    map<string,string> two_to_three;
    vector<ll> pow_three(20);
    pow_three[0]=1;
    for (int i=1;i<=15;++i) {
        pow_three[i]=pow_three[i-1]*3;
    }
    if (N<=8) {
        // len<=8 直接双射计算
        // 暴力生成这个长度 <=8 的双射
        do {
            for (ll len=1;len<=8;++len) {
                vector<string> two_s;
                // 生成该长度的二进制串
                for (ll status=0;status<(1<<len);++status) {
                    string sta;
                    ll op_status=status;
                    while (true) {
                        if (op_status==0) {
                            break;
                        }
                        sta.push_back('0'+(op_status&1));
                        op_status/=2;
                    }
                    sta.resize(len,'0');
                    two_s.push_back(sta);
                }
                ll idx=0;
                // 生成该长度的三进制串
                for (ll status=0;status<pow_three[len];++status) {
                    string sta;
                    ll op_status=status;
                    while (true) {
                        if (op_status==0) {
                            break;
                        }
                        sta.push_back('0'+op_status%3);
                        op_status/=3;
                    }
                    sta.resize(len,'0');
                    if (is_unique(sta,three_to_two)) {
                        three_to_two[sta]=two_s[idx];
                        two_to_three[two_s[idx]]=sta;
                        ++idx;
                    }
                    if (idx>=two_s.size()) {
                        break;
                    }
                }
            }
        }while (false);
    }else {
        const ll len2=8,len3=6;
        vector<string> two_s;
        // 生成该长度的二进制串
        for (ll status=0;status<(1<<len2);++status) {
            string sta;
            ll op_status=status;
            while (true) {
                if (op_status==0) {
                    break;
                }
                sta.push_back('0'+(op_status&1));
                op_status/=2;
            }
            sta.resize(len2,'0');
            two_s.push_back(sta);
        }
        ll idx=0;
        for (ll status=0;status<pow_three[len3];++status) {
            string sta;
            ll op_status=status;
            while (true) {
                if (op_status==0) {
                    break;
                }
                sta.push_back('0'+op_status%3);
                op_status/=3;
            }
            sta.resize(len3,'0');
            if (!(sta.find("22")==-1 && sta.front()!='2' && sta.back()!=2)) {
                continue;
            }
            three_to_two[sta]=two_s[idx];
            two_to_three[two_s[idx]]=sta;
            ++idx;
            if (idx>=two_s.size()) {
                break;
            }
        }
    }


    if (op=="Encode") {
        string s;
        cin >> s;
        if (N<=8) {
            cout<<two_to_three[s]<<"\n";
            return;
        }
        string pre8(s.begin(),s.begin()+8);
        string thr6=two_to_three[pre8];
        string code="22"+thr6+string(s.begin()+8,s.end());
        cout<<code<<"\n";
    }else {
        string s;
        cin >> s;
        if (N<=8) {
            cout<<find_str(s,three_to_two)<<"\n";
            return;
        }
        ll pos22=s.find("22");
        if (pos22==-1) {
            rotate(s.begin(),s.begin()+SZ(s)-1,s.end());
        }else {
            rotate(s.begin(),s.begin()+pos22,s.end());
        }
        string code=three_to_two[string(s.begin()+2,s.begin()+8)]+string(s.begin()+8,s.end());
        cout<<code<<"\n";
    }
    
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2031795
AC
https://codeforces.com/gym/106129/submission/362719223

*/

心路历程（WA，TLE，MLE……）