20231027 B 组模拟赛 题解
前言
T3 非常复杂，可拓展性低，几乎没人改，就不改了。
T1
简单题。容易想到 $O(n^3)$ dp。
具体来说，设状态 $dp_{l,r,k}$ 表示左侧 $[1,l)$，右侧 $(r,n]$ 全拿完了，先手已经在其中拿了 $k$ 个菜，先手是否会赢。由于 $l,r$ 已知我们可以通过奇偶性判断当前是谁的回合。若是先手那么转移就是两个后继状态取或（因为先手肯定会选会赢的那个后继），若是后手转移就是取与（因为他肯定不希望先手赢）。比较简单的记搜。
参考代码
#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=355,inf=0x3f3f3f3f;
int t,n,m,pre[N],suf[N],a[N];
bool dp[N][N][N],vis[N][N][N];
char str[N];
bool solve(int l,int r,int k){
if(k==m) return false;
if(pre[l-1]+suf[r+1]-k==m) return true;
if(vis[l][r][k]) return dp[l][r][k];
vis[l][r][k]=1;
int cnt=l-1+(n-r);
if(cnt&1){
dp[l][r][k]=1;
dp[l][r][k]&=solve(l+1,r,k);
dp[l][r][k]&=solve(l,r-1,k);
}else{
dp[l][r][k]|=solve(l+1,r,k+a[l]);
dp[l][r][k]|=solve(l,r-1,k+a[r]);
}
return dp[l][r][k];
}
signed main(){
t=read();
while(t--){
n=read();m=read();
scanf(" %s",str+1);
forup(i,1,n){
a[i]=(str[i]=='V');
}
pre[0]=suf[n+1]=0;
forup(i,1,n) pre[i]=pre[i-1]+a[i];
fordown(i,n,1) suf[i]=suf[i+1]+a[i];
mem(dp,0);mem(vis,0);
puts(solve(1,n,0)?"yes":"no");
}
}
T2
这道题我记得赛时想了个鬼畜做法。然后寄了。
首先如果不看操作三那么就是一个线段树模板二。考虑操作三如何处理。
其实很简单，容易发现若封锁区间对应的 $\log n$ 个结点，那么先把这些边断开。除去断开的部分后，它们会影响的部分恰好是递归寻找它们途中的那些结点。也就是说操作是可以在线段树的 PushUp 中完成的。注意断开后仍在封锁和查询操作时需要进入对应结点。
那么我们可以把它拆成“封锁”和“解封”两个操作。
为了维护区间加，需要记区间内没被封锁的点数。为了维护区间乘需要维护区间内没被封锁的总和。注意查询时被封锁区间仍然会产生贡献。
然后考虑一些实现细节。首先根据懒标记的理解，它是一些修改的堆积。那么封锁时不会出问题吗？其实不会出问题，因为你封锁和解封时都会提前下传多余的懒标记，所以不会出现封锁期间的懒标记被传入封锁结点或者该下传的没有下传的情况。
然后是如何维护没被封锁的点数和没被封锁的总和。由于封锁会重复进行，那么如果一个结点不是叶子，它的子孙结点可能在它被封锁期间封锁了。那么解锁的时候从子孙结点获得新的信息即可。注意特判叶子结点。
参考代码
#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;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#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,mod=1e9+7;
int n,m,a[N];
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int addmark[N<<2],multmark[N<<2],Tm[N<<2],querysum[N<<2],querysuml[N<<2],querycnt[N<<2];
void PushUp(int id){
querysum[id]=(querysum[id<<1]+querysum[id<<1|1])%mod;
querysuml[id]=(querysuml[id<<1]+querysuml[id<<1|1])%mod;
if(Tm[id]){
(querysuml[id]+=querysum[id])%=mod;
querysum[id]=0;
}
querycnt[id]=0;
if(!Tm[id<<1] ) querycnt[id]+=querycnt[id<<1];
if(!Tm[id<<1|1]) querycnt[id]+=querycnt[id<<1|1];
}
void Build(int l=1,int r=n,int id=1){
multmark[id]=1;
if(l==r){
querysum[id]=a[l];
querycnt[id]=1;
return;
}
Build(lson);Build(rson);
PushUp(id);
}
void Modify(int id,int ADD,int MUL){
querysum[id]=(1ll*querysum[id]*MUL%mod+1ll*ADD*querycnt[id]%mod)%mod;
multmark[id]=1ll*multmark[id]*MUL%mod;
addmark[id]=(1ll*addmark[id]*MUL%mod+ADD)%mod;
}
void PushDown(int id){
if(addmark[id]==0&&multmark[id]==1) return;
if(!Tm[id<<1] ) Modify(id<<1 ,addmark[id],multmark[id]);
if(!Tm[id<<1|1]) Modify(id<<1|1,addmark[id],multmark[id]);
addmark[id]=0;multmark[id]=1;
}
void Update(int L,int R,int ADD,int MUL,int l=1,int r=n,int id=1){
if(Tm[id]) return;
if(l!=r) PushDown(id);
if(L<=l&&r<=R){
Modify(id,ADD,MUL);
return;
}
if(L<=mid) Update(L,R,ADD,MUL,lson);
if(mid< R) Update(L,R,ADD,MUL,rson);
PushUp(id);
}
void Blockade(int L,int R,int T,int X,int l=1,int r=n,int id=1){
if(l!=r) PushDown(id);
if(L<=l&&r<=R){
if(X){
if(!Tm[id]){
(querysuml[id]+=querysum[id])%=mod;
querysum[id]=0;
}
Tm[id]=max(Tm[id],T);
}else if(Tm[id]==T){
if(l!=r){
querysum[id]=(querysum[id<<1]+querysum[id<<1|1])%mod;
querysuml[id]=(querysuml[id<<1]+querysuml[id<<1|1])%mod;
}else{
querysum[id]=querysuml[id];
querysuml[id]=0;
}
Tm[id]=0;
}
return;
}
if(L<=mid) Blockade(L,R,T,X,lson);
if(mid< R) Blockade(L,R,T,X,rson);
PushUp(id);
}
int Query(int L,int R,int l=1,int r=n,int id=1){
if(l!=r) PushDown(id);
if(L<=l&&r<=R){
return (querysum[id]+querysuml[id])%mod;
}
int res=0;
if(L<=mid) (res+=Query(L,R,lson))%=mod;
if(mid< R) (res+=Query(L,R,rson))%=mod;
return res;
}
void Print(int l=1,int r=n,int id=1){
printf("%d %d %d %d|\n",l,r,querysum[id],querysuml[id]);
if(l==r) return;
Print(lson);Print(rson);
}
}mt;
vector<pii> svf[N];
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
}
mt.Build();
forup(Case,1,m){
int op=read(),l=read(),r=read();
if(op==1){
int x=read();
mt.Update(l,r,x,1);
}else if(op==2){
int x=read();
mt.Update(l,r,0,x);
}else if(op==3){
int x=read();
mt.Blockade(l,r,Case+x,1);
if(Case+x+1<=m) svf[Case+x].push_back(mkp(l,r));
}else{
printf("%d\n",mt.Query(l,r));
}
for(auto i:svf[Case]){
mt.Blockade(i.fi,i.se,Case,0);
}
}
}
T4
好题。
这一类“求前 $k$ 优解”的问题有一个固定的套路。
这种问题的做法一般基于一种类似 Dijkstra 的堆贪心。
记状态集合为 $T$，每个状态 $i\in T$ 的权值为 $val(i)$。
我们考虑对于每一个状态 $i$，建立形如 $i\to trans(i)$ 的转移。
其中 $trans(i)$ 为常数个可以通过对 $i$ 进行常数次调整得到的状态，并保证 $val(i)<val(trans(i))$。并且，额外要求若 $j\in trans(i)，\nexists i'\ne i,j\in trans(i')$。即每个状态只能从一个状态转移过来。
容易发现为了满足这个条件，必定要找到一个初始状态 $I$，使得 $val(I)$ 最小。且可以以它为起点到达所有合法状态。
容易发现这样的转移构成了一棵外向树的形式，那么我们就可以建一个堆，初始只有根结点，然后每次取出堆顶 $t$ 加入 $trans(t)$。就能在 $O(k\log k)$ 的时间内求解。
所以这类问题的重点通常在于如何构建唯一的不漏转移，最基本的一种考量是贪心地扩展代价差尽量小的，再有就是考虑进行一些钦定来去重之类的。
另外，此处状态的定义和 DP 不同，两个长得一样的状态可能是本质不同的。此处定义状态只是为了方便 $trans$ 的设计，你或许可以在后文看到例子。
首先从简化版本的问题开始考虑如何构建 $trans$：
- 只有 $1$ 类商品，必须选择恰好 $1$ 个。
这个太简单了，先按价格排序，设一个状态为 $x$，$trans(x)$ 就是 $\begin{Bmatrix}x+1\end{Bmatrix}$，初始状态即 $x=1$。
- 只有 $1$ 类商品，必须选择恰好 $k$ 个（可以把 $k$ 视作常数）。
仍按价格排序，一个简单的想法是记一个状态 $X=(x_1,x_2,x_3\dots,x_k)$ 表示选择的 $k$ 个商品分别是什么。并且钦定 $x_1< x_2< x_3\dots <x_k$。初始状态即 $I=(1,2,3\dots k)$，$trans$ 就是把每个 $x_i$ 分别 $+1$，注意不要越过 $x_{i+1}$。
但是这样有个问题，显然会算重。比如当 $k=2$，$(2,4)$ 状态可以从 $(1,4)$ 和 $(2,3)$ 两种状态转移过来。考虑通过某种钦定使得其中一种转移失效。
对于 $k=2$，容易想到可以在动了 $x_1$ 之后就不动 $x_2$，即对于每个状态额外记一个 $p$，$(x_1,x_2,p)$ 表示当前 $x_p$ 在动。初始状态就是 $(1,2,2)$，然后对于 $p=2$，$trans$ 是 $(x_1,x_2+1,2)$ 和 $(x_1+1,x_2,1)$（注意这里要先移动 $x_1$，因为 $(x_1,x_2,1)$ 和 $(x_1,x_2,2)$ 其实是本质相同的）。注意 $x_1$ 不能越过 $x_2$。容易发现这样就不重不漏了。
然后推广到一般情况。类似于 $k=2$，于每个状态，都有一个前缀 $x_1=1,x_2=2\dots,x_p=p$（$p$ 可以为 $0$），然后 $x_{p+1}$ 正在移动中，$x_{p+2}\sim x_{k}$ 已经固定。在 $k=2$ 的情况要注意不能越过 $x_2$，那么这里就要注意不能越过 $x_{p+2}$。容易想到设状态 $(p,y,z)$ 表示前缀 $1\sim p$ 没动过，当前正在动 $x_{p+1}$，且 $x_{p+1}=y$，$x_{p+2}=z$ 的代价。容易发现本质不同的状态可能具有相同的表示，但是刚刚说过，我们只关心 $trans$ 的构造，所以不用担心。然后 $trans$ 就是 $(p,y+1,z)$ 和 $(p,p+1,y)$。初始状态是 $(k-1,k,\infty)$，注意边界条件。
- 只有 $1$ 类商品，需要选择 $[l,r]$ 个。
其实很简单，把初始状态设为 $(l-1,l,\infty)$，然后给满足 $y=p+1,z=\infty$ 的状态加一个 $(p+1,y+1,\infty)$ 的 $trans$ 即可，其余部分和情况 $2$ 类似。
- 有 $m$ 类商品，每种需要选择 $1$ 个。
依旧对每一类按价格排序，一个状态 $X=(x_1,x_2,x_3\dots x_m)$。容易想到初始状态就是每种选第一个，但是 $trans$ 不太好设计。依旧考虑先简单设计再用钦定的方式去重。
一个容易想到的简单设计就是每个种类选下一个，但是显然会算重。那么仿照之前的，可以钦定一个指针 $p$，每次只改 $p$ 或者把 $p$ 移向下一个。这样就不会算重了，而且 $trans$ 的大小也变小，更容易转移了。
但是还有个问题，我们的状态是 $(X,p)$，容易发现 $X$ 相同，$p$ 不同的两状态是本质相同的。如何解决呢？除初始状态外，我们可以钦定 $x_p>1$，然后新增一个 $trans$ 为 $(x_p-1,x_{p+1}+1,p+1)$（这里省略了其它东西，但应该能看懂），这样就不会有问题了。
- 有 $m$ 类商品，每种需要选择 $[l_i,r_i]$ 个。
这就是原问题了。
考虑对每一类商品进行一个 $1\to 3$ 的转化，然后就做完了。
为什么呢？考虑你可以把每一种商品看做一个黑盒，你每次只需要找到“下一小的方案”，并不关心它具体是怎么得到的。
每次对每一个商品的转化是 $O(\log k)$ 的，总复杂度大概是 $O(k\log^2k)$，这个上界貌似是卡不到的，因为可以对每一类商品记忆化已经求出来的前几小，大部分转移就是单 $\log$ 的。另外注意边界问题。
参考代码
#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=2e5+5,inf=0x3f3f3f3f;
i64 n,m,t,x[N],y[N],ans[N],aad;
vector<i64> cs[N],sv[N],seq;
struct Node{
i64 x,y,z,val,c;
Node(i64 _x=0,i64 _y=0,i64 _z=0,i64 _val=0,i64 _c=0):x(_x),y(_y),z(_z),val(_val),c(_c){}
bool operator <(const Node &r)const{return val>r.val;}
};
priority_queue<Node> q[N];
struct node{
i64 p,x,val;
node(i64 _p=0,i64 _x=0,i64 _val=0):p(_p),x(_x),val(_val){}
bool operator <(const node &r)const{return val>r.val;}
};
priority_queue<node> nq;
void nxt(priority_queue<Node> &q,Node nw){
if(nw.y==nw.x+1&&nw.z==inf&&nw.y<(i64)cs[nw.c].size()&&nw.y<y[nw.c]){
q.push(Node{nw.x+1,nw.y+1,inf,nw.val+cs[nw.c][nw.y],nw.c});
}
if(nw.x!=-1&&nw.y<(i64)cs[nw.c].size()&&nw.y<nw.z-1){
q.push(Node{nw.x,nw.y+1,nw.z,nw.val-cs[nw.c][nw.y-1]+cs[nw.c][nw.y],nw.c});
}
if(nw.x>0&&nw.x+1<nw.y){
q.push(Node{nw.x-1,nw.x+1,nw.y,nw.val-cs[nw.c][nw.x-1]+cs[nw.c][nw.x],nw.c});
}
}
signed main(){
n=read();m=read();t=read();
forup(i,1,n){
i64 a=read(),c=read();
cs[a].push_back(c);
}
forup(i,1,m){
sort(cs[i].begin(),cs[i].end());
x[i]=read();y[i]=read();
if((i64)cs[i].size()<x[i]){
forup(i,1,t){
puts("-1");
}
return 0;
}
i64 val=0;
forup(j,0,x[i]-1){
val+=cs[i][j];
}
sv[i].push_back(val);
Node nw=Node{x[i]-1,x[i],inf,val,i};
nxt(q[i],nw);
if(!q[i].size()){
aad+=sv[i][0];
continue;
}
nw=q[i].top();q[i].pop();
sv[i].push_back(nw.val);
nxt(q[i],nw);
seq.push_back(i);
}
sort(seq.begin(),seq.end(),[&](i64 a,i64 b){
return sv[a][1]-sv[a][0]<sv[b][1]-sv[b][0];
});
node nw=node{0,0,0};
for(auto i:seq){
nw.val+=sv[i][0];
}
nq.push(nw);
i64 cnt=0;
while(cnt<t&&nq.size()){
++cnt;
node u=nq.top();nq.pop();
ans[cnt]=u.val;
i64 pp=seq[u.p];
if(u.x<(i64)sv[pp].size()-1||q[pp].size()){
if(u.x==(i64)sv[pp].size()-1){
Node nw=q[pp].top();q[pp].pop();
sv[pp].push_back(nw.val);
nxt(q[pp],nw);
}
nq.push(node{u.p,u.x+1,u.val+sv[pp][u.x+1]-sv[pp][u.x]});
}
if(u.p<(i64)seq.size()-1&&u.x>=1){
i64 np=seq[u.p+1];
nq.push(node{u.p+1,1,u.val+sv[np][1]-sv[np][0]});
}
if(u.p<(i64)seq.size()-1&&u.x==1){
i64 np=seq[u.p+1];
nq.push(node{u.p+1,1,u.val-sv[pp][1]+sv[pp][0]-sv[np][0]+sv[np][1]});
}
}
forup(i,1,cnt){
printf("%lld\n",ans[i]+aad);
}
forup(i,cnt+1,t){
puts("-1");
}
}