The 2025 ICPC 德国 German Collegiate Programming Contest——J. Jumbled Packets（使用22作为分隔符，其他地方不能出现22这样子的分隔符） · znzryb
## 题目大意
这是一道交互题，你的程序会对每个测试用例被运行**两次**。
**编码阶段（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位，我们也是用双设，就是直接我们下面放一个这个代码吧，就是非常暴力的。
```cpp
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](https://qoj.ac/submission/2031795)
AC
[https://codeforces.com/gym/106129/submission/362719223](https://codeforces.com/gym/106129/submission/362719223)
::: 源代码
```cpp
/**
* 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……）