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 由 温婕莺