思路
这是一篇乱搞题解，不保证能过所有 hack，能过官方数据
关于乱搞的正确性咱会在最后说。不知道乱搞能不能过审，过不了审就放自己博客了（）
首先看到字典序想到贪心，我们可以设状态 $f_{i,j}$ 表示目前位置为 $i$，剩下可以删的长度为 $j$ （事实上，这个可删的长度就是可删线段压缩后的状态，二者是等价的）。
我们贪心地尝试下一个字母，从 $a$ 到 $z$ 一次尝试，遍历队列里的每一个状态（咱的实现是 BFS ），枚举所有可能的当前枚举字符的位置，算出这些位置 $pos$ 和 $i$ 的差，查看这个距离是否在二进制集合意义下属于 $j$，即 $(pos-i) \in j$，如果是，则转移到 $f_{pos+1,j - (pos-i)}$。
理论复杂度复杂度 $O(n^4)$，不过实际跑出来的复杂度在极端数据（泉部为 $a$）的情况下也只有 $O(n^3)$，也许是咱哪里算错了吧。发现这个算法在绝大多数情况下根本跑不满，因为你找到了 $ch$ 处有转移之后就直接退出本回合的转移了（贪心嘛），你的字符种类再多，在绝大多数情况下只有最小的字符会起作用。于是我们交上代码，发现 TLE on #7 ，数据就是泉部为 $a$ 的数据。
特判是没有用的，一是“面对数据编程”本质作弊，二是出题人肯定不傻，在其他数据中随机插入了少量其他字符。对每个回合转移出来的状态数打表，发现状态数在达到某一个值之后很快固定为一个值，这是因为我们每个状态的转移本来就很多（每个状态 $n$ 个），再加上在大多数字母为 $a$ 的情况下转移是极容易成立的，于是剪枝，在下一层的状态数固定很多次以后直接退出。经过细微调参通过本题。
乱搞感想（？）及改良
咱认为一个好的乱搞应该是针对所有数据的，而不好的乱搞则是只针对某一种数据。很惭愧咱的乱搞应该算后者，因为它的确是对着数据调出来的。然而我们通过上文的推理，想要把咱的这种代码在复杂度上卡掉，一定只能是某一种字符重复出现（应该别无可能），那么我们自然可以把这当做一个性质来用。
另外，乱搞是一场不公平的博弈。出题人能够看到选手的程序并加以针对，而选手在赛时无法看到数据。所以我们只要把乱搞代码写死，过不了多久它就真的要死了。那么怎么办呢？我们干脆不把代码写死！让代码“活起来”的方法就是随机化。
“没有随机化的乱搞在 hack 面前是无力的”，为了不被针对性出数据，我们加入随机化因素。为了防止“无效转移固定次数后退出”被针对，我们略微随机这个“固定次数”的数字，并且对转移序列进行 shuffle。咱目前没有想出能够卡掉加了这些随机化的数据，如果真的没有数据能在合理概率下卡掉它的话，这也能算一种随机化正解吧。
不过这些随机化和乱搞调参卡常需要的时间并不比想正解好多少......有能力最好还是写正解。写乱搞主要还是有种和出题人斗智斗勇的快感(
代码
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
using pii = pair<int,int>;
const int MAXW = 14;
const int MAXSTAT = (1<<12) + 10 + 18 + 11 + 8;
const int MAXN = 2006 + 1018 + 1108 + 1000;
string str;
int n,step,maxs,res,pos[28][MAXN],postail[28],vis[MAXN][MAXN],qTail,nxtTail;
pii q[MAXN],nxt[MAXN];
string ans;
mt19937 rng(time(0));
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>str;
n = str.length();
str = "." + str;
for(int i = 1;i <= n;i++){
pos[str[i] - 'a'][++postail[str[i] - 'a']] = i;
}
step = log2(n);
maxs = (1<<step) - 1;
res = n - maxs;
q[++qTail] = {1,maxs};
for(int i = 1;i <= res;i++){
sort(q+1,q+qTail+1);
for(int ch = 0;ch < 26;ch++){
nxtTail = 0;
int st = 1;
for(int nowi = 1,sameCnt = 0;nowi <= qTail;nowi++){
int stTail = nxtTail;
auto u = q[nowi];
while(st <= postail[ch] && pos[ch][st] < u.first)st++;
for(int it = st;it <= postail[ch];it++){
const int j = pos[ch][it];
if(((u.second & (j - u.first)) == (j - u.first))){
if(vis[j+1][u.second - (j - u.first)] != i){
vis[j+1][u.second - (j - u.first)] = i;
nxt[++nxtTail] = {j+1,u.second - (j - u.first)};
}
}
if(j > u.first + u.second)break;
}
if(nxtTail == stTail){
sameCnt++;
}else{
sameCnt = 0;
}
if(sameCnt > 60)break;
}
if(nxtTail != 0){
swap(q,nxt),swap(qTail,nxtTail);
ans += 'a' + ch;
break;
}
}
}
cout<<ans<<endl;
return not(Akano loves pure__Elysia);
}
Comments NOTHING