题解：AT_abc345_c [ABC345C] One Time Swap

求过审

题面翻译

给定一个字符串 $ s $ ，求执行以下操作一次可以产生的字符串的个数

设 $ N $ 为 $ s $ 的长度。选择一对整数 $ (i,j) $ ，使 $ 1≤i<j≤N $ ，交换 $ s $ 的第 $ i $ 个和第 $ j $ 个字符

可以证明，在这个问题的约束条件下，你总是可以得到它

思路

暴力做法

我们可以暴力枚举 $ 1 \leq i < j \leq N $

若 $ s_i=s_j $ ，即交换后 $ s $ 不变，那么跳过

否则 $ ans $ 加 $ 1 $

注意：如果有重复字母，需要将 $ ans $ 加 $ 1 $

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;
ll l,ans=0,f=0;
int main()
{
	ios::sync_with_stdio(0);//关闭流同步 
	cin>>s;
	l=s.size();
	s=' '+s;//巧妙地把第一位下标转成1
	for(int i=1;i<=l;i++)
	{
		for(int j=i+1;j<=l;j++)
		{
			if(s[i]!=s[j]) ans++;
			else f=1;
		}
	}
	cout<<ans+f;
	return 0;
}

提交后发现 $ TLE\ 13 $ 个点

优化

我们可以发现对于 $ s_i $

那么和其相等的 $ s_j $ 的个数可以通过后缀和统计

于是

for(int j=i+1;j<=l;j++)
{
	if(s[i]!=s[j]) ans++;
	else f=1;
}

这重循环可以变为

ans+=l-i+1sum[s[i]-'a'+1];
//这里是把a的下标看做1
//sum是后缀和

所以我们可以先求后缀和，然后计算

也可以倒着枚举，边计算边求

这里采用倒着枚举：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;
ll f[1000100],a[100100],l,fl;
//fl记录是否有重复字母
int main()
{
	cin>>s;
	l=s.size();
	s=' '+s;
	a[s[l]-'a'+1]=1;
	f[l]=0;
	for(ll i=l-1;i>=1;--i)
	{
		a[s[i]-'a'+1]++;
		if(!fl&&a[s[i]-'a'+1]>1) fl=1;
		f[i]=l-i+1-a[s[i]-'a'+1];
	}
	for(ll i=1;i<=l;++i) f[0]+=f[i];
	cout<<f[0]+fl;
	return 0;
}

无关的话（审核大大不要计较）：被禁言了，怎么解啊？

感谢观看