题目描述
将字母转为数字来实现前缀和,且不能是随意n个字母转为数字的和等于另外n个字母转为数字的和
(n个字母中可以有相同字母)
故字母变为的数字必须为素数,且不能为前两项的和
样例
#include<stdio.h>
#include<string.h>
//判断素数
int is_prime(int num) {
if (num <= 1) {
return 0;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return 0;
}
}
return 1;
}
int main(){
char s[500000];
scanf("%s", s);
int n;
scanf("%d", &n);
int len = (int )strlen(s);
int num[len];
int sum[len];
//无和差分数组,不会出现a + b + c + ... + n == b + c + ... + (n + 1)的问题
int no_sum_diff_num[26];
no_sum_diff_num[0] = 1;
no_sum_diff_num[1] = 2;
for (int k = 2; k < 26; k++) {
no_sum_diff_num[k] = no_sum_diff_num[k - 1] + no_sum_diff_num[k - 2] + 1;
while (!is_prime(no_sum_diff_num[k]))
no_sum_diff_num[k]++;
}
//将字母变为无和差分数列
int i;
for (i = 0; i < len; i++)
num[i] = no_sum_diff_num[(int)(s[i] - 'a')] ;
//前缀和模板套进去
sum[0] = num[0];
for (i = 1; i < len; i++)
sum[i] = sum[i - 1] + num[i];
while (n--){
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
if (a != b && sum[b - 1] - ((a - 2 < 0) ? 0: sum[a - 2]) == sum[d - 1] - ((c - 2 < 0) ? 0: sum[c - 2]) || (a == b && num[a - 1] == num[c - 1]))
printf("DA\n");
else printf("NE\n");
}
return 0;
}
算法1
(前缀和)
时间复杂度 O(n)
参考文献
C 代码
#include<stdio.h>
int main(){
int n1, n2;
scanf("%d %d", &n1, &n2);
int num[n1];
int i;
for (i = 0; i < n1; i++) scanf("%d", &num[i]);
int res[n1];
res[0] = num[0];
for (i = 1; i < n1; i++)
res[i] = res[i - 1] + num[i];
while (n2--){
int l, r;
scanf("%d %d", &l, &r);
printf("%d\n", res[r - 1] - (l - 2 >= 0? res[l - 2]: 0));
}
return 0;
}