给出一个字符串,你可以选择一个长度大于等于1的子串进行翻转,也可以什么都不做.只能翻转最多一次. 问所有不同的操作方式得到的字符串中有多少个是本质不同的.
tourist的题妙妙啊. 首先这个题我们可以发现,如果一个子串[i,j]满足s[i]==s[j],那么翻转这个子串相当于翻转子串[i+1,j-1],于是我们不妨先统计有多少个子串满足左端和右端的字符不同.这是答案的一个上界. 同时,如果两个不同的字串都满足左端的字符不等于右端的字符,那么这两个子串分别翻转得到的串一定不同.只需考虑四个端点位置,讨论一下就可以证明这一点. 依次考虑以每个位置为左端点,右边有多少个位置的字符和左端点不相同. 复杂度O(n).
#include<cstdio> #include<cstring> char str[200005]; int cnt[30],sum[30]; int main(){ scanf("%s",str+1); int n=strlen(str+1); for(int i=1;i<=n;++i)sum[str[i]-'a'+1]++; long long ans=0; for(int i=1;i<=n;++i){ cnt[str[i]-'a'+1]++; ans=ans+n-i-(sum[str[i]-'a'+1]-cnt[str[i]-'a'+1]); } printf("%lld\n",ans+1); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7468671.html
相关资源：数据结构—成绩单生成器