暑假集训CSP提高模拟15
组题人： @LYinMX
\(T1\) P213. 串串 \(15pts\)
-
部分分
- \(15pts\) ：当 \(|S|=1\) 时输出 \(1\) ，否则顺序输出 \([2,|S|]\) 。
-
正解
- 由题，有 \(R\) 一定是 \(S\) 的前缀。
- 赛时在这里被绕进去，一直在想怎么证。
- 发现翻转存在一个“传递关系”：若 \(a\) 能被 \(b\) 翻转得到，且 \(b\) 能被 \(c\) 翻转得到，则 \(a\) 能被 \(c\) 翻转得到。这启发我们可以从后到前考虑整个字符串。
- 不难发现，奇回文串才可能会对翻转产生影响
- 字符串 \(S\) 的最长真翻转子串（不包括本身）为 \(S\) 除去末尾最短回文子串的后半部分（除去部分不包括回文中心）。
- 考虑枚举回文中心，若能顶到右端点或能顶到左端点且翻转后仍符合题意则说明符合题意。
- 最后统计答案时要除去加入的特殊字符的影响。
点击查看代码
int r[10000010],vis[10000010]; string s,t; int main() { int T,n,maxr,id,i,j; cin>>T; for(j=1;j<=T;j++) { cin>>s; maxr=id=0; t=" #"; for(i=0;i<s.size();i++) { t+=s[i]; t+="#"; } n=t.size()-1; for(i=1;i<=n;i++) { r[i]=(i<maxr)?min(r[id-(i-id)],maxr-i):1; while(1<=i-r[i]&&i+r[i]<=n&&t[i+r[i]]==t[i-r[i]]) { r[i]++; } if(maxr<i+r[i]) { maxr=i+r[i]; id=i; } } for(i=n;i>=1;i--) { vis[i]=((i+r[i]-1==n)||(i<i+r[i]-2&&vis[i+r[i]-2]==1&&i-r[i]+1==1));//除去加入的特殊字符影响 //vis[i] 表示 i 是否能作为翻转中心 } for(i=1;i<=n;i++) { if('a'<=t[i]&&t[i]<='z'&&vis[i]==1) { cout<<i/2<<" "; } } cout<<endl; } return 0; } - 由题，有 \(R\) 一定是 \(S\) 的前缀。
\(T2\) P215. 排排 \(47pts\)
-
至多需要三次操作，分别取 \(k=1,k=n,k=1\) 进行操作即可。
-
若 \(\{ P \}\) 本身就升序则不需要操作，输出 \(0\) 即可。
-
若 \(\exist k \in [1,k]\) 满足 \(P_{k}=k\) 且 \(P_{1 \sim k-1}\) 恰好包含了 \([1,k-1]\) （即 \(\nexists x \in [1,k-1],P_{x}>P_{k}\) ）则操作 \(k\) 即可，输出 \(1\) 即可。
-
考虑取 \(k=1\) 操作的意义在于防止最后出现 \(P_{n-1}>P_{n}\) 的情况，而这仅出现于 \(P_{1}=n,P_{n}=1\) 的时候，特判即可；否则输出 \(2\) 。
点击查看代码
int a[200010]; int main() { int t,n,flag,maxx,i,j; cin>>t; for(j=1;j<=t;j++) { cin>>n; flag=1; maxx=0; for(i=1;i<=n;i++) { cin>>a[i]; flag&=(a[i-1]<=a[i]); } if(flag==1) { cout<<0<<endl; } else { for(i=1;i<=n;i++) { if(a[i]==i&&maxx<a[i]) { flag=1; break; } maxx=max(maxx,a[i]); } if(flag==1) { cout<<1<<endl; } else { if(a[1]==n&&a[n]==1) { cout<<3<<endl; } else { cout<<2<<endl; } } } } return 0; }
\(T3\) P187. 序序 \(10pts\)
- 强化版： luogu P6406 [COCI2014-2015#2] Norma | SP22343 NORMA2 - Norma | luogu P8868 [NOIP2022] 比赛
- 部分分
- 子任务 \(1\) ：挂个 \(ST\) 表预处理，暴力查询，时间复杂度为 \(O(n^{2}m)\) ，空间复杂度为 \(O(n \log n)\) 。
- 子任务 \(2\) ：对式子进行二维差分，预处理矩阵，时间复杂度为 \(O(n^{2}+m)\) ，空间复杂度为 \(O(n^{2})\) 。
- 正解
-
感觉猫树分治的做法很可做，等有时间再补吧。
-
\(T4\) P214. 桥桥 \(13pts\)
-
部分分
- \(13pts\)
-
修改时按照链式前向星的编号修改，查询时遍历整个图。
点击查看代码
struct node { int nxt,to,w,id; }e[200010]; int head[200010],vis[200010],cnt=0,ans; 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 dfs(int x,int w,int dfn) { ans++; vis[x]=dfn; for(int i=head[x];i!=0;i=e[i].nxt) { if(vis[e[i].to]!=dfn&&e[i].w>=w) { dfs(e[i].to,w,dfn); } } } int main() { int n,m,q,t,s,u,v,w,i; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w,i); add(v,u,w,i); } scanf("%d",&q); for(i=1;i<=q;i++) { scanf("%d%d%d",&t,&s,&w); if(t==1) { e[s*2-1].w=e[s*2].w=w; } else { ans=0; dfs(s,w,i); printf("%d\n",ans); } } return 0; } -
将边和操作都离线下来，按照重量由大到小排序，双指针维护比当前重的边和加入顺序。对于永远没有修改的边直接加入并查集，对于有修改的边枚举修改操作看修改时间是否比询问时间靠前。
-
- \(13pts\)
-
正解
- 考虑对操作进行分块。
- 默认这个块以前的修改已经被修改掉。
- 同样将边和询问操作按重量由大到小排序，双指针维护加入的边。对于有修改的边打下标记，若修改时间早于询问时间则用改后的边权更新答案，否则按照原值更新，下次询问时可撤销并查集再暴力删掉即可。
- 最终，将修改的边暴力修改。
- 块长取 \(\sqrt{m \log n}\) 跑得飞快，但貌似算出来是 \(\sqrt{m \frac{\log m}{\log n}}\) 取最优情况。
点击查看代码
struct node { int u,v,w,id; }e[200010]; bool cmp1(node a,node b) { return a.w>b.w; } struct quality { int id,w,dfn; }; bool cmp2(quality a,quality b) { return a.w>b.w; } vector<quality>c,q,tmp; int ans[200010],pos[200010],vis[200010],lsvis[200010],klen; stack<int>s1,s2; void init(int n,int m) { klen=sqrt(m*log2(n))+1; } struct DSU { int fa[200010],siz[200010]; void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; siz[i]=1; } } int find(int x) { return (fa[x]==x)?x:find(fa[x]); } void merge(int x,int y,stack<int> &s) { x=find(x); y=find(y); if(x!=y) { if(siz[x]<siz[y]) { swap(x,y); } s.push(y); siz[x]+=siz[y]; fa[y]=x; } } void split(stack<int> &s) { while(s.empty()==0) { siz[fa[s.top()]]-=siz[s.top()]; fa[s.top()]=s.top(); s.pop(); } } }D; void solve(ll n,ll m) { sort(e+1,e+1+m,cmp1); sort(q.begin(),q.end(),cmp2); for(int i=1;i<=m;i++) { pos[e[i].id]=i; } D.init(n); tmp.clear(); for(int i=0;i<c.size();i++) { vis[c[i].id]=-1;//原边被删 tmp.push_back((quality){c[i].id,e[pos[c[i].id]].w,0});//将原边加入候选集合 } for(int i=0;i<c.size();i++) { tmp.push_back((quality){c[i].id,c[i].w,c[i].dfn});//改后的边加入候选集合 } while(s1.empty()==0) { s1.pop(); } for(int i=0,j=1;i<q.size();i++) { for(;e[j].w>=q[i].w&&j<=m;j++) { if(vis[e[j].id]==0)//没有修改的直接加入并查集 { D.merge(e[j].u,e[j].v,s1); } } for(int k=0;k<tmp.size();k++) { if(tmp[k].dfn<=q[i].dfn) { lsvis[tmp[k].id]=vis[tmp[k].id];//方便后面撤销 vis[tmp[k].id]=tmp[k].w;//后面可以用来更新答案 } } for(int k=0;k<c.size();k++) { if(vis[c[k].id]>=q[i].w) { D.merge(e[pos[c[k].id]].u,e[pos[c[k].id]].v,s2); } } ans[q[i].dfn]=D.siz[D.find(q[i].id)]; for(int k=0;k<tmp.size();k++)//撤销 { if(tmp[k].dfn<=q[i].dfn) { vis[tmp[k].id]=lsvis[tmp[k].id]; } } D.split(s2);//撤销 } for(int i=0;i<c.size();i++) { e[pos[c[i].id]].w=c[i].w;//暴力改 vis[c[i].id]=0; } c.clear(); q.clear(); } int main() { int n,m,t,pd,s,w,i; cin>>n>>m; init(n,m); for(i=1;i<=m;i++) { cin>>e[i].u>>e[i].v>>e[i].w; e[i].id=i; } cin>>t; for(i=1;i<=t;i++) { cin>>pd>>s>>w; if(pd==1) { c.push_back((quality){s,w,i}); } else { q.push_back((quality){s,w,i}); } if(i%klen==0) { solve(n,m); } } if(t%klen!=0) { solve(n,m); } for(i=1;i<=t;i++) { if(ans[i]!=0) { cout<<ans[i]<<endl; } } return 0; }
总结
- 赛时历程：看到下发样例最后以颜文字命名的文件夹（其实是编码不同导致的），以为是 @joke3579 出的题，所以肯定会把 \(T1,T4\) 互换顺序（赛后证明是 \(T1,T2\) 互换顺序）。看到题后因为不会分析 \(T4\) 的复杂度所以觉得 \(T4\) 暴力可过，所以开题顺序为 \(T2,T3,T4,T1\) 。 \(T2\) 忘了在哪里看到过一个类似的，所以直接就去想结论了，期间因为不会用
bitset的any和none，尝试枚举所有用途过样例后就没再管。 \(T3\) 去厕所时口胡了一个两个单调栈预处理以 \(i\) 结尾的子串的最大值和最小值乘积之和的假做法，写出代码后手摸样例发现思路假了，只能把之前写的暴力交上去了。 \(T4\) 写完暴力电脑死机了，被迫重启，然后没有想到链式前向星编号能直接改边权，而是记录边的起点、终点，然后枚举起点的所有边找到这条边的编号，为了防止被卡专门将边随机打乱来保证复杂度正确。写 \(T1\) 时还剩 \(1.5h\) ，被一个显然的结论绕住了，只想了 \(15pts\) 的部分分。然后就去背昨天的《蜀道难》了。 - \(T2\) 没想到会有 \(3\) 种操作的情况，挂了 \(46pts\) ；因
bitset问题挂了 \(7pts\) 。test.count()返回有多少位为 \(1\) 。- 若 \(test\) 所有位都为 \(0\) ，则
test.any()返回false，test.none()返回true。 - 若 \(test\) 至少一位为 \(1\) ，则
test.any()返回true，test.none()返回false。
- \(T4\) 误认为只要用了
bitset，时间复杂度就会带个 \(\frac{1}{w}\) 。std::random_shuffle(左指针l,右指针r)在 C++14 中被弃用，在 C++17 中被移除。- 左闭右开。
std::shuffle(左指针l,右指针r,rng)其中rng是一个随机数生成器，例如std::mt19937 rng(time(0));或std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
后记
-
\(T2\) 因为是结论题所以没下发大样例， \(T3\) 题面太过古老，与现测评机功能不符。
