2025CSP-S模拟赛64
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 50 | 0 | 0 | - | 50 | 7/7 |
挂 155pts，挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂挂。
意难平，遂写场上做法。
A. 小 Z 爱计数
首先按照时间排序。对于两个数对 \((a,b)\) 和 \((a',b')\)，令 \(a<a'\)，则合法当且仅当满足一下条件之一：
- 有归零操作，\(|b'|+1\le a'-a\)
- 无归零操作，\(|b-b'|\le a'-a\land a'-a-|b-b'|\equiv0\pmod2\)
注意 \((a_1,b_1)\) 需要与 \((0,0)\) 判断。怒挂 50pts。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int T,n,m;
struct node{int t,v;node(int t=0,int v=0):t(t),v(v){}il bool operator<(const node &x)const{return t<x.t;}
}a[maxn];
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){cin>>m>>n;for(int i=1;i<=n;i++){cin>>a[i].t>>a[i].v;}a[++n]=node();sort(a+1,a+n+1);for(int i=1;i<n;i++){int x=a[i].v,y=a[i+1].v,z=a[i+1].t-a[i].t;if(abs(y)+1<=z||abs(x-y)<=z&&(z-abs(x-y))%2==0);else{cout<<"No\n";goto togo;}}cout<<"Yes\n";togo:;}return 0;
}
}
int main(){return asbt::main();}
B. 小 Z 爱划分
首先考虑一个 \(O(n^2)\) 的 DP：设 \(f_i\) 表示 \(1\) 到 \(i\) 的所有划分的和，于是有 \(f_i=\sum_{j=0}^{i-1}f_j\times(pre_i\oplus pre_j)^2\)。能拿 20pts。
对于 \(a\le255\) 的部分分，注意到值域很小，因此把所有 \(pre_j\) 全都插入字典树，在叶子节点上累加答案即可。时间复杂度 \(O(nV)\)，20pts。
场上只有 T2 需要 freopen，我直接没看见，怒挂 40pts。
正解考虑对每两位计算答案，因为 \((c_1+c_2+\dots+c_k)^2=\sum_{i=1}^{k}\sum_{j=1}^{k}c_ic_j\)，所以对于第 \(x\) 位和第 \(y\) 位，\(f_j\) 能对 \(f_i\) 产生贡献当且仅当这两位都不相同，贡献为 \(f_j\times2^{x+y}\)。于是记 \(sum_{j,x,k,y}\) 表示 \(pre\) 的第 \(j\) 位为 \(x\)，第 \(k\) 位为 \(y\) 的 \(f\) 之和即可线性对数方完成。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5,mod=1e9+7;
il int pls(int x,int y){return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){x=pls(x,y);
}
il int mns(int x,int y){return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){x=mns(x,y);
}
int T,n,a[maxn],f[maxn],sum[37][2][37][2],_2[67];
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;_2[0]=1;for(int i=1;i<=60;i++){_2[i]=pls(_2[i-1],_2[i-1]);}while(T--){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i]^=a[i-1];}f[0]=1;memset(sum,0,sizeof(sum));for(int i=0;i<=30;i++){for(int j=0;j<=30;j++){sum[i][0][j][0]=1;}}for(int i=1;i<=n;i++){f[i]=0;for(int j=0;j<=30;j++){for(int k=0;k<=30;k++){int x=a[i]>>j&1,y=a[i]>>k&1;f[i]=(sum[j][x^1][k][y^1]*1ll*_2[j+k]+f[i])%mod;}}for(int j=0;j<=30;j++){for(int k=0;k<=30;k++){int x=a[i]>>j&1,y=a[i]>>k&1;add(sum[j][x][k][y],f[i]);}}}cout<<f[n]<<'\n';}return 0;
}
}
int main(){return asbt::main();}
C. 小 Z 爱优化
首先考虑值域较小的部分分，考虑可行性 DP，设 \(f_{i,j,k}\) 表示考虑了 \(1\) 到 \(i\)，最大值为 \(j\)，最小值为 \(k\) 是否可行。假设现在加入了 \(t\)，前面的最大值为 \(j\)，于是 \(f_{i,\max(j,t)}\) 的 01 序列可以或上 \(f_{i-1/i-2,j}\) 的第 \(1\) 到 \(t\) 位，然后如果 \(f_{i-1/i-2,j}\) 的第 \(t+1\) 到 \(V\) 位有 \(1\) 那么 \(f_{i,\max(j,t),t}\leftarrow1\)。能拿 20pts。
在这个做法的基础上离散化一下能再拿 \(n\le30\) 的 20pts。bitset 优化一下能拿 \(n\le1000\) 的 25pts。
卡空间失败，怒挂 65pts。
考虑正解。当前这一坨东西已然难以优化，不妨换个思路（
枚举最小值 \(c\)，强制要求所有组都 \(\ge c\)。设 \(f_i\) 表示考虑 \(1\) 到 \(i\)，最大值最小为多少。于是有转移：
\[f_i=\min(\max(f_{i-1},a_i),\max(f_{i-2},a_i+a_{i-1}))
\]
当然 \(a_i\ge c\) 才能进行第一种转移，\(a_i+a_{i-1}\ge c\) 才能进行第二种转移。这东西写成矩阵是满足结合律的，于是考虑 DDP，有：
\[\begin{bmatrix}
f_i&f_{i-1}
\end{bmatrix}
=\begin{bmatrix}
f_{i-1}&f_{i-2}
\end{bmatrix}
\times\begin{bmatrix}
a_i&0\\
a_i+a_{i-1}&+\infty
\end{bmatrix}
\]
用线段树维护，\(c\) 变化时将对应位置的矩阵更改一下即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=2e5+5,inf=1e18;
int T,n,a[maxn];
struct node{int val,pos;node(int val=0,int pos=0):val(val),pos(pos){}il bool operator<(const node &x)const{return val<x.val||val==x.val&&pos<x.pos;}
}b[maxn<<1];
struct juz{int a[2][2];il int*operator[](int x){return a[x];}il juz operator*(juz x)const{juz res;for(int i:{0,1}){for(int j:{0,1}){res[i][j]=min(max(a[i][0],x[0][j]),max(a[i][1],x[1][j]));}}return res;}
}tr[maxn<<2];
il void pushup(int id){tr[id]=tr[lid]*tr[rid];
}
il void build(int id,int l,int r){if(l==r){tr[id][0][0]=a[l],tr[id][0][1]=0;tr[id][1][0]=a[l]+a[l-1],tr[id][1][1]=inf;return ;}int mid=(l+r)>>1;build(lid,l,mid);build(rid,mid+1,r);pushup(id);
}
il void upd(int id,int l,int r,int p,int v){if(l==r){if(tr[id][0][0]==v){tr[id][0][0]=inf;}if(tr[id][1][0]==v){tr[id][1][0]=inf;}return ;}int mid=(l+r)>>1;if(p<=mid){upd(lid,l,mid,p,v);}else{upd(rid,mid+1,r,p,v);}pushup(id);
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){cin>>n;int tot=0;for(int i=1;i<=n;i++){cin>>a[i];b[++tot]=node(a[i],i);b[++tot]=node(a[i]+a[i-1],i);}sort(b+1,b+tot+1);build(1,1,n);int ans=min(tr[1][0][0],tr[1][1][0])-b[1].val;
// cout<<b[1].val<<' '<<min(tr[1][0][0],tr[1][1][0])<<'\n';for(int i=1;i<tot;i++){upd(1,1,n,b[i].pos,b[i].val);
// cout<<"P "<<b[i].pos<<' '<<b[i].val<<'\n';if(b[i].val!=b[i+1].val){ans=min(ans,min(tr[1][0][0],tr[1][1][0])-b[i+1].val);
// cout<<"Q "<<b[i+1].val<<' '<<min(tr[1][0][0],tr[1][1][0])<<'\n';}}cout<<ans<<'\n';}return 0;
}
}
signed main(){return asbt::main();}
D. 小 Z 爱考试
容易发现有些点必然会加上 \(w_i\)，有些点必然不会加。具体地，可将点分为三类：
- \(a_i<a_{b_i}\)，必然加上 \(w_i\)，称为一类点
- \(a_i\ge a_{b_i}+w_{b_i}\)，必然不会加上 \(w_i\)，称为二类点
- \(a_{b_i}\le a_i<a_{b_i}+w_{b_i}\)，需要通过 \(b_i\) 确定加不加，称为三类点
于是我们连边 \(i\to b_i\)，得到一个基环树森林。询问 \(u\) 点的答案时，就不断在树上跑，直到跑到一个一类点或二类点停下。情况分为三类：
- 遇到了一类点。设一路上跑过的点为 \(p_1,p_2,\dots,p_k\)，那么只有这些点以 \(p_k,p_{k-1},\dots,p_1\) 的顺序发生时答案为 \(a_u+w_u\)。这种情况的概率为 \(\frac{{n\choose k}(n-k)!}{n!}=\frac{1}{k!}\)。
- 遇到了二类点。因为二类点不会加，所以这一路上的点都不会加。
- 跑到了环里，全是三类点，还是不会加。
于是我们只需要求在基环树上从 \(u\) 开始跑到的第一个一类或二类点即可。不妨将它们统称为黑点，三类点为白点。由于需要动态修改，考虑用数据结构维护。将基环树分为树和环两部分。首先是树上的部分，考虑重链剖分，对每个重链维护一个存储所有黑点的 set，我们要求的就是在这条链上第一个深度比 \(u\) 小的黑点，若没有则一直往上跳到根。
如果子树上没有，那么就在环上找。还是给环开一个 set，给环上的点标号，我们要找的就是第一个编号大于 \(u\) 的黑点。可能要绕一圈绕回来，断环为链，将整个环存两遍即可。
对于修改，只会影响 \(u\) 和所有 \(b_i=u\) 的 \(i\) 的类型。\(i\) 只有 \(3\) 个，暴力修改即可。时间复杂度 \(O(n\log^2n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define lwrb lower_bound
#define uprb upper_bound
using namespace std;
namespace asbt{
const int maxn=2e5+5,mod=1e9+7;
int T,n,m,a[maxn],b[maxn],c[maxn],d[maxn];
int cid[maxn],ccnt,crn[maxn],chid[maxn],chnt;
int dep[maxn],sz[maxn],hes[maxn],top[maxn];
int inv[maxn],len[maxn],fa[maxn];
bool bla[maxn];
vector<int> e[maxn];
queue<int> q;
struct node{int k,u;node(int k=0,int u=0):k(k),u(u){}il bool operator<(const node &x)const{return k<x.k;}
};
set<node> cir[maxn],chn[maxn];
il void dfs1(int u){sz[u]=1;int mxs=0;for(int v:e[u]){if(d[v]){continue;}dep[v]=dep[u]+1;fa[v]=u;dfs1(v);sz[u]+=sz[v];if(mxs<sz[v]){mxs=sz[v],hes[u]=v;}}
}
il void dfs2(int u){if(!chid[u]){chid[u]=++chnt;top[u]=u;}if(bla[u]){chn[chid[u]].insert(node(dep[u],u));}if(hes[u]){chid[hes[u]]=chid[u];top[hes[u]]=top[u];dfs2(hes[u]);}for(int v:e[u]){if(d[v]||v==hes[u]){continue;}dfs2(v);}
}
il pii query(int u){int uu=u;while(dep[u]){auto it=chn[chid[u]].uprb(node(dep[u],u));if(it==chn[chid[u]].begin()){if(dep[top[u]]){u=fa[top[u]];}else{u=top[u];}}else{it=prev(it);return mp(dep[uu]-it->k+1,it->u);}}auto it=cir[cid[u]].lwrb(node(crn[u],u));if(it==cir[cid[u]].end()){return mp(-1,-1);}else{return mp(it->k-crn[u]+dep[uu]+1,it->u);}
}
il void solve(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i]>>b[i]>>c[i];d[b[i]]++;e[b[i]].pb(i);}for(int i=1;i<=n;i++){if(d[i]==0){q.push(i);}if(a[i]<a[b[i]]||a[i]>=a[b[i]]+c[b[i]]){bla[i]=1;}}while(q.size()){int u=q.front();q.pop();if(--d[b[u]]==0){q.push(b[u]);}}for(int i=1;i<=n;i++){if(d[i]&&!cid[i]){ccnt++;int u=i;do{cid[u]=ccnt,crn[u]=++len[ccnt];if(bla[u]){cir[ccnt].insert(node(crn[u],u));}dfs1(u),dfs2(u);u=b[u];}while(u!=i);do{if(bla[u]){cir[ccnt].insert(node(len[ccnt]+crn[u],u));}u=b[u];}while(u!=i);}}
// for(int i=1;i<=n;i++){
// cout<<i<<' '<<cid[i]<<' '<<crn[i]<<' '<<chid[i]<<' '<<dep[i]<<'\n';
// }while(m--){int opt,u,cc;cin>>opt>>u;if(opt==3){pii x=query(u);int v=x.sec,len=x.fir;
// cout<<v<<' '<<len<<'\n';if(~v&&a[v]<a[b[v]]){cout<<(inv[len]*1ll*(a[u]+c[u])+(1-inv[len]+mod)*1ll*a[u])%mod<<'\n';}else{cout<<a[u]<<'\n';}}else{cin>>cc;(opt==1?a:c)[u]=cc;bool t=a[u]<a[b[u]]||a[u]>=a[b[u]]+c[b[u]];
// cout<<bla[u]<<' '<<t<<'\n';if(bla[u]&&!t){chn[chid[u]].erase(node(dep[u],u));if(cid[u]){cir[cid[u]].erase(node(crn[u],u));cir[cid[u]].erase(node(len[cid[u]]+crn[u],u));}}else if(!bla[u]&&t){
// puts("666");chn[chid[u]].insert(node(dep[u],u));if(cid[u]){cir[cid[u]].insert(node(crn[u],u));cir[cid[u]].insert(node(len[cid[u]]+crn[u],u));}}bla[u]=t;for(int v:e[u]){bool t=a[v]<a[b[v]]||a[v]>=a[b[v]]+c[b[v]];if(bla[v]&&!t){chn[chid[v]].erase(node(dep[v],v));if(cid[v]){cir[cid[v]].erase(node(crn[v],v));cir[cid[v]].erase(node(len[cid[v]]+crn[v],v));}}else if(!bla[v]&&t){chn[chid[v]].insert(node(dep[v],v));if(cid[v]){cir[cid[v]].insert(node(crn[v],v));cir[cid[v]].insert(node(len[cid[v]]+crn[v],v));}}bla[v]=t;}}}for(int i=1;i<=n;i++){a[i]=b[i]=c[i]=d[i]=0;cid[i]=crn[i]=chid[i]=0;dep[i]=sz[i]=hes[i]=top[i]=0;len[i]=fa[i]=bla[i]=0;e[i].clear();}for(int i=1;i<=ccnt;i++){cir[i].clear();}for(int i=1;i<=chnt;i++){chn[i].clear();}ccnt=chnt=0;
}
int main(){ios::sync_with_stdio(0),cin.tie(0);inv[0]=inv[1]=1;for(int i=2;i<=2e5;i++){inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;}for(int i=2;i<=2e5;i++){inv[i]=inv[i-1]*1ll*inv[i]%mod;}cin>>T;while(T--){solve();}return 0;
}
}
int main(){return asbt::main();}