暑假集训CSP提高模拟 25
组题人： @KafuuChinocpp | @H_Kaguya
\(T1\) P235.可持久化线段树 \(0pts\)
-
标记永久化主席树板子。
点击查看代码
const ll p=998244353; ll a[100010]; struct PDS_SMT { ll root[100010],rt_sum; struct SegmentTree { ll ls,rs,sum,lazy; }tree[100010<<5]; #define lson(rt) tree[rt].ls #define rson(rt) tree[rt].rs ll build_rt() { rt_sum++; return rt_sum; } void build_tree(ll &rt,ll l,ll r) { rt=build_rt(); if(l==r) { tree[rt].sum=a[l]; return; } ll mid=(l+r)/2; build_tree(lson(rt),l,mid); build_tree(rson(rt),mid+1,r); tree[rt].sum=(tree[lson(rt)].sum+tree[rson(rt)].sum)%p; } void update(ll pre,ll &rt,ll l,ll r,ll x,ll y,ll val) { rt=build_rt(); tree[rt]=tree[pre]; tree[rt].sum=(tree[rt].sum+(min(r,y)-max(l,x)+1)*val%p)%p; if(x<=l&&r<=y) { tree[rt].lazy=(tree[rt].lazy+val)%p; return; } ll mid=(l+r)/2; if(x<=mid) { update(lson(pre),lson(rt),l,mid,x,y,val); } if(y>mid) { update(rson(pre),rson(rt),mid+1,r,x,y,val); } } ll query(ll rt,ll l,ll r,ll x,ll y) { if(x<=l&&r<=y) { return tree[rt].sum; } ll mid=(l+r)/2,ans=0; if(x<=mid) { ans=(ans+query(lson(rt),l,mid,x,y))%p; } if(y>mid) { ans=(ans+query(rson(rt),mid+1,r,x,y))%p; } return (ans+tree[rt].lazy*(min(r,y)-max(l,x)+1)%p)%p; } }T; int main() { ll n,m,pd,l,r,x,c_cnt=0,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; } T.build_tree(T.root[0],1,n); for(i=1;i<=m;i++) { cin>>pd; if(pd==1) { cin>>l>>r>>x; c_cnt++; T.update(T.root[c_cnt-1],T.root[c_cnt],1,n,l,r,x); } if(pd==2) { cin>>l>>r; cout<<T.query(T.root[c_cnt],1,n,l,r)<<endl; } if(pd==3) { cin>>x; c_cnt-=x; } } return 0; }
\(T2\) P208.Little Busters ! \(0pts\)
-
Lun边至少属于图中的一个环等价于Lun边连接的两个端点属于一个边双连通分量，Qie边不属于图中的任意环等价于Qie边连接的两个端点不属于一个边双连通分量。 -
部分分
- \(20 \%\) ：枚举每条边保留或不保留，然后 \(Tarjan\) 判断是否合法。
- 另外 \(20 \%\) ：缩完点后只能有一个点否则不满足题意。
- 另外 \(20 \%\) ：直接删成一棵树就行了。
- 随机 \(pts\) ：乱搞。
点击查看代码
struct node { int nxt,to,w,id; }E[200010]; int head[200010],u[200010],v[200010],w[200010],dfn[200010],low[200010],c[200010],vis[200010],tot=0,cnt=0,scc_cnt=0; vector<pair<int,int> >e[200010],ans; stack<int>s; void add(int u,int v,int w,int id) { cnt++; E[cnt].nxt=head[u]; E[cnt].to=v; E[cnt].w=w; E[cnt].id=id; head[u]=cnt; } void tarjan(int x,int fa) { tot++; dfn[x]=low[x]=tot; s.push(x); for(int i=0;i<e[x].size();i++) { if(e[x][i].first!=fa) { if(dfn[e[x][i].first]==0) { tarjan(e[x][i].first,x); low[x]=min(low[x],low[e[x][i].first]); } else { low[x]=min(low[x],dfn[e[x][i].first]); } } } if(dfn[x]==low[x]) { int k; scc_cnt++; do { k=s.top(); s.pop(); c[k]=scc_cnt; }while(k!=x); } } void tarjanE(int x,int fa) { tot++; dfn[x]=low[x]=tot; s.push(x); for(int i=head[x];i!=0;i=E[i].nxt) { if(vis[E[i].id]==0&&E[i].to!=fa) { if(dfn[E[i].to]==0) { tarjanE(E[i].to,x); low[x]=min(low[x],low[E[i].to]); } else { low[x]=min(low[x],dfn[E[i].to]); } } } if(dfn[x]==low[x]) { int k; scc_cnt++; do { k=s.top(); s.pop(); c[k]=scc_cnt; }while(k!=x); } } bool check(int state,int n,int m) { if(__builtin_popcount(state)<n-1) { return false; } scc_cnt=tot=0; ans.clear(); for(int i=1;i<=n;i++) { dfn[i]=low[i]=c[i]=0; e[i].clear(); } while(s.empty()==0) { s.pop(); } for(int i=0;i<=m-1;i++) { if((state>>i)&1) { e[u[i+1]].push_back(make_pair(v[i+1],w[i+1])); e[v[i+1]].push_back(make_pair(u[i+1],w[i+1])); ans.push_back(make_pair(u[i+1],v[i+1])); } } tarjan(1,0); for(int i=1;i<=n;i++) { if(dfn[i]==0) { return false; } } for(int i=1;i<=n;i++) { for(int j=0;j<e[i].size();j++) { if(e[i][j].second==1) { if(c[i]!=c[e[i][j].first]) { return false; } } else { if(c[i]==c[e[i][j].first]) { return false; } } } } return true; } void dfs(int x,int fa) { vis[x]=1; for(int i=0;i<e[x].size();i++) { if(vis[e[x][i].first]==0) { cout<<x<<" "<<e[x][i].first<<endl; dfs(e[x][i].first,x); } } } int main() { int n,m,flag1=1,flag2=1,state,i,j; string pd; cin>>n>>m; for(i=1;i<=m;i++) { cin>>u[i]>>v[i]>>pd; w[i]=(pd=="Lun"); flag1&=(w[i]==1); flag2&=(w[i]==0); } if(flag1==1) { for(i=1;i<=m;i++) { e[u[i]].push_back(make_pair(v[i],w[i])); e[v[i]].push_back(make_pair(u[i],w[i])); } tarjan(1,0); if(scc_cnt==1) { cout<<"YES"<<endl; cout<<m<<endl; for(i=1;i<=m;i++) { cout<<u[i]<<" "<<v[i]<<endl; } } else { cout<<"NO"<<endl; } } else { if(flag2==1) { for(i=1;i<=m;i++) { e[u[i]].push_back(make_pair(v[i],w[i])); e[v[i]].push_back(make_pair(u[i],w[i])); } cout<<"YES"<<endl; cout<<n-1<<endl; dfs(1,0); } else { if(m<=20) { for(state=0;state<=(1<<m)-1;state++) { if(check(state,n,m)==true) { cout<<"YES"<<endl; cout<<ans.size()<<endl; for(i=0;i<ans.size();i++) { cout<<ans[i].first<<" "<<ans[i].second<<endl; } return 0; } } cout<<"NO"<<endl; } else { for(i=1;i<=m;i++) { add(u[i],v[i],w[i],i); add(v[i],u[i],w[i],i); e[u[i]].push_back(make_pair(v[i],w[i])); e[v[i]].push_back(make_pair(u[i],w[i])); } tarjan(1,0); for(int i=1;i<=n;i++) { for(int j=head[i];j!=0;j=E[j].nxt) { if(E[j].w==1) { if(c[j]!=c[E[j].to]) { vis[E[j].id]=1; } } else { if(c[j]!=c[E[j].to]) { vis[E[j].id]=0; } } } } scc_cnt=tot=0; ans.clear(); for(int i=1;i<=n;i++) { dfn[i]=low[i]=c[i]=0; e[i].clear(); } while(s.empty()==0) { s.pop(); } tarjanE(1,0); for(int i=1;i<=n;i++) { if(dfn[i]==0) { cout<<"NO"<<endl; return 0; } } for(int i=1;i<=n;i++) { for(int j=0;j<e[i].size();j++) { if(e[i][j].second==1) { if(c[i]!=c[e[i][j].first]) { cout<<"NO"<<endl; return 0; } } else { if(c[i]==c[e[i][j].first]) { cout<<"NO"<<endl; return 0; } } } } for(i=1;i<=m;i++) { if(vis[i]==0) { ans.push_back(make_pair(u[i],v[i])); } } cout<<"YES"<<endl; cout<<ans.size()<<endl; for(i=0;i<ans.size();i++) { cout<<ans[i].first<<" "<<ans[i].second<<endl; } } } } return 0; }
\(T3\) P220.魔卡少女樱 \(45pts\)
- 部分分
-
\(65pts\) ：设 \(f_{i,j}\) 表示当前处理到 \(i\) 时，且 \(a_{i}=j\) 的合法方案数，状态转移方程为 \(f_{i,j}=\sum\limits_{k=0}^{j-1}[k \not \equiv j \pmod{3}] \times f_{i-1,k}=\sum\limits_{k=0}^{j-1}f_{i-1,k}-\sum\limits_{k=0}^{j-1}[k \equiv j \pmod{3}] \times f_{i-1,k}\) ，边界为 \(f_{1,i}=[i+n-1 \le m]\) 。前缀和优化后时间复杂度为 \(O(nm)\) 。
点击查看代码
const ll p=998244353; int f[2][10000010],sum[5]; int main() { int n,m,ans=0,i,j; cin>>n>>m; if(n-1<=m) { for(i=0;i<=m;i++) { f[1][i]=(i+n-1<=m); } for(i=2;i<=n;i++) { sum[0]=sum[1]=sum[2]=sum[3]=0; for(j=0;j<=m;j++) { f[i&1][j]=(sum[3]-sum[j%3]+p)%p; sum[j%3]=(sum[j%3]+f[(i-1)&1][j])%p; sum[3]=(sum[3]+f[(i-1)&1][j])%p; } } for(i=n-1;i<=m;i++) { ans=(ans+f[n&1][i])%p; } cout<<ans<<endl; } else { cout<<0<<endl; } return 0; }
-
- 正解
\(T4\) P202.声之形 \(5pts\)
- 原题： 2024牛客暑期多校训练营5 K 思
- 部分分
总结
- \(T1\) 因不会算结构体变量空间和提交前没有再编译一遍，挂了 \(100pts\) 。
- \(T2\) 提交前没有再编译一遍，挂了 \(60pts\) 。
- 我再也不相信
C/C++的报错了。。。
- 我再也不相信
- \(T3\) 结束前 \(10 \min\) 前原 \(O(nm^{2})\) 的做法才发现可以前缀和优化，过了小样例后就直接交了，忘删每次 \(O(m)\) 的清空了，挂了 \(25pts\) 。
后记
- \(T1\) 原本在 @H_Kaguya 可持久化数据结构课件里做例题，没想到他和教练会为了检验我们有没有掌握将其放在了 \(T1\) 的位置。而 luogu P4690 [Ynoi2016] 镜中的昆虫 因被出到模拟赛里作为 \(T4\) ，他干脆没讲，只透露了会有一道珂朵莉树的题在模拟赛里等着我们，详见 暑假集训CSP提高模拟20 T4 P128. 穗 。
- \(T3\) 在前几天于题库中曾被公开过，组题人貌似泄题了也没管。