子串查询(二维前缀数组) 2018"百度之星"程序设计大赛 - 资格赛
2024-08-29 13:51:24
子串查询
Time Limit: 3500/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 835 Accepted Submission(s): 409
Problem Description
度度熊的字符串课堂开始了!要以像度度熊一样的天才为目标,努力奋斗哦!
为了检验你是否具备不听课的资质,度度熊准备了一个只包含大写英文字母的字符串 A[1,n]=a1a2⋯an,接下来他会向你提出 q 个问题 (l,r),你需要回答字符串 A[l,r]=alal+1⋯ar 内有多少个非空子串是 A[l,r] 的所有非空子串中字典序最小的。这里的非空子串是字符串中由至少一个位置连续的字符组成的子序列,两个子串是不同的当且仅当这两个子串内容不完全相同或者出现在不同的位置。
记 |S| 为字符串 S 的长度,对于两个字符串 S 和 T ,定义 S 的字典序比 T 小,当且仅当存在非负整数 k(≤min(|S|,|T|)) 使得 S 的前 k 个字符与 T 的前 k 个字符对应相同,并且要么满足 |S|=k 且 |T|>k,要么满足 k<min(|S|,|T|) 且 S 的第 k+1 个字符比 T 的第 k+1 个字符小。例如 "AA" 的字典序比 "AAA" 小,"AB" 的字典序比 "BA" 小。
Input
第一行包含一个整数 T,表示有 T 组测试数据。
接下来依次描述 T 组测试数据。对于每组测试数据:
第一行包含两个整数 n 和 q,表示字符串的长度以及询问的次数。
第二行包含一个长为 n 的只包含大写英文字母的字符串 A[1,n]。
接下来 q 行,每行包含两个整数 li,ri,表示第 i 次询问的参数。
保证 1≤T≤10,1≤n,q≤105,1≤li≤ri≤n。
Output
对于每组测试数据,先输出一行信息 "Case #x:"(不含引号),其中 x 表示这是第 x 组测试数据,接下来 q 行,每行包含一个整数,表示字符串 A[l,r] 中字典序最小的子串个数,行末不要有多余空格。
Sample Input
1
2 3
AB
1 1
1 2
2 2
2 3
AB
1 1
1 2
2 2
Sample Output
Case #1:
1
1
1
1
1
1
题意在给定区间内找最小的字典序的个数,一个字符的时候是最短的,只要计算最小的那个字符出现的次数,用二维前缀数组记录,参考自其他大佬
#include<bits/stdc++.h>
using namespace std;
int a[][];
int main()
{
int t;
scanf("%d",&t);
string s;
int cnt=;
while(t--)
{
memset(a,,sizeof(a));
int n,q;
scanf("%d %d",&n,&q);
cin>>s;
a[][s[]-'A']=;
printf("Case #%d:\n",cnt++);
for(int i=; i<s.size(); i++)
{
for(int j=;j<;j++)
a[i][j]=a[i-][j];//二维前缀数组 a[i][s[i]-'A']++;
}
while(q--)
{
int x,y;
scanf("%d %d",&x,&y);
x--;
y--;
for(int i=; i<; i++)
{
if(x!=&&a[y][i]-a[x-][i]!=){//左边界不是第一个的情况
printf("%d\n",a[y][i]-a[x-][i]);
break;
}
else
if(x==&&a[y][i]!=){//从第一个开始
printf("%d\n",a[y][i]);
break;
}
}
}
}
return ;
}
最新文章
- 工大助手(C#与python交互)
- H5移动前端开发常用高能css3汇总
- C语言 时间函数的学习和总结
- ViewModel在MVC3中的应用:一个view显示多个model
- iOS高性能图片架构与设计
- 判断IMEI或MEID是否合法
- 浅谈RDD
- WPF Customize TabControl
- 十依据一个有用的算法来找到最小(最大)的k的数量-线性搜索算法
- diskpart修改盘符
- java中的final与static
- dede织梦如何防止被黑客入侵渗透?
- HashMap 你真的了解吗?
- iOS中用UILabel实现UITextView的占位文字
- ruby the diference between gets and gets.chomp()
- No module named ";Crypto";,如何安装Python三方模块Crypto
- 集成Javascript Logging on MVC or Core
- codeforces #541 D. Gourmet choice(拓扑+并查集)
- 阅读:ECMAScript 6 入门(1)
- DevExpress WinForms v18.2新版亮点(二)
热门文章
- HDU 1754 I Hate It 【线段树单点修改 维护区间最大值】
- 2017.9.1 Java中的程序方法
- Webstorm 添加新建.vue文件功能并支持高亮vue语法和es6语法
- Maven Dependencies missing jar 解决
- QBXT Day 2 记录
- 手把手教你玩转 CSS3 3D 技术
- GoBelieve Android SDK接入备忘
- Spring知识点小结(一)
- 初涉基环外向树dp&;&;bzoj1040: [ZJOI2008]骑士
- chromium之tuple