今天打了百度之星，在xwd学长的帮助下签到成功（我太菜了）。虽说是签到，但顺带学了一下一个叫前缀和的东西，还是有点收获的。
参考：蒟蒻复习之—–前缀和和差分
求解问题：
给出一个整形数组a[n]，然后给出闭区间[l, r]，求a[l] + a[l + 1] + a[l + 1] + ……+a[r]
假设有很多组l, r所以不能用直接模拟的办法。
解法
设一个数组sum[]， sum[i] 表示a[1] + a[2] + ……a[i]，即数组a的前i项和。在初始化sum之后，要求[l, r]闭区间的元素和，则可以转换为sum[r] - sum[l - 1]。
代码：
int init() {
for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i];
}
int get(int l, int r) {
return sum[r] - sum[l-1];
}
百度之星2018的1002题
image.png
image.png
题意分析
简单来说：给出一个字符串，然后求某个闭区间里的字典序最小的子序列个数，由题意知，A的字典序小于AA，即前面都相同的情况下越短的字符串字典序越小，所以字典序最短的应该是单个字母，所求即是——在给定区间里字典序最小的那个字母出现的次数
解法
求在给定区间里字典序最小的那个字母出现的次数，可以转换为前缀和问题，设一个26 * n的数组sum，每个一维数组sum[x]就表示字母x出现次数的前缀和。
所以，需要枚举'A' ~'Z'，求出每个字母出现次数的前缀和。
sum[s[0]][0] = 1;//在j = 0处，s[0]出现了1次，所以记为0
for (int i = 'A'; i <= 'Z'; i++){
for (int j = 1; j < n; j++){
if (s[j] == i){
sum[i][j] = sum[i][j - 1] + 1;// 如果i出现了，则sum为上一次+1，可以类比一下前面写的纯前缀和里的 sum[i] = sum[i-1] + a[i];
}
else{
sum[i][j] = sum[i][j - 1];//没有出现，即当前位置对和没有贡献，亦可以理解为sum[i][j] = sum[i][j - 1] + 0
}
}
}
最后查询的时候还有一个小坑，题意中下标从1开始，但读字符串的话下标从0开始，所以每次都需要l--, r--一下。（当时脑抽没注意这个，调了半天）
完整代码
#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define maxn 100005
#define LOCAL
int main(int argc, char * argv[]) {
//freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++){
int n, q, l, r, ans[maxn];
int sum[100][maxn];
scanf("%d%d", &n, &q);
char s[maxn];
scanf("%s", s);
ms(sum);
ms(ans);
sum[s[0]][0] = 1;
for (int i = 'A'; i <= 'Z'; i++){
for (int j = 1; j < n; j++){
if (s[j] == i){
sum[i][j] = sum[i][j - 1] + 1;
}
else{
sum[i][j] = sum[i][j - 1];
}
}
}
for (int k = 0; k < q; k++){
scanf("%d%d", &l, &r);
l--;r--;
for (int i = 'A'; i <= 'Z'; i++){
if (sum[i][r]-sum[i][l - 1] > 0){
ans[k] = sum[i][r] - sum[i][l - 1];
break;
}
}
}
printf("Case #%d:\n", t);
for (int i = 0; i < q; i++){
printf("%d\n", ans[i]);
}
}
return 0;
}
