2021中国大学生程序设计竞赛 女生专场C题题解
2021/11/5 22:14:43
本文主要是介绍2021中国大学生程序设计竞赛 女生专场C题题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
思路:要求何寻找一个最短的 t,使得 t 不是 s(l,r) 的子序列,假设现在位于x,那么下一步有m个选择,我们要使得子序列尽可能的小,所以就要选择离x最远的那个字母,直到走出r为止。于是问题转化为:从 l 开始沿着 _next 一路往右跳,要跳多少步才能跳到 > r 的地方。求区间最值问题,使用st表,我们使用倍增的方法使得_next[i][j]: 是i从2^j步到达的最远位置。
#include<bits/stdc++.h> using namespace std; char s[200100]; int _next[200100][26];//st表 int v[2000100]; int a[26]; int main(){ int m,n; scanf("%d%d",&m,&n); scanf("%s",s+1); for(int i=0;i<=25;i++){ a[i]=n+1; } for(int i=n;i>=0;i--){ for(int j=0;j<m;j++){ v[i]=max(v[i],a[j]); } _next[i][0]=v[i]; if(i)a[s[i]-'a']=i; } for(int i=1;i<=n;i++){ cout<<v[i]<<' '; } for(int j = 1; j < 20; j ++){ for(int i = 0; i <= n; i ++) { int t = _next[i][j - 1]; if(t <= n) _next[i][j] = _next[t][j - 1]; else _next[i][j] = n + 1; } } int q; scanf("%d",&q); while(q--){ int l,r; scanf("%d%d",&l,&r); int ans = 0, now = l - 1; for(int j = 19; ~j; j --) if(_next[now][j] <= r) ans += (1 << j), now = _next[now][j]; printf("%d\n",ans+1); } return 0; }
这篇关于2021中国大学生程序设计竞赛 女生专场C题题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08测试人员在 Scrum 中的角色是什么?
- 2024-07-07Dify + TiDB Vector,快速构建你的AI Agent
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享