自动搬运

查看原文

来自洛谷，原作者为

	poembelief 一个拉到极致的蒟蒻

搬运于2025-08-24 23:08:19，当前版本为作者最后更新于2025-01-10 15:32:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

[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;
}