CF1307C Cow and Message:数学+前缀和

题目来源: CF1307C Cow and Message.
题目大意:找出子串在原串中序号成等差数列的最大值。
要成等差数列,长度1个或2个很容易,3个就麻烦啦,所以最大值只可能出现在长度为1或2的情况。
一开始想错了,以为只找出个数最多的两个即可,相乘。例如aabbb,没有注意顺序问题,写错了。
所有长度为2的等差数列只有2626种。如果长度一个字符在位置p上,那么他只能与后面的的字符形成等差数里,所以维护前缀和或后缀和,然后26n边扫边计算。
参考代码

using namespace std;
typedef long long ll;
//一个字母,只能与后面的形成子串
const int N=1e5+10;
char s[N];
ll cnt[30],b[N][30];
int main() {
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%s",s);
	int l=strlen(s);
	for(int i=0; s[i]; i++) {
		int t=s[i]-'a';
		cnt[t]++;
		if(i>0)memcpy(b[i],b[i-1],240);//这里写成120,差错好久
		b[i][t]++;
	}
	sort(cnt,cnt+26);
	ll ans=max(cnt[25],cnt[25]*(cnt[25]-1)/2),sum[30][30]={0};
	for(int k=0; s[k]; k++) {//字符ij有多少个,i在前,j在 
		int j=s[k]-'a';
		for(int i=0; i<=25; i++) {
			if(j!=i)sum[i][j]+=b[k][i];
			ans=max(ans,sum[i][j]);
			char x=i+'a',y=s[k];
		}
	}
	printf("%lld\n",ans);
}
CF1307C Cow and Message:数学+前缀和CF1307C Cow and Message:数学+前缀和 lengxuenong 发布了116 篇原创文章 · 获赞 25 · 访问量 4万+ 私信 关注
上一篇:超级书架2(计蒜客)


下一篇:luogu P2419 [USACO08JAN]牛大赛Cow Contest