璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:usaco23open_feb_b
problems
名称FEB B
题目编号USACO23OPEN_B1
题目链接luogu.com.cn/…
来源USACO
算法分类模拟
难易程度容易

FEB B

想法

通过观察可知,对于在字符串中的连续的'F'子串,可能出现的贡献为一个公差为2的等差数列。对于在字符串开头的连续的'F'子串,可能出现的贡献为一个公差为1的等差数列。根据开头是否为'F'进行分类讨论,来计算这个等差数列的上限与下界。

  • 上限:所有F均创造了价值,也就是说F均与前一个相等。
  • 下界:所有F尽可能不创造价值,也就是说F均与前一个不相等。

根据开头与结尾是否为'F'来计算公差,如果开头或结尾为'F'则公差为1,因为开头字母的变化只会造成第一个与第二个的贡献变化,变化值为1,所以开头的连续'F'子串的公差为1。如果开头或结尾不为'F'则公差为2。

代码实现

#include<cstdio>
#include<cstring>
 
const int N = 2*1e5+10;
char line[N], t[N];
 
int main()
{
	int n, begin = 0, end = 0;
	scanf("%d\n", &n);
	scanf("%s", line);
 
	if(line[0] == 'F') {
		int j = 0; char temp;
		while(line[j] == 'F') j++;
		if(j >= n) temp = 'B';
		else temp = line[j];
 
		memcpy(t, line, sizeof(line));
		for(int i=j; i<n-1; i++) {
			if(t[i+1] == 'F') t[i+1] = (t[i] == 'B' ? 'E' : 'B');
			if(t[i] == t[i+1])begin++;
		}
 
		memcpy(t, line, sizeof(line));
		t[0] = temp;
		for(int i=0; i<n-1; i++) {
			if(t[i+1] == 'F') t[i+1] = t[i];
			if(t[i] == t[i+1])end++; 
		}
	}
	else {
		memcpy(t, line, sizeof(line));
		for(int i=0; i<n-1; i++) {
			if(t[i+1] == 'F') t[i+1] = (t[i] == 'B' ? 'E' : 'B');
			if(t[i] == t[i+1])begin++;
		}
 
		memcpy(t, line, sizeof(line));
		for(int i=0; i<n-1; i++) {
			if(t[i+1] == 'F') t[i+1] = t[i];
			if(t[i] == t[i+1])end++;
		}
	}
	int step = (line[0] == 'F' || line[n-1] == 'F') ? 1 : 2, ans=0;
	for(int i=begin; i<=end; i+=step)
		ans++;
	printf("%d\n", ans);
	for(int i=begin; i<=end; i+=step) {
		printf("%d\n", i);
	}
	return 0;	
}
/app/www/public/data/pages/icpc/problems/usaco23open_feb_b.txt · 最后更改: 2023/05/06 08:15 由 温婕莺