2018"百度之星"程序设计大赛-资格赛P1002子串查询（前缀和）

因为过关要求貌似是随便A掉一道题，，，还实时给了AC率，不是摆明了让我挑最水的题写吗。。

problem

• 给定一个字符串A[1,n].
• 询问q次，A[l,r]内字典序最小的连续非空子串有多少次重复。
• n <= 10^5

solution

• 字典序最小(可是字典序越短越小啊)，那么最小的一定是一个字母
• 于是就变成了求[l,r]最小字母的出现次数。

emmm

• 前缀和统计[1,r]中有每个字母有多少个。
• 对于每次查询，字典序从小到大枚举，如果存在该字符(个数不为零)，即为答案

codes

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100010;
int n, q; char s[maxn];
int a[maxn][27];
int main(){
    int w;  scanf("%d",&w);
    for(int _w = 1; _w <= w; _w++){
        printf("Case #%d:\n", _w);
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        int len = strlen(s+1);
        memset(a,0,sizeof(a));
        for(int i = 1; i <= len; i++){
            for(int j = 0; j <= 25; j++)
                a[i][j] = a[i-1][j];
            a[i][s[i]-'A']++;
        }
        for(int i = 1; i <= q; i++){
            int l, r;  scanf("%d%d",&l,&r);
            for(int j = 0; j <= 25; j++){//从小到大枚举
                if(a[r][j]-a[l-1][j] != 0){//存在该字符
                    printf("%d\n",a[r][j]-a[l-1][j]);//输出
                    break;
                }
            }
        }
    }
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/81431850