20231007 B 组模拟赛 题解
前言
这场我记得赛时切 T1T4，最终得分 100+45+15+100=260，排名贼高。这告诉我们正确的开题顺序有多重要。
T1
这道题很简单，考虑自己模拟一下。容易发现必然是先向一个方向走（下文以起始方向向右为例），遇到第一个 $L$ 回头，而之前经过的 $R$ 都变成 $L$ 了，那么向左遇到起点左侧第一个 $R$ 再回头，再往右的时候容易发现之前的 $L$， 就变成 $R$ 了，会碰到下一个 $L$ 再回头。那么我们只需要统计初始序列当前位置左侧有多少个 $R$，右侧有多少个 $L$ 就行了。具体计算很简单，我就不多赘述了。
复杂度可以 $O(n)$，取决于你维护的方式。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e6+5;
i64 n,a[N],cntl[N],suml[N],sumr[N];
char str[N];
signed main(){
n=read();
scanf(" %s",str+1);
forup(i,1,n){
a[i]=(str[i]=='L');
}
fordown(i,n,1){
cntl[i]=cntl[i+1];
if(a[i]){
++cntl[i];
suml[cntl[i]]=suml[cntl[i]-1]+i;
}
}
i64 cntr=0;
forup(i,1,n){
if(cntr==cntl[i+1]){
i64 ls=i*cntr-sumr[cntr],rs=suml[cntl[i+1]]-i*cntl[i+1],ans=ls*2+rs*2;
if(a[i]){
ans+=i;
}else{
ans+=n-i+1;
}
printf("%lld ",ans);
}else if(a[i]){
if(cntr<=cntl[i+1]){
i64 ls=i*cntr-sumr[cntr],rs=(suml[cntl[i+1]]-suml[cntl[i+1]-cntr])-i*cntr;
printf("%lld ",ls*2+rs*2+i);
}else{
i64 ls=i*(cntl[i+1]+1)-(sumr[cntr]-sumr[cntr-cntl[i+1]-1]),rs=suml[cntl[i+1]]-i*cntl[i+1];
printf("%lld ",ls*2+rs*2+n+1-i);
}
}else{
if(cntr>=cntl[i+1]){
i64 rs=suml[cntl[i+1]]-i*cntl[i+1],ls=i*cntl[i+1]-(sumr[cntr]-sumr[cntr-cntl[i+1]]);
printf("%lld ",ls*2+rs*2+n+1-i);
}else{
i64 rs=(suml[cntl[i+1]]-suml[cntl[i+1]-cntr-1])-i*(cntr+1),ls=i*cntr-sumr[cntr];
printf("%lld ",ls*2+rs*2+i);
}
}
if(!a[i]){
++cntr;
sumr[cntr]=sumr[cntr-1]+i;
}
}
}
T2
首先，对于划分成 $k$ 段的答案，容易发现重排后必定是一个前缀贡献其 $0$ 的数量，一个后缀贡献其 $1$ 的数量，中间有至多一个贡献前半部分 $1$ 与后半部分 $0$。而容易想到是不是可以把这一段分成两半，然后算分成 $k+1$ 段，每一的段贡献就是 $\max(cnt_0,cnt_1)$。
为方便叙述，称贡献为 $cnt_0$ 的段为“零段”，贡献为 $cnt_1$ 的段为“壹段”（大写是为了防止歧义）。容易发现上面的猜想其实在 $k\le 2$ 的时候都是可以的。首先若存在某一段 $i$，使得原序列上第 $i$ 段是零段，第 $i+1$ 段是壹段，那么直接可以把这两段合在一起。否则必然原序列上前缀全是壹段，后缀全是零段，那么必然存在至少一个 $i$，使得 $i,i+1$ 类型相同。可以考虑把这两段合在一起。对于 $k=1$，直接暴力即可，方法很多，不多赘述。
另外，容易发现原序列 $s$ 上连续的 $0$ 和 $1$ 分不分开其实无所谓，或者说连续的同一个数可以当成一个固定不分开的块，不影响答案，对于大于等于块数的 $k$，容易发现答案就是 $n$（虽然其实这并不重要）。
那么问题就转化成了有一个 $01$ 交替的带权序列，你要把它分成 $k$ 段，每一段的权值是 $\max\left(\sum val_0,\sum val_1\right)$，求最大权值和。
而容易发现这其实是一个经典的反悔贪心，相当于最初所有段都做贡献，然后每次删掉一些段不做贡献，再把左右两段合并（比如最初是 $010$，假如合并成一个 $0$ 相当于把中间一个 $1$ 的贡献删掉了）。另外，容易发现每一对相邻的 $01$ 中必定有至少一个会产生贡献，即永远不会删除两个相邻的段。
套路地，这可以用优先队列 $+$ 双向链表维护，先不考虑边界，最初插入所有初始段，每次选出权值最小的一段 $x$ 删掉，然后把它前后两段 $px,nx$ 合并，合并的一段权值为 $val_{px}+val_{nx}-val_x$，下次如果删掉这段相当于删掉 $px,nx$ 再把 $x$ 重新加入贡献，由于每次选的都是最小的，它必定不会产生负数。合并后段数 $-2$，更新对应段数的答案。
容易发现边界不太好处理，我们可以分类讨论左右边界删掉/不删掉来解决。注意删掉边界只会使段数 $-1$，另外注意假如钦定边界删掉那么边界的下一个必定不会删掉，注意特判。
然后对答案求一个前缀最大值（因为中间可能有空缺），更新原问题答案即可，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e5+5,inf=0x3f3f3f3f;
int n,a[N],ans[N],res[N],sz;
char str[N];
vector<int> vec;
int sv[N];
struct Node{
int pos,val;
bool operator <(const Node &r)const{return val>r.val;}
};
priority_queue<Node> q;
int ppcnt(int x){
int res=0;
while(x){
x-=x&-x;
++res;
}
return res;
}
int pre[N],nxt[N];
int suf[N];
signed main(){
n=read();
scanf(" %s",str+1);
forup(i,1,n){
a[i]=(str[i]=='1');
}
int nw=1;
forup(i,2,n){
if(a[i]==a[i-1]){
++nw;
}else{
vec.push_back(nw);
nw=1;
}
}
vec.push_back(nw);
sz=vec.size();
forup(Case,0,3){// (2)!
while(q.size()) q.pop();
int cnt=ppcnt(Case),nw=vec[Case&1]+vec[sz-1-((Case>>1)&1)];
mem(sv,-1);
forup(j,1+(Case&1),sz-2-((Case>>1)&1)){
sv[j]=vec[j];
q.push(Node{j,sv[j]});
nxt[j]=j+1;pre[j]=j-1;
nw+=vec[j];
}
pre[1+(Case&1)]=nxt[sz-2-((Case>>1)&1)]=0;
res[sz-cnt]=max(res[sz-cnt],nw);
while(sz-cnt>=3){
while(q.size()&&sv[q.top().pos]!=q.top().val) q.pop();
Node u=q.top();q.pop();
nw-=u.val;
if(pre[u.pos]==0){
sv[nxt[u.pos]]=sv[u.pos]=-1;
cnt+=2;
pre[nxt[nxt[u.pos]]]=0;
}else if(nxt[u.pos]==0){
sv[pre[u.pos]]=sv[u.pos]=-1;
cnt+=2;
nxt[pre[pre[u.pos]]]=0;
}else{
sv[pre[u.pos]]+=sv[nxt[u.pos]]-u.val;
q.push(Node{pre[u.pos],sv[pre[u.pos]]});
sv[u.pos]=sv[nxt[u.pos]]=-1;
cnt+=2;
int L=pre[u.pos],R=nxt[nxt[u.pos]];
nxt[L]=R;pre[R]=L;
}
res[sz-cnt]=max(res[sz-cnt],nw);
}
}
fordown(i,n,1){// (1)!
suf[i]=suf[i+1]+a[i];
}
ans[1]=suf[1];
int ss=0;
forup(i,1,n){
ss+=(a[i]==0);
ans[1]=max(ans[1],ss+suf[i+1]);
}
forup(i,2,n){
nw=max(nw,res[i+1]);
ans[i]=nw;
}
forup(i,1,n){
printf("%d ",ans[i]);
}
}
- 暴力计算 $k=1$ 的答案。
- 分类讨论边界删不删掉。
T3
本场考试最难题。
设原序列为 $S$，分出来的两个序列为 $A,B$，$P(S)$ 表示 $S$ 序列中前缀最大值集合，$Q(S)=S-P(S)$。
首先，由于要求字典序最小的序列，我们可以考虑从前往后贪心地，能填 $0$ 就填 $0$，否则填 $1$。换句话说，我们希望求出在确定某一前缀后，后面是否存在某种分配方式使得 $A,B$ 序列中前缀最大值的个数相等。
首先可以想到设 $f_{i,a,b,s}$ 表示考虑后缀 $S_{i\sim n}$，$A$ 的下一个前缀最大值为 $a$，$B$ 的下一个前缀最大值为 $b$，$|P(A')-P(B')|=s$ 的后缀方案是否存在，这个可以很简单地 $O(n^4)$ 求出。但是很不好优化。考虑寻找性质。
容易发现，$P(A)\cup P(B)\supseteq P(S)$，这个比较显然，因为若 $S_i$ 为前缀最大值，无论怎么分，你显然不可能在 $S_{1\sim i-1}$ 之间找到任何一个大于 $S_i$ 的让它变成不是前缀最大值。那么我们其实更关心 $Q(S)$ 在 $P(A),P(B)$ 中的部分。
而我们又可以发现，必定可以构造出解使得 $Q(S)$ 仅与 $P(A),P(B)$ 其中之一（或者两者都不）有交。考虑若 $u,v\in Q(S),u\in P(A),v\in P(B)$，那么假如把 $u$ 放到 $B$ 中，$v$ 放到 $A$ 中，会使得 $u\in Q(A),v\in Q(B)$（因为 $S$ 中 $u$ 前面必定存在大于 $u$ 数，且被分到 $B$ 中了，$v$ 同理），$|P(A)-P(B)|$ 的值没变，但是两边的 $P$ 与 $Q(S)$ 的交都减小了 $1$，最终必定能使得其中一边与 $Q(S)$ 完全无交。
另外值得注意的是，我们只用这样的构造（指只有至多一个 $P$ 与 $Q(S)$ 有交）来判断后缀是否有解，并不影响答案的构造。（但是有趣的是如果就按这样构造答案仍能通过 CatOJ 以及 AtCoder 原题所有数据，但我不会证啊。等个有缘人）
因为上面的结论，若钦定 $P(A')\cap Q(S)=\varnothing$ 显然有 $|P(A')|+c_A=|SP(B')|+|SQ(B')|+c_B$，其中 $A',B'$ 表示当前后缀，$c_A,c_b$ 表示前面已有的前缀最大值个数，$SP(B')$ 表示 $P(B')\cap P(S)$，$SQ(B')$ 表示 $P(B')\cap Q(S)$。
然后移一下项，能得到 $c_A+c_B+|P(A')|+|SP(B')|=c_A+c_B+|P(S')|=2|SP(B')|+|SQ(B')|$。
容易发现 $c_a+c_b+|P(S')|$ 是已知的，也就是说只要能凑出 $2|SP(B')|+|SQ(B')|$ 等于某已知量就说明后缀有解。令 $x=|SP(B')|,y=|SQ(B')|$。
另外，容易发现若能凑出 $2x+y$，那么也能凑出 $2(x-1)+y$，因为上面的那个式子左边和 $A$ 完全没有关系，你可以吧 $SP(B')$ 里面的东西换到 $P(A')$ 里面，而如果 $x=0$，那么 $SQ(B')$ 中所有东西放到 $A$ 中都不会产生贡献，因为 $P(A)$ 中必定有比它们大的前缀最大值。这说明什么？说明奇偶性相同的数中，小于等于能凑出的最大值的数均可凑出来。
那么这就是一个带权最大上升子序列，可以用线段树维护当前后缀信息。并且由于 $S$ 是一个排列，那么线段树维护区间最大值其实就是可撤回的了（这么说有点抽象，可以看看代码）。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,NN=1<<18,inf=0x3f3f3f3f;
int n,p[N],ip[N],V;
struct SegTree{//这就是 zkw 线段树带给我的自信
int querymax[NN<<1];
void Build(){
mem(querymax,0xc0);
}
void Update(int P,int X){
querymax[P+NN]=X;
for(int i=(P+NN)>>1;i;i>>=1){
querymax[i]=max(querymax[i<<1],querymax[i<<1|1]);
}
}
int Query(int L,int R){
int res=-inf;
for(L+=NN-1,R+=NN+1;L^R^1;L>>=1,R>>=1){
if(!(L&1)) res=max(res,querymax[L^1]);
if( R&1 ) res=max(res,querymax[R^1]);
}
return res;
}
};
SegTree t[2];
int ans[N];
bool check(int ca,int cb,int p){
int kk=ca-cb+V;
return kk>=0&&kk<=t[kk&1].Query(p,n+1);
}
signed main(){
n=read();
int mx=0;
forup(i,1,n){
p[i]=read();
if(p[i]>mx){
mx=p[i];
ip[i]=1;
++V;
}
}
t[0].Build();t[1].Build();
t[0].Update(n+1,0);
fordown(i,n,1){
int r1=t[1].Query(p[i],n+1),r0=t[0].Query(p[i],n+1);
if(ip[i]){
t[1].Update(p[i],r1+2);
t[0].Update(p[i],r0+2);
}else{
t[1].Update(p[i],r0+1);
t[0].Update(p[i],r1+1);
}
}
if(!check(0,0,0)){
puts("-1");
return 0;
}
int ma=0,mb=0,ca=0,cb=0;
forup(i,1,n){
if(ip[i]) --V;
t[0].Update(p[i],-inf);
t[1].Update(p[i],-inf);
if(check(ca+(p[i]>ma),cb,mb)||check(cb,ca+(p[i]>ma),max(ma,p[i]))){// (1)!
ans[i]=0;
if(p[i]>ma){
ma=p[i];
++ca;
}
}else{
ans[i]=1;
if(p[i]>mb){
mb=p[i];
++cb;
}
}
}
forup(i,1,n){
printf("%d",ans[i]);
}
}
- 注意 $P(A'),P(B')$ 都有可能和 $Q(S)$ 相交。
T4
有彼阳出题人把最简单题放 T4。
要维护的东西线段树可以直接维护。
具体来说，对每个结点维护区间内剩余车辆价值总和，区间内剩余车辆数量，该区间有多少个删除操作无法在区间内部解决。
然后合并的时候，考虑右儿子的删除操作对左儿子的影响，然后递归合并，容易发现每次只会进一个儿子所以复杂度是 $O(\log n)$ 的。
总复杂度 $O(n\log^2 n)$，具体如何维护见代码，太板了懒得讲。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m;
struct Node{
int tp,v;
};
Node a[N];
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int querysum[N<<2],querycnt[N<<2],queryera[N<<2];
int work(int ct,int l,int r,int id){
if(ct==0){
return querysum[id];
}
if(l==r){
return 0;
}
if(ct<=querycnt[id<<1|1]){
return querysum[id]-querysum[id<<1|1]+work(ct,rson);//(1)!
}else{
return work(ct-querycnt[id<<1|1]+queryera[id<<1|1],lson);
}
}
void PushUp(int id,int l,int r){
if(queryera[id<<1|1]==0){
querysum[id]=querysum[id<<1]+querysum[id<<1|1];
querycnt[id]=querycnt[id<<1]+querycnt[id<<1|1];
queryera[id]=queryera[id<<1];
}else if(queryera[id<<1|1]<=querycnt[id<<1]){
querysum[id]=querysum[id<<1|1]+work(queryera[id<<1|1],lson);
querycnt[id]=querycnt[id<<1|1]+querycnt[id<<1]-queryera[id<<1|1];
queryera[id]=queryera[id<<1];
}else{
querysum[id]=querysum[id<<1|1];
querycnt[id]=querycnt[id<<1|1];
queryera[id]=queryera[id<<1]+queryera[id<<1|1]-querycnt[id<<1];
}
}
void Update(int P,Node X,int l=1,int r=n,int id=1){
if(l==r){
a[P]=X;
if(X.tp==1){
querycnt[id]=querysum[id]=0;
queryera[id]=X.v;
}else{
querycnt[id]=1;
querysum[id]=X.v;
queryera[id]=0;
}
return;
}
if(P<=mid) Update(P,X,lson);
else Update(P,X,rson);
PushUp(id,l,r);
}
int Ask(){
return querysum[1];
}
}mt;
signed main(){
n=read();m=read();
forup(i,1,n){
int tp=read(),v=read();
mt.Update(i,Node{tp,v});
}
forup(Case,1,m){
int x=read(),tp=read(),v=read();
mt.Update(x,Node{tp,v});
printf("%d\n",mt.Ask());
}
}
- 注意
querysum[id]-querysum[id<<1|1]才能得到左儿子对当前结点实际的贡献。