戴言老师有一天闲来无事，用1秒钟时间，随手切了18套题。这十八套题闪耀着戴言老师智慧的光芒飘向太空，多年后，它们成为了散落在宇宙中的十八大星系。0202年，太空旅行者duyi发现了它们，并穷尽必生精力游历了这十八个星系，将他的见闻整理成册。这就是「DY十八章」。
本套题来自正睿。under权限：19 csp-s 线上冲刺
字符串
子序列匹配问题（给定一个字符串\(s\)，问它是不是另一个字符串\(t\)的子序列），有一个经典的贪心方法。逐个考虑\(s\)的每一位，设当前考虑了\(s_{1\dots i}\)，在\(t\)上匹配到位置\(j\)（即\(s_{1\dots i}\)是\(t_{1\dots j}\)的子序列，且\(j\)是满足这样条件的最小的\(j\)）。接下来直接让\(j\)跳到\(t\)上\(j\)之后的、第一个等于\(s_{i+1}\)的位置即可。如果找不到这样的位置，则说明匹配失败：\(s\)不是\(t\)的子序列。
对于本题，可以把这个贪心的过程搬到DP上。
设\(dp[i][j]\)，表示我们构造出的串，在\(S\), \(T\)上用上述方法贪心地匹配，分别匹配到了第\(i\)、第\(j\)个位置，所需要构造的串的最小长度。预处理出\(S\), \(T\)上每个位置之后第一个\(0\) / \(1\)在哪里出现，则可以\(O(1)\)转移。
这个DP是比较容易的。然而难点在于，如何使字典序最小呢？字典序最小，肯定是要从前往后贪心。但是这个贪心的前提又是使长度最小。我们改变一下\(dp\)数组的定义，变成：此时最少还需要构造多长的串，才能使其是\(S_{i+1\dots n}\)和\(T_{j+1\dots m}\)的公共非子序列。那么在转移时，如果下一位填\(0\)转移到的长度\(\leq\)填\(1\)转移到的长度，我们就让下一位填\(0\)，否则让下一位填\(1\)。并且用一个数组记录下转移的路径。这种从后往前的DP，可以用记忆化搜索实现，比较方便。
时间复杂度\(O(nm)\)。
参考代码（片段）：
const int MAXN=4000,INF=0x3f3f3f3f;
char s[MAXN+5],t[MAXN+5];
int n,m,dp[MAXN+5][MAXN+5],ns[MAXN+5][2],nt[MAXN+5][2],ps[2],pt[2];
pair<int,pii>nxt[MAXN+5][MAXN+5];
int dfs(int i,int j){
assert(i==n+1||j==m+1||s[i]==t[j]);
if(dp[i][j]!=INF)return dp[i][j];
if(i==n+1&&j==m+1)return dp[i][j]=0;
dp[i][j]=dfs(ns[i][0],nt[j][0])+1;
nxt[i][j]=mk(0,mk(ns[i][0],nt[j][0]));
if(dfs(ns[i][1],nt[j][1])+1<dp[i][j]){
dp[i][j]=dfs(ns[i][1],nt[j][1])+1;
nxt[i][j]=mk(1,mk(ns[i][1],nt[j][1]));
}
return dp[i][j];
}
void get_res(int i,int j,string& res){
if(i==n+1&&j==m+1)return;
res+=(char)(nxt[i][j].fi+'0');
get_res(nxt[i][j].se.fi,nxt[i][j].se.se,res);
}
int main() {
cin>>n>>m>>(s+1)>>(t+1);
ps[0]=ps[1]=n+1;
pt[0]=pt[1]=m+1;
ns[n+1][0]=ns[n+1][1]=n+1;
nt[m+1][0]=nt[m+1][1]=m+1;
for(int i=n;i>=1;--i)ns[i][0]=ps[0],ns[i][1]=ps[1],ps[s[i]-'0']=i;
for(int i=m;i>=1;--i)nt[i][0]=pt[0],nt[i][1]=pt[1],pt[t[i]-'0']=i;
memset(dp,0x3f,sizeof(dp));
int ans0=dfs(ps[0],pt[0])+1;
//cout<<ans0<<endl;
string res0="0";
get_res(ps[0],pt[0],res0);
//cout<<res0<<endl;
memset(dp,0x3f,sizeof(dp));
memset(nxt,0,sizeof(nxt));
int ans1=dfs(ps[1],pt[1])+1;
//cout<<ans1<<endl;
string res1="1";
get_res(ps[1],pt[1],res1);
//cout<<res1<<endl;
if(ans0<=ans1)cout<<res0<<endl;
else cout<<res1<<endl;
return 0;
}
相关题目推荐：
序列
考虑最终每个数的出现次数，一定是\(2^x-1\)的形式（即二进制下全是\(1\)）。也就是说，对于每个数值，假设当前已经选了\(2^x-1\)个，那么下一次如果要选该数值，必定一次新增\(2^x\)个。当然，我们不一定盯着一个值选。可能由于该数值已经选了过多（\(x\)太大），导致选该数值不如选一个比它更大、但出现次数更少的数划算。更直观地讲，我们可以把每次的选择，列成一张表格，行表示值，列表示该值新增的出现次数：
我们要做的，就是在该表格中，选择尽量多的格子，使其权值和\(\leq n\)。
根据贪心，我们肯定先选权值小的格子。所以可以二分我们选的最大权值，记为\(\text{mx}\)。问题转化为求所有权值权值\(\text{mx}\)的格子的权值和，然后判断是否\(\leq n\)。
这个表格很特殊，它行很多，高达\(O(n)\)级别，列却只有\(O(\log n)\)级别。所以我们枚举每一列，可以\(O(1)\)算出要从这一列里选多少个。知道选多少个后，求这一列的和，就相当于\(2^x\)乘以一个等差数列，也可以\(O(1)\)计算。
需要注意的是，等于\(\text{mx}\)的数，可能一部分选，一部分不选，要注意判断。
二分出最大权值后，我们再重复一遍二分的过程，就能求出选到的数量了。
单次询问时间复杂度\(O(\log^2n)\)。
参考代码（片段）：
ull n,sn,sum,cnt;
bool check(ull mx){
sum=0;cnt=0;
--mx;
for(int i=0;i<=60;++i){
ull lim=mx/(1ull<<i);
if(lim>sn||(lim+1)*lim/2>n/(1ull<<i))return false;
sum+=(lim+1)*lim/2*(1ull<<i);
cnt+=lim;
if(sum>n)return false;
}
++mx;
ull rest=n-sum;
for(int i=0;i<=60;++i){
if(mx%(1ull<<i)==0){
if(rest<mx)break;
rest-=mx;
cnt++;
}
else break;
}
if(rest==n-sum)return false;
sum=n-rest;
return true;
}
int main() {
int T;cin>>T;while(T--){
cin>>n;
sn=sqrt(n);sn<<=1;
ull l=1,r=n;
while(l<r){
ull mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
check(l);
//cout<<sum<<endl;
cout<<cnt<<endl;
}
return 0;
}
交换
先假设所有数字互不相同。我们从小到大考虑每个数字。那么根据题目要求，当前数字，要么放在开头，要么放在结尾。
对于一次交换操作，我们在较小的数上计算其代价。于是，把当前数挪到前面的代价，就是其前面还未考虑过的数的数量。同理，挪到后面的代价，就是其后面还未考虑过的数的数量。容易发现，当前数无论放在前面还是放在后面，都不影响它后面数的代价，因为代价只和未考虑的数有关。所以可以贪心地：哪种移动方式代价小，就移到哪里。至于求代价，用支持带点修改、区间求和的数据结构（如线段树）简单维护即可。
当有重复的数字时，最优情况下，相同数字间是不会发生交换的：即，所有交换完成后，相同数字间的相对顺序不变。因为如果发生了交换，那么不做这次交换一定能使答案更优。但是用上述的方法，可能就会计算相同数字间的交换。为了避免这种情况，我们按每个值考虑：先把当前值的所有出现位置，都设置为“已考虑”。这样就能避免交换两个相同值的问题了。
时间复杂度\(O(n\log n)\)。
参考代码（片段）：
const int MAXN=3e5;
struct SegmentTree{
int sum[MAXN*4+5];
void build(int p,int l,int r){
if(l==r){sum[p]=1;return;}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
sum[p]=sum[p<<1]+sum[p<<1|1];
}
void modify(int p,int l,int r,int pos,int x){
if(l==r){sum[p]+=x;return;}
int mid=(l+r)>>1;
if(pos<=mid)modify(p<<1,l,mid,pos,x);
else modify(p<<1|1,mid+1,r,pos,x);
sum[p]=sum[p<<1]+sum[p<<1|1];
}
int query(int p,int l,int r,int ql,int qr){
if(ql>qr)return 0;
if(ql<=l && qr>=r)return sum[p];
int mid=(l+r)>>1,res=0;
if(ql<=mid)res+=query(p<<1,l,mid,ql,qr);
if(qr>mid)res+=query(p<<1|1,mid+1,r,ql,qr);
return res;
}
SegmentTree(){}
}T;
int n,a[MAXN+5];
pii p[MAXN+5];
int main() {
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i],p[i]=mk(a[i],i);
sort(p+1,p+n+1);
T.build(1,1,n);
ll ans=0;
for(int i=1;i<=n;++i){
int j=i;
while(j+1<=n&&p[j+1].fi==p[i].fi)++j;
for(int k=i;k<=j;++k){
T.modify(1,1,n,p[k].se,-1);
}
for(int k=i;k<=j;++k){
int vl=T.query(1,1,n,1,p[k].se-1);
int vr=T.query(1,1,n,p[k].se+1,n);
ans+=min(vl,vr);
}
i=j;
}
cout<<ans<<endl;
return 0;
}