题解 CF1398D 【Colored Rectangles】

发表于

题意

给定数组 $a$ 满足 $a_i\in \{0,1,…9\}$，求有多少个区间 $[l,r]$ 满足 $\sum_{i=l}^r=r-l+1$。

$\operatorname{Sol}$

考场上的奇怪想法qwq。

把式子变形一下，变成

先枚举一下 $r$，把式子的右边丢进一个桶里。再开始枚举 $l$，为了保证区间合法，每次统计前先去除 $l-1$ 处的贡献，再统计答案，实现见代码。

$\operatorname{Code}$

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
#include <bits/stdc++.h>
using namespace std;
int t[1000001], a[100001], pre[100001];
char ch[100001];
int main (){
    int T;
    scanf("%d", &T);
    while(T--){
        memset(t, 0, sizeof(t));//多测清空桶
        int n;
        scanf("%d", &n);
        scanf("%s", ch + 1);
        for (int i = 1; i <= n; i++){
            a[i] = ch[i] - '0';
            pre[i] = pre[i - 1] + a[i];
        }
        for (int i = 0; i <= n; i++)
            t[pre[n] - pre[i] + i]++;//先把右边的式子丢进桶里
        long long ans = 0;
        for (int i = 1; i <= n; i++){
            t[pre[n] - pre[i - 1] + i - 1]--;//去除不合法的贡献
            ans += t[pre[n] - pre[i - 1] + i - 1];//统计答案
        }
        printf("%lld\n", ans);//记得开long long
    }
    return 0;
}
+ +