Codeforces Gym 102428 E. Eggfruit Cake

题意：
给定一个只含 $P$P和 $E$E的首尾可相连的字符串，求至少包含一个字符 $E$E的且串长不超过 $n$n的子串个数。

题解：
枚举串中每个 $E$E。设当前 $E$E与枚举的上一个 $E$E之间 $P$P的个数为 $x$x个，为了避免重复统计，我们在当前 $E$E的顺时针方向选择 $min(n-1,x)$min(n−1,x)个字符，在当前 $E$E的逆时针方向选择 $n-1$n−1个字符。
那么问题就转换为了求长度为 $1$1~ $n$n的串的个数。
假设当前 $E$E顺时针方向可选字符为 $l$l个，逆时针方向可选字符为 $r$r个。
由于 $l\le r$l≤r,所以我们枚举选择 $l$l的个数。

共 $n$n种情况

共 $n-1$n−1种情况

共 $n-2$n−2种情况

$\cdots$⋯

共 $n-l$n−l种情况

那么答案就是 $(n-l)+(n-l+1)+...+(n-1)+n=\frac{(2\ast n-l)\ast (l+1)}{2}$(n−l)+(n−l+1)+...+(n−1)+n=2(2∗n−l)∗(l+1)​

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 100010;
char s[N];
int pos[N], g;
int n;

int main()
{
	scanf("%s%d", s, &n);
	int len = strlen(s);
	
	for(int i = 0; i < len; i++)
		if(s[i] == 'E') pos[g++] = i;
		
	if(g == 0) return 0 * printf("0\n");
	
	ll x = min(n - 1, pos[0] + len - pos[g - 1] - 1);
	ll res = (ll)(x + 1) * (2 * n - x) / 2;
	for(int i = 1; i < g; i++) {
		ll t = min(n - 1, pos[i] - pos[i - 1] - 1);
		res += (ll)(t + 1) * (2 * n - t) / 2;
	}
	
	printf("%lld\n", res);
	
	return 0;
}