T1 换座位
这题的线性做法是这样：
我们首先从前向后模拟，确定一下一直执行到每次询问的t i t_i t i i d i id_i i d i
然后我们再从后向前模拟，确定一下执行完最后m − t i m-t_i m − t i
两个拼一下就是答案。
int now[maxn],pos[maxn];
void work()
{
//now[i]：第i个座位上现在坐着谁
//pos[i]：i号人，现在去哪个位置上坐了
for (int i=1;i<=n;i++) now[i]=i,pos[i]=i;
int a,b;
for (int i=1;i<=m;i++)
{
for (int j:ask[i]) //做这次操作之后
{
a=u[j]; b=v[j];
swap(now[a],now[b]);
pos[now[a]]=a; pos[now[b]]=b;
ans[j]=pos[id[j]];
swap(now[a],now[b]);
pos[now[a]]=a; pos[now[b]]=b;
}
swap(now[x[i]],now[y[i]]);
pos[now[x[i]]]=x[i]; pos[now[y[i]]]=y[i];
}
//现在我知道在询问发生那一刻，id去哪了
//我还需要知道，在询问发生后，每个位置的点去哪了
for (int i=1;i<=n;i++) now[i]=i,pos[i]=i;
for (int i=m;i>=1;i--)
{
for (int j:ask[i])
{
int tt=ans[j]; //走完以后在tt了
//最终tt和now[tt]互换位置了
ans[j]=now[tt]; //现在走完到now[tt]去了
}
swap(now[x[i]],now[y[i]]);
}
// for (int i=1;i<=Q;i++) cout<<ans[i]<<" ";
ll ret=0; for (int i=1;i<=Q;i++) ret=(ret+(ll)(i)*ans[i])%mod;
cout<<ret<<endl;
}
T2 蛇形数组
这题实简单。
我们考虑把每次操作对应的坐标抽象成数字i d id i d 0 0 0 i d id i d 0 0 0 0 0 0 1 1 1
那么，直接用线段树维护即可，需要动态开点。
//王老师的代码·
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5,mx=2e8+5;
int n,tot;
struct node{
int sum,lc,rc;
}tree[N*8];
int add(int rt){
tree[rt].sum = 0;
tree[rt].lc = tree[rt].rc = 0;
return rt;
}
void pushup(int rt){
tree[rt].sum = tree[tree[rt].lc].sum+tree[tree[rt].rc].sum;
}
void update(int l,int r,int rt,int p){
if(l==r){
tree[rt].sum = 1;
return;
}
int mid = (l+r)>>1;
if(p<=mid){
if(tree[rt].lc==0)tree[rt].lc=add(++tot);
update(l,mid,tree[rt].lc,p);
}
else{
if(tree[rt].rc==0)tree[rt].rc=add(++tot);
update(mid+1,r,tree[rt].rc,p);
}
pushup(rt);
}
int query(int l,int r,int rt,int val){
if(l==r){
return l;
}
int mid = (l+r)>>1;
if(tree[rt].lc==0)tree[rt].lc=add(++tot);
if(mid-l+1-tree[tree[rt].lc].sum>=val){
return query(l,mid,tree[rt].lc,val);
}
else{
if(tree[rt].rc==0)tree[rt].rc=add(++tot);
return query(mid+1,r,tree[rt].rc,val-(mid-l+1-tree[tree[rt].lc].sum));
}
}
signed main(){
cin>>n;
int root = add(++tot);
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
int c = max(abs(x),abs(y));
int pos = (2*c-1)*(2*c-1);
if(y==c){
if(-x==c)pos=(2*c+1)*(2*c+1);
else pos+=(x+c);
}
else if(x==c){
pos+=2*c+(c-y);
}
else if(-y==c){
pos+=2*c+2*c+(c-x);
}
else{
pos+=2*c+2*c+2*c+(y+c);
}
if(x==0 && y==0)pos=1;
int ret = query(1,mx*mx,root,pos);
update(1,mx*mx,root,ret);
cout<<ret<<endl;
}
return 0;
}
#include<bits/stdc++.h>
#define ll long long
#define ls lson[now]
#define rs rson[now]
#define mid ((l+r)>>1)
#define maxn 100005
#define mod 998244353
using namespace std;
//你们内部被打了多少个元素
int sum[maxn<<7],lson[maxn<<7],rson[maxn<<7];
int tot=1;
void modify(int &now,ll l,ll r,ll pos) //这个位置被打了一下
{
if (!now) now=++tot;
if (l==r) {sum[now]=1; return;}
if (pos<=mid) modify(ls,l,mid,pos);
else modify(rs,mid+1,r,pos);
sum[now]=sum[ls]+sum[rs];
return;
}
ll get(int &now,ll l,ll r,ll val) //我要找到恰好val个0所在位置
{
if (!now) now=++tot;
if (l==r) return l;
if ((mid-l+1)-sum[ls]>=val) return get(ls,l,mid,val);
return get(rs,mid+1,r,val-((mid-l+1)-sum[ls]));
}
int Q,rt=1;
ll mx=2e8*2e8+2e8;
ll x,y;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>Q;
while (Q--)
{
cin>>x>>y;
ll quan=max(abs(x),abs(y));
ll id=(2*quan-1)*(2*quan-1);
if (y==quan) //右边折线
{
if (x==-quan) id=(2*quan+1)*(2*quan+1);
else id+=(x+quan);
}
//上边折线
else if (x==quan)
{
id+=(quan+quan);
id+=(quan-y);
}
//左边折线
else if (y==-quan)
{
id+=(quan+quan); id+=(quan+quan);
id+=(quan-x);
}
else //下折线
{
id+=(quan+quan); id+=(quan+quan); id+=(quan+quan);
id+=(y-(-quan));
}
if (x==0 && y==0) id=1;
ll tmp=get(rt,1,mx,id);
// cout<<sum[rt]<<endl;
// cout<<id<<" "<<tmp<<endl;
cout<<tmp<<"\n";
modify(rt,1,mx,tmp);
}
assert(tot<(maxn<<7));
}
T3 找不同
前30分不说了。
先嘴一个也许能过的做法，但是我没写。
假设要求最近，则我们直接从所有字符串对应的二进制状态出发，一起BFS，找到距离每个点最近的点即可。
现在要求的是最远，等价于在翻转的二进制状态下要求最近，那岂不是一样的？只不过这次目标点的集合不一样了罢了。
正解的话是这样，我们定义一个d p dp d p
d p i , s t a dp_{i,sta} d p i , s t a s t a sta s t a i i i s t a sta s t a
那么d p i , s t a dp_{i,sta} d p i , s t a d p i − 1 , s t a dp_{i-1,sta} d p i − 1 , s t a d p i − 1 , s t a ⨁ 2 i + 1 dp_{i-1,sta\bigoplus 2^i}+1 d p i − 1 , s t a ⨁ 2 i + 1
初始状态是：d p 0 , s t a = 0 dp_{0,sta}=0 d p 0 , s t a = 0 s t a sta s t a − inf -\inf − inf
可以通过滚动压缩一维。时间复杂度O ( m 2 m ) O(m2^m) O ( m 2 m )
#include<bits/stdc++.h>
#define ll long long
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
#define maxn 100005
#define mod 998244353
using namespace std;
int dp[1<<18];
int n,m;
string s[maxn];
int sta[maxn];
int main()
{
cin>>n>>m; for (int i=1;i<=n;i++) cin>>s[i];
for (int i=1;i<=n;i++) for (int j=0;j<m;j++) if (s[i][j]=='G') sta[i]|=(1<<j);
memset(dp,-0x3f,sizeof(dp));
for (int i=1;i<=n;i++) dp[sta[i]]=0;
for (int i=0;i<m;i++)
for (int sta=0;sta<(1<<m);sta++)
if (((sta>>i)&1)==0)
{
int x=dp[sta],y=dp[sta|(1<<i)];
dp[sta]=max(x,y+1);
dp[sta|(1<<i)]=max(y,x+1);
}
for (int i=1;i<=n;i++) cout<<dp[sta[i]]<<endl;
}
T4 切割字符串
SOURCE：ABC240EX
容易想到的一个暴力做法是：d p i , j dp_{i,j} d p i , j i i i j j j
显然j j j 2650 2650 2650
此外，对于相同的i i i j j j d p i , j dp_{i,j} d p i , j
以及，d p i , j dp_{i,j} d p i , j j j j
那么我们考虑在做这个暴力dp的时候优化一下转移：
考虑维护一个d p dp d p i i i d p j dp_j d p j
我们顺着转移：
对于每一个i i i k k k i + 1 , . . . , n i+1,...,n i + 1 , ... , n S [ i + 1 , k ] S_{[i+1,k]} S [ i + 1 , k ] d p i , j dp_{i,j} d p i , j
显然，由于d p dp d p k k k
一个细节是，我们是用顺推的形式转移，所以需要把每一次可以更新的内容，丢到一个l a z y lazy l a zy v e c t o r vector v ec t or i i i d p dp d p
#include<bits/stdc++.h>
#define maxn 25005
#define ll long long
using namespace std;
string S;
string dp[maxn];
vector< pair<int,string> > ADD[maxn];
int n;
int check(string x,string y)
{
int len=min(x.size(),y.size());
for (int i=0;i<len;i++)
if (x[i]<y[i]) return 1;
else if (x[i]>y[i]) return 0;
return 0;
}
int main()
{
cin>>n;
cin>>S;
S='-'+S;
for (int i=0;i<=n;i++)
{
for (pair<int,string> temp:ADD[i])
{
int tt=temp.first;
if (dp[tt]=="") dp[tt]=temp.second;
else dp[tt]=min(dp[tt],temp.second);
}
string s=""; int now=1;
for (int j=i+1;j<=n;j++)
{
s+=S[j];
while (dp[now]!="" && s>dp[now])
{
now++;
}
if (dp[now]=="" || s<dp[now]) ADD[j].push_back(make_pair(now,s));
if (dp[now]=="") break;
if (check(s,dp[now])) break;
}
}
int ans=0;
for (int i=1;i<=25000;i++)
if (dp[i]!="")
{
ans=i;
}
cout<<ans<<endl;
}
复杂度证明：
首先提出这样两个引理：
（1）
∣ d p i , j ∣ ≤ ∣ d p i , j − 1 ∣ + 1 |dp_{i,j}|\leq |dp_{i,j-1}|+1 ∣ d p i , j ∣ ≤ ∣ d p i , j − 1 ∣ + 1
这个显然在任何情况下都是正确的。
因此：∣ d p i , j ∣ ≤ j |dp_{i,j}|\leq j ∣ d p i , j ∣ ≤ j
（2）
j ≤ 2650 j\leq 2650 j ≤ 2650
也是显然的。
我们首先考虑这样一个事情，对于一个位置i i i i + t i+t i + t break掉，那么：意味着这个位置更新了一个长度为t t t dp数组的第j j j j j j t t t d p i , j ′ < j dp_{i,j'<j} d p i , j ′ < j
那么，我们能想到，复杂度应该是这么算：
∑ i ∑ j m i n ( t , ∣ d p i , j ∣ ) \sum_{i}\sum_{j}min(t,|dp_{i,j}|) ∑ i ∑ j min ( t , ∣ d p i , j ∣ )
此处，t t t i \sqrt i i ∑ ∣ d p i , j ∣ \sum {|dp_{i,j}|} ∑ ∣ d p i , j ∣ i i i
看起来两个同时取得上界的时候，复杂度应该是：
∑ i i i = 4 × 10 10 \sum_i i\sqrt i =4\times 10^{10} ∑ i i i = 4 × 1 0 10
但实际上，t t t ∑ ∣ d p i , j ∣ \sum |dp_{i,j}| ∑ ∣ d p i , j ∣
当t t t ∣ d p i , j ∣ |dp_{i,j}| ∣ d p i , j ∣ [ 1 , 2 , 3 , . . . , i ] [1,2,3,...,\sqrt i] [ 1 , 2 , 3 , ... , i ] 0 0 0 O ( 3 × 10 8 ) O(3\times 10^8) O ( 3 × 1 0 8 )
当∑ ∣ d p i , j ∣ \sum |dp_{i,j}| ∑ ∣ d p i , j ∣ ∣ d p i , j ∣ |dp_{i,j}| ∣ d p i , j ∣ [ 1 , 1 , 2 , 2 , 2 , 2 , 3 , . . . , 3 , . . ] [1,1,2,2,2,2,3,...,3,..] [ 1 , 1 , 2 , 2 , 2 , 2 , 3 , ... , 3 , .. ] 0,1,00,01,10,11等子串，再按字典序拼起来后得到。此时可以认为字符串长度都是O ( 1 ) O(1) O ( 1 ) n × 2650 n\times 2650 n × 2650
大概能感觉到，这个是个凹函数，两端点的极值不炸，中间更不会炸，所以复杂度是正确的。
# T1 换座位
这题的线性做法是这样：
我们首先从前向后模拟，确定一下一直执行到每次询问的$t_i$时候，现在$id_i$跑到第几个位置上去了。
然后我们再从后向前模拟，确定一下执行完最后$m-t_i$次操作后，每一个位置的人，现在去了哪个位置。
两个拼一下就是答案。
```c++
int now[maxn],pos[maxn];
void work()
{
//now[i]：第i个座位上现在坐着谁
//pos[i]：i号人，现在去哪个位置上坐了
for (int i=1;i<=n;i++) now[i]=i,pos[i]=i;
int a,b;
for (int i=1;i<=m;i++)
{
for (int j:ask[i]) //做这次操作之后
{
a=u[j]; b=v[j];
swap(now[a],now[b]);
pos[now[a]]=a; pos[now[b]]=b;
ans[j]=pos[id[j]];
swap(now[a],now[b]);
pos[now[a]]=a; pos[now[b]]=b;
}
swap(now[x[i]],now[y[i]]);
pos[now[x[i]]]=x[i]; pos[now[y[i]]]=y[i];
}
//现在我知道在询问发生那一刻，id去哪了
//我还需要知道，在询问发生后，每个位置的点去哪了
for (int i=1;i<=n;i++) now[i]=i,pos[i]=i;
for (int i=m;i>=1;i--)
{
for (int j:ask[i])
{
int tt=ans[j]; //走完以后在tt了
//最终tt和now[tt]互换位置了
ans[j]=now[tt]; //现在走完到now[tt]去了
}
swap(now[x[i]],now[y[i]]);
}
// for (int i=1;i<=Q;i++) cout<<ans[i]<<" ";
ll ret=0; for (int i=1;i<=Q;i++) ret=(ret+(ll)(i)*ans[i])%mod;
cout<<ret<<endl;
}
```
# T2 蛇形数组
这题实简单。
我们考虑把每次操作对应的坐标抽象成数字$id$（这个需要算算），那么，每次查询，实际上就是想知道，一个初始是全$0$的序列里面，第$id$个$0$在哪里，然后把那个$0$改成$1$。
那么，直接用线段树维护即可，需要动态开点。
```c++
//王老师的代码·
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5,mx=2e8+5;
int n,tot;
struct node{
int sum,lc,rc;
}tree[N*8];
int add(int rt){
tree[rt].sum = 0;
tree[rt].lc = tree[rt].rc = 0;
return rt;
}
void pushup(int rt){
tree[rt].sum = tree[tree[rt].lc].sum+tree[tree[rt].rc].sum;
}
void update(int l,int r,int rt,int p){
if(l==r){
tree[rt].sum = 1;
return;
}
int mid = (l+r)>>1;
if(p<=mid){
if(tree[rt].lc==0)tree[rt].lc=add(++tot);
update(l,mid,tree[rt].lc,p);
}
else{
if(tree[rt].rc==0)tree[rt].rc=add(++tot);
update(mid+1,r,tree[rt].rc,p);
}
pushup(rt);
}
int query(int l,int r,int rt,int val){
if(l==r){
return l;
}
int mid = (l+r)>>1;
if(tree[rt].lc==0)tree[rt].lc=add(++tot);
if(mid-l+1-tree[tree[rt].lc].sum>=val){
return query(l,mid,tree[rt].lc,val);
}
else{
if(tree[rt].rc==0)tree[rt].rc=add(++tot);
return query(mid+1,r,tree[rt].rc,val-(mid-l+1-tree[tree[rt].lc].sum));
}
}
signed main(){
cin>>n;
int root = add(++tot);
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
int c = max(abs(x),abs(y));
int pos = (2*c-1)*(2*c-1);
if(y==c){
if(-x==c)pos=(2*c+1)*(2*c+1);
else pos+=(x+c);
}
else if(x==c){
pos+=2*c+(c-y);
}
else if(-y==c){
pos+=2*c+2*c+(c-x);
}
else{
pos+=2*c+2*c+2*c+(y+c);
}
if(x==0 && y==0)pos=1;
int ret = query(1,mx*mx,root,pos);
update(1,mx*mx,root,ret);
cout<<ret<<endl;
}
return 0;
}
```
```c++
#include<bits/stdc++.h>
#define ll long long
#define ls lson[now]
#define rs rson[now]
#define mid ((l+r)>>1)
#define maxn 100005
#define mod 998244353
using namespace std;
//你们内部被打了多少个元素
int sum[maxn<<7],lson[maxn<<7],rson[maxn<<7];
int tot=1;
void modify(int &now,ll l,ll r,ll pos) //这个位置被打了一下
{
if (!now) now=++tot;
if (l==r) {sum[now]=1; return;}
if (pos<=mid) modify(ls,l,mid,pos);
else modify(rs,mid+1,r,pos);
sum[now]=sum[ls]+sum[rs];
return;
}
ll get(int &now,ll l,ll r,ll val) //我要找到恰好val个0所在位置
{
if (!now) now=++tot;
if (l==r) return l;
if ((mid-l+1)-sum[ls]>=val) return get(ls,l,mid,val);
return get(rs,mid+1,r,val-((mid-l+1)-sum[ls]));
}
int Q,rt=1;
ll mx=2e8*2e8+2e8;
ll x,y;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>Q;
while (Q--)
{
cin>>x>>y;
ll quan=max(abs(x),abs(y));
ll id=(2*quan-1)*(2*quan-1);
if (y==quan) //右边折线
{
if (x==-quan) id=(2*quan+1)*(2*quan+1);
else id+=(x+quan);
}
//上边折线
else if (x==quan)
{
id+=(quan+quan);
id+=(quan-y);
}
//左边折线
else if (y==-quan)
{
id+=(quan+quan); id+=(quan+quan);
id+=(quan-x);
}
else //下折线
{
id+=(quan+quan); id+=(quan+quan); id+=(quan+quan);
id+=(y-(-quan));
}
if (x==0 && y==0) id=1;
ll tmp=get(rt,1,mx,id);
// cout<<sum[rt]<<endl;
// cout<<id<<" "<<tmp<<endl;
cout<<tmp<<"\n";
modify(rt,1,mx,tmp);
}
assert(tot<(maxn<<7));
}
```
T3 找不同
前30分不说了。
先嘴一个也许能过的做法，但是我没写。
假设要求最近，则我们直接从所有字符串对应的二进制状态出发，一起`BFS`，找到距离每个点最近的点即可。
现在要求的是最远，等价于在翻转的二进制状态下要求最近，那岂不是一样的？只不过这次目标点的集合不一样了罢了。
正解的话是这样，我们定义一个$dp$。
$dp_{i,sta}$表示考虑了跟$sta$二进制下前$i$位不一样，其他位一样的所有数字，跟$sta$差异度最大的状态有多大。
那么$dp_{i,sta}$转移其实就两种，要么是$dp_{i-1,sta}$，要么是$dp_{i-1,sta\bigoplus 2^i}+1$。
初始状态是：$dp_{0,sta}=0$，如果$sta$在输入中存在，如果不存在则是$-\inf$。
可以通过滚动压缩一维。时间复杂度$O(m2^m)$
```c++
#include<bits/stdc++.h>
#define ll long long
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
#define maxn 100005
#define mod 998244353
using namespace std;
int dp[1<<18];
int n,m;
string s[maxn];
int sta[maxn];
int main()
{
cin>>n>>m; for (int i=1;i<=n;i++) cin>>s[i];
for (int i=1;i<=n;i++) for (int j=0;j<m;j++) if (s[i][j]=='G') sta[i]|=(1<<j);
memset(dp,-0x3f,sizeof(dp));
for (int i=1;i<=n;i++) dp[sta[i]]=0;
for (int i=0;i<m;i++)
for (int sta=0;sta<(1<<m);sta++)
if (((sta>>i)&1)==0)
{
int x=dp[sta],y=dp[sta|(1<<i)];
dp[sta]=max(x,y+1);
dp[sta|(1<<i)]=max(y,x+1);
}
for (int i=1;i<=n;i++) cout<<dp[sta[i]]<<endl;
}
```
# T4 切割字符串
SOURCE：ABC240EX
容易想到的一个暴力做法是：$dp_{i,j}$表示考虑到$i$了，一共选了$j$个区间，结尾字符串最小是谁，也就是保留一个字符串。
显然$j$不会超过$2650$，这个可以暴力枚举算一下。
此外，对于相同的$i$，随着$j$变大，$dp_{i,j}$必然字典序单调。
以及，$dp_{i,j}$对应的字符串，长度不会超过$j$。
那么我们考虑在做这个暴力dp的时候优化一下转移：
考虑维护一个$dp$数组，存的是对于当前$i$来说，每一个$dp_j$。
我们顺着转移：
对于每一个$i$，我们暴力枚举$k$从$i+1,...,n$，看看$S_{[i+1,k]}$形成的字符串可以拼在哪一个$dp_{i,j}$的后面。
显然，由于$dp$数组本来是单调的，所以插入位置有且只可能有一个，我们直接双指针找到对应的$k$即可。
一个细节是，我们是用顺推的形式转移，所以需要把每一次可以更新的内容，丢到一个$lazy$性质的$vector$里，当枚举到$i$的时候再更新这些内容到$dp$数组中。
```c++
#include<bits/stdc++.h>
#define maxn 25005
#define ll long long
using namespace std;
string S;
string dp[maxn];
vector< pair<int,string> > ADD[maxn];
int n;
int check(string x,string y)
{
int len=min(x.size(),y.size());
for (int i=0;i<len;i++)
if (x[i]<y[i]) return 1;
else if (x[i]>y[i]) return 0;
return 0;
}
int main()
{
cin>>n;
cin>>S;
S='-'+S;
for (int i=0;i<=n;i++)
{
for (pair<int,string> temp:ADD[i])
{
int tt=temp.first;
if (dp[tt]=="") dp[tt]=temp.second;
else dp[tt]=min(dp[tt],temp.second);
}
string s=""; int now=1;
for (int j=i+1;j<=n;j++)
{
s+=S[j];
while (dp[now]!="" && s>dp[now])
{
now++;
}
if (dp[now]=="" || s<dp[now]) ADD[j].push_back(make_pair(now,s));
if (dp[now]=="") break;
if (check(s,dp[now])) break;
}
}
int ans=0;
for (int i=1;i<=25000;i++)
if (dp[i]!="")
{
ans=i;
}
cout<<ans<<endl;
}
```
## 复杂度证明：
首先提出这样两个引理：
（1）
$|dp_{i,j}|\leq |dp_{i,j-1}|+1$。
这个显然在任何情况下都是正确的。
因此：$|dp_{i,j}|\leq j$在任何情况下也是正确的。
（2）
$j\leq 2650$。
也是显然的。
我们首先考虑这样一个事情，对于一个位置$i$，假设其枚举到位置$i+t$才`break`掉，那么：意味着这个位置更新了一个长度为$t$的串到`dp`数组的第$j$个位置（此处$j$不确定）。且，这个串$t$的字典序，比之前每一个$dp_{i,j'<j}$的字典序都要大。
那么，我们能想到，复杂度应该是这么算：
$\sum_{i}\sum_{j}min(t,|dp_{i,j}|)$。
此处，$t$的上界是$\sqrt i$，$\sum {|dp_{i,j}|}$的上界是$i$。
看起来两个同时取得上界的时候，复杂度应该是：
$\sum_i i\sqrt i =4\times 10^{10}$
但实际上，$t$和$\sum |dp_{i,j}|$无法同时取得上界。
当$t$取得上界时，$|dp_{i,j}|$对应的数组是$[1,2,3,...,\sqrt i]$，通过构造全$0$的字符串取得，此时复杂度约是$O(3\times 10^8)$。
当$\sum |dp_{i,j}|$取得上界时，$|dp_{i,j}|$对应的数组按长度排序后是$[1,1,2,2,2,2,3,...,3,..]$，通过构造`0,1,00,01,10,11`等子串，再按字典序拼起来后得到。此时可以认为字符串长度都是$O(1)$级别的，复杂度是$n\times 2650$。
大概能感觉到，这个是个凹函数，两端点的极值不炸，中间更不会炸，所以复杂度是正确的。
