CF1168B Good Triple 题解

· · 题解

思路

易知，若一个三元组 (x,k) 是合法的，当且仅当 x<x+k<x+2k 且 s_x=s_{x+k}=s_{x+2k}。

因此，对于一个区间 [l,r]，只要存在一个合法三元组满足 l\le x<x+2k\le r，那么这个区间就是满足条件的区间。

我们可以固定区间左端点 l，求出使区间 [l,r] 合法的最小右端点。设这个最小右端点为 R_l，那么所有满足条件的右端点就是 R_l,R_l+1,\dots,n，共 n-R_l+1 个。

于是，原题就能转化为：对于每一个 l，求出所有起点不小于 l 的合法三元组中，最小的右端点。

我们可以从右到左枚举区间左端点 l，记 r 为当前已经找到的最小右端点。

首先考虑起点为 l 的三元组：

枚举 k=1,2,3,\dots，检查是否满足 s_l=s_{l+k}=s_{l+2k}。

由于右端点 l+2k 会随着 k 的增大而增大，所以第一次找到的合法 k 对应的右端点一定是起点为 l 时的最小右端点。

找到后，更新 r=\min(r,l+2\times k)。

而由于之前的 r 表示起点在 l+1 到 n 之间的三元组的最小右端点，因此更新之后，r 就表示起点至少为 l 的所有三元组中的最小右端点。

因此，左端点固定为 l 时，合法的右端点数量为 \max(n-r+1,0)，将其加入答案即可。

复杂度分析

时间复杂度为 O(n\log n)（均摊）。

空间复杂度为 O(n)。

注意，答案需要使用 long long 类型存储。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int n,ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    s=' '+s;
    n=s.size()-1;
    int r=n+1;
    for(int l=n;l>=1;l--){
        for(int k=1;l+2*k<=n;k++){
            if(s[l]==s[l+k]&&s[l+k]==s[l+2*k]){
                r=min(r,l+2*k);
                break;
            }
        }
        ans+=max(n-r+1,0ll);
    }
    cout<<ans<<endl;
    return 0;
}