补题

比赛传送门

E

记dp[i]为以i为起点的数组有几个好数组,如果i位置开始有一个块,那么可以状态转移(自己的块加上后面原有的好数组)注:k为a[i]

$$dp[i]=1+dp[i+k] $$

否则

$$dp[i]=0 $$

最终答案就是dp数组的总和
接下来的问题就是如何快速判断i位置开始是否有一个块了:
预处理一个数组 s 其中s[i]表示从位置 i 开始，向右连续出现且值与 a[i]相同的元素所能到达的最远下标
从右往左扫描:
如果$a[i]==a[i+1]$ 那么$s[i]=s[i+1]$
否则$s[i]=i$
如果$i+k-1≦s[i]$那么i位置开始有一个块
那么问题都解决了,接下来可以愉快地写代码了(注意处理数组越界)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    vector<int> s(n);
    for (int i=n-1;i>=0;i--) {
        if (i<n-1 && a[i]==a[i+1]) s[i]=s[i+1];
        else s[i]=i;
    }
    vector<int> dp(n+1); dp[n]=0;
    for (int i=n-1;i>=0;i--) {
        if (s[i]>=i+a[i]-1) dp[i]=dp[i+a[i]]+1;
        else dp[i]=0;
    }
    int sum=0;
    for (int i=n-1;i>=0;i--) sum+=dp[i];
    cout<<sum<<el;
}

F

emmm看了好多题解,都是用稀疏表,目前还没学qwq,学了之后来补题

说些什么吧！

waline