题解：P11553 [ROIR 2016 Day 1] 奇怪的字符串

· · 题解

题目传送门

[ROIR 2016 Day 1] 奇怪的字符串

题目分析

我们先不考虑子串的问题，先考虑如何判断一个子串是否是奇怪的。

随便找几个字符串看一下，或者就看样例给的 abba，会发现 abba 最直观的不合法例子在于 aa 是子序列但不是子串。观察 aa 是如何取出来的，可以大胆推测一下：一个子串是奇怪的，当且仅当该字符串由一种字符构成或者两种不同字符是相邻排放的。

形式化的说法就是令 A、B 为多个相同字符拼接成字符串，一个字符串是奇怪的当且仅当该字符串格式为 A、B、AB，而 ABA 或者 ABC 之类的字符串是不奇怪的。

我们来稍稍证明一下：

对于字符串 ABA，一定可以取出不合法例子 AA，只要含这种结构的字符串一定不奇怪。

对于字符串 ABC，一定可以取出不合法例子 AC，只要含这种结构的字符串一定不奇怪。

对于字符串 A，取不出不合法例子是显然的。

对于字符串 AB，令 A 的大小为 n，B 的大小为 m，则对于 x \leq n,y \leq m，子序列一定是 x 个 a 或 y 个 b，或 x 个 a 和 y 个 b 拼接起来的字符串，而这是一定可以取出来的，故而一定是奇怪的。

至此，这题就变得很简单了：只需要考虑 AB 和 A 形子串有多少个即可，注意去重问题。

代码

#include<bits/stdc++.h>
using namespace std;
/*
*/
const int N=2e5+5;
int n,t,ty[N];
long long ans,tot[30][30][N],cnt[N],same[N];
char s[N];
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  freopen("tx.in","r",stdin);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++){
        if(s[i]!=s[i-1]) ty[++t]=s[i]-'a';
        cnt[t]++;
    }
    for(int i=1;i<=t;i++){
        same[ty[i]]=max(same[ty[i]],cnt[i]);
        for(int j=1;j<=cnt[i];j++){
            tot[ty[i-1]][ty[i]][j]=max(tot[ty[i-1]][ty[i]][j],cnt[i-1]);
        }
    }
    for(int i=0;i<26;i++){
        ans+=same[i];
        for(int j=0;j<26;j++){
            if(i==j) continue;
            for(int k=1;k<=n;k++){
//              if(!tot[i][j][k]) continue;
                ans+=tot[i][j][k];
//              cout<<i<<','<<j<<','<<k<<":"<<tot[i][j][k]<<endl;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}