题解 | 滑动窗口做法

实际上就是问我们，能找出多少对区间 $[L,R]$ ，使满足这一段被挖去后，剩余的字符串中有一个子序列是 $P_{[L,R]}$ 。

观察时间复杂度，大概是 $O(n^2) \sim O(n^2 \log n)$ 的级别，我们考虑这样一件事：

如果 $[L,R]$ 是合法答案，那么往里缩也一样合法，因为往里缩会减少字符数量。
如果 $[L,R]$ 不是答案，那么扩大一样不合法，因为往外扩会额外增加字符负担
如果 $R-L+1>\frac n 2$ ，那么一定不合法，因为子序列长度不可能超过两边的长度。

于是很容易想到滑动窗口的做法：

初始时，设 $L=2，R=2$ ，

若当前区间合法，则 $R++$
若当前区间不合法，显然 $[L,R-1]$ 是合法区间，答案有 $R-L$ 个，累计答案后 $L++$
特别地：若 $[L,L]$ 不是合法区间，需要R++一次

枚举的时间复杂度是 $O(n)$ ，判断合法(即S是否是T的子序列）的时间复杂度是 $O(n)$ ，最终的时间复杂度为： $O(n^2)$ 事实上根据结论3的优化，我们每次 $R$ 的移动跨度不会超过 $\frac n 2$ ，所以常数会非常小

#include <iostream>
#include <vector>
using namespace std;
const int N=2e3+1;
int a[N];
int n;
bool check(int& l,int& r){
    int i=1,j=l;
    while(i<=n && j<=r){
        if(a[i]==a[j]){
            j++;
        }
        i++;
        if(i==l)i=r+1;
    }
    return j==r+1;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=0;
    int l=2,r=2;
    int len;
    while(l<n){
        len=(r-l+1);
        while(len<=n-len && check(l,r) && r<n){ //如果合法，并且r没有超过n
            r++;//如果可以就一直++
        }
        //退出了有2种情况
        //不合法,且l<r,说明[l,r-1]是合法区间
        //不合法,且l=r，说明[l,l]不合法，需要r++
        if(l<r)ans+=r-l;
        else r++;
        l++;
    }
    cout<<ans;
    return 0;
}

这道题我一直以为是什么难题，以为是dp，以为是什么需要注意力的题，仔细分析后发现其实很简单，这份代码极致优化过后能跑到 $20ms$ ，内存占用也低，也算不错了