暑假集训CSP提高模拟9
组题人： @Delov
\(T1\) P161. 大众点评 \(0pts\)
-
思路来自 1037 - CSP 2021 提高级第一轮 第 5 题 。
-
\(2n\) 次比较是好做的。不难发现在这些比较是有多余的，考虑减少多余比较。
-
将 \(n\) 座拉面馆两两配对，对奇偶进行分讨。若 \(n\) 为奇数，令 \(a_{n+1}=a_{n}\) 。
-
将第 \(i\) 和 \(i+1\) 座拉面馆配对，并要求 \(a_{i}<a_{i+1}\) ，用 \(\left\lfloor \frac{n}{2} \right\rfloor\) 次比较足够了。
-
那么最终答案的最大值一定来自奇数位置上的数，最小值一定来自偶数位置上的数，至多各消耗 \(\left\lceil \frac{n}{2} \right\rceil-1\) 次比较。
点击查看代码
#include<bits/stdc++.h> #include"ramen.h" using namespace std; void Ramen(int n) { vector<int>maxx,minn; if(n%2==0) { for(int i=0;i<=n-1;i+=2) { if(Compare(i+1,i)==-1) { maxx.push_back(i); minn.push_back(i+1); } else { maxx.push_back(i+1); minn.push_back(i); } } } else { for(int i=0;i<=n-2;i+=2) { if(Compare(i+1,i)==-1) { maxx.push_back(i); minn.push_back(i+1); } else { maxx.push_back(i+1); minn.push_back(i); } } maxx.push_back(n-1); minn.push_back(n-1); } int max_pos=maxx[0],min_pos=minn[0]; for(int i=1;i<maxx.size();i++) { if(Compare(maxx[i],max_pos)==1) { max_pos=maxx[i]; } } for(int i=1;i<minn.size();i++) { if(Compare(min_pos,minn[i])==1) { min_pos=minn[i]; } } Answer(min_pos,max_pos); }
\(T2\) P164. 录取查询 \(100pts\)
-
\(s_{l \sim r}\) 是 \(t\) 的子串当且仅当 \(s_{l \sim r}\) 是有序的，且除 \(s_{l},s_{r}\) 的字符外其他字符的出现次数必须等于全局中这些字符的出现次数。
-
两个限制线段树都可以维护，时间复杂度为 \(O(|\sum|n \log n)\) ，其中 \(|\sum|\) 取小写字母字符集 \(26\) 。
点击查看代码
int cnt[30]; char s[100010]; int val(char x) { return x-'a'+1; } struct SMT { struct SegmentTree { int cnt[30],l,r,lcol,rcol,flag; }tree[400010]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void pushup(int rt) { for(int i=1;i<=26;i++) { tree[rt].cnt[i]=tree[lson(rt)].cnt[i]+tree[rson(rt)].cnt[i]; } tree[rt].flag=(tree[lson(rt)].flag==1&&tree[rson(rt)].flag==1&&tree[lson(rt)].rcol<=tree[rson(rt)].lcol); tree[rt].lcol=tree[lson(rt)].lcol; tree[rt].rcol=tree[rson(rt)].rcol; } void build(int rt,int l,int r) { tree[rt].l=l; tree[rt].r=r; if(l==r) { tree[rt].lcol=tree[rt].rcol=val(s[l]); tree[rt].flag=1; tree[rt].cnt[val(s[l])]=1; return; } int mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void update(int rt,int pos,char s) { if(tree[rt].l==tree[rt].r) { tree[rt].cnt[tree[rt].lcol]=0; tree[rt].lcol=tree[rt].rcol=val(s); tree[rt].cnt[tree[rt].lcol]=1; return; } int mid=(tree[rt].l+tree[rt].r)/2; if(pos<=mid) { update(lson(rt),pos,s); } else { update(rson(rt),pos,s); } pushup(rt); } SegmentTree query(int rt,int x,int y) { if(x<=tree[rt].l&&tree[rt].r<=y) { return tree[rt]; } int mid=(tree[rt].l+tree[rt].r)/2; SegmentTree p,q,ans; if(y<=mid) { return query(lson(rt),x,y); } else { if(x>mid) { return query(rson(rt),x,y); } else { p=query(lson(rt),x,y); q=query(rson(rt),x,y); for(int i=1;i<=26;i++) { ans.cnt[i]=p.cnt[i]+q.cnt[i]; } ans.flag=(p.flag==1&&q.flag==1&&p.rcol<=q.lcol); ans.lcol=p.lcol; ans.rcol=q.rcol; return ans; } } } bool ask(ll l,ll r) { SegmentTree ans=query(1,l,r); if(ans.flag==0) { return false; } else { for(int i=ans.lcol+1;i<=ans.rcol-1;i++) { if(ans.cnt[i]!=cnt[i]) { return false; } } return true; } } }T; int main() { int n,m,pd,l,r,i; char x; cin>>n>>(s+1); for(i=1;i<=n;i++) { cnt[val(s[i])]++; } T.build(1,1,n); cin>>m; for(i=1;i<=m;i++) { cin>>pd; if(pd==1) { cin>>l>>x; cnt[val(s[l])]--; s[l]=x; cnt[val(s[l])]++; T.update(1,l,x); } else { cin>>l>>r; if(T.ask(l,r)==1) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } } } return 0; }
\(T3\) P165. 精准打击 \(0pts\)
-
本题根节点的深度定义为 \(0\) ，不知道为啥题目没给这个条件。
-
部分分
- \(10pts\) ：若 \(x=\sum\limits_{i=0}^{d}k^{i}\) ，此时不需要删边，否则断一条边即可。
-
正解
- 连通块为树时显然是使删边数量最小的情况。
- 考虑枚举子树根节点的深度 \(dep\) ，然后贪心地从上往下删子树内的边并尽可能多删，缩小问题规模。
- \(dep \ne D\) 时需要需要断掉和父亲节点断边。
点击查看代码
ll num[70],sum[70]; int main() { ll t,d,k,x,ans,cnt,tot,i,j,h; cin>>t; for(h=1;h<=t;h++) { cin>>d>>k>>x; sum[0]=num[0]=1; for(i=1;i<=d;i++) { num[i]=num[i-1]*k; sum[i]=sum[i-1]+num[i]; } ans=sum[d]; for(i=0;i<=d;i++) { if(sum[i]>=x) { cnt=(i!=d); tot=sum[i]-x;//需要删的点数 for(j=i-1;tot>0&&j>=0;j--) { cnt+=tot/sum[j]; tot%=sum[j]; } ans=min(ans,cnt); } } cout<<ans<<endl; } return 0; }
\(T4\) P172. 你画我猜 \(8pts\)
- 原题： luogu P4459 [BJOI2018] 双人猜数游戏
- 部分分
- \(12pts\) ：手摸前三个点。
- 正解
- 感觉和 UVA1657 游戏 Game 挺像。
总结
- 赛时历程：将 \(T1,T2,T3,T4\) 溜了一眼， \(T1\) 的结论自己觉得想一会儿就能会了， \(T2,T3\) 不太可做， \(T4\) 有部分分可以打，加上之前打过交互。遂先写 \(T1\) ，和本地的 \(CE\) 搏斗；然后趁着脑子清醒，写了 \(T4\) 的前几个点； \(T2\) 想过支持动态插入、删除平衡树套线段树维护哈希，想过字典树上更改父亲，但都不可做，最终一共想了 \(35 \min\) 就想出来了， \(15 \min\) 码完加调完，大样例一遍过且跑得飞快就直接交了；最后写 \(T3\) 。
- \(T1\)
- 下标从 \(0\) 开始是没想到的，被绕了一会儿。
- 结论以前刷初赛时专门上网查了一下，所以想了一会儿回忆起来了。
- 以为
Compare(X,Y)中比较的是 \(x,y\) 的大小关系，但实际上是 \(a_{x},a_{y}\) 的大小关系，于是自认为 \(CE\) 是本地的问题，直接交了，挂了 \(100pts\) 。
- \(T3\)
- 没看见 \(10 \%\) 的数据是保证 \(x\) 为一棵满 \(k\) 叉树的点数和，直接当深度 \(=d\) 来做，挂了 \(10pts\) 。
- \(T4\)
- 以为从
Alice还是从Bob开始问并不会影响最终结果，导致手摸样例错了一个点。
- 以为从
后记
- 新题较多，且难度不单调递增。初赛知识点普及场，非传统题普及场。