【题解】洛谷 P9183 [USACO23OPEN] FEB B

本文主要是介绍【题解】洛谷 P9183 [USACO23OPEN] FEB B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - 题目描述
  - 输入格式
  - 输出格式
  - 数据范围
  - 知识点
  - 思路
  - - 结论
    - 证明
  - 代码

P9183 [USACO23OPEN] FEB B

题目描述

贝西和埃尔希正在密谋最终推翻他们的主人——农夫约翰！他们通过 $N$ 条短信进行计划。他们的对话可以用一个长度为 $N$ 的字符串 $S$ 来表示。
其中 $S_i$ 是字母 B或 E，这意味着第 $i$ 条消息分别由贝西或埃尔希发送的。

然而，农夫约翰听说了这个消息，并试图拦截他们的谈话。因此，字符串 $S$ 的一些字母是 F，这意味着农夫约翰混淆了信息，发件人未知（贝西、埃尔希都有可能）。
注：约翰没有发送信息！他只是在干扰奶牛间的通话！

未混淆对话的兴奋程度是一只奶牛重复发送信息的次数。也就是说，子串 BB或 EE在 $S$ 中出现的次数。你想找到原始信息的兴奋程度，但你不知道约翰的信息中哪一条实际上是贝西或埃尔希的。在所有可能的情况下，从小到大输出所有可能的兴奋程度。

输入格式

第一行：一个整数 $N$ （通话长度）。
第二行：一个字符串 $S$ （通话内容）。

输出格式

第一行：输出一个整数 $K$ ，为不同兴奋程度的可能数量。
随后 $K$ 行：每行一个整数，为每种兴奋程度。注意按照从小到大的顺序输出。

数据范围

$\le N \le 2 \times 10^5$ 。

测试点 4~8： $\le 10$
测试点 9~20：无额外限制。

知识点

DFS、找规律、贪心。

思路

结论

通过 DFS 暴力对拍，我们发现答案为一个等差数列。

证明

不妨设整个序列中仅有一个 F。

分类讨论这个 F 的位置。

F 在开头

此时序列形如 Fxxxxxx。

不妨设第二位为 E。

若将 F 变为 E，则对答案的贡献为 $1$ 。
若将 F 变为 B，则对答案无贡献。

F 在中间

此时序列形如 xxxFxxx。

F 两侧字符相同。不妨设该字符为 E，则序列为 xxEFExx。
- 若将 F 变为 E，则对答案的贡献为 $2$ 。
- 若将 F 变为 B，则对答案无贡献。
F 两侧字符不同。不妨设此时序列为 xxBFExx。无论如何替换，对答案的贡献都是 1。因此下面进行贪心时不考虑这种情况。

F 在结尾。这种情况与情况 $1$ （F 在开头）相同。

证毕。得出结论：答案为一个等差数列，且如果字符串首尾至少一个位置是 F，那么等差数列的公差为 $1$ 。如果头和尾都不是 F，那么等差数列公差为 $2$ 。

对于中间的 F，我们考虑贪心求出等差数列首项与末项。

发现 EB 交替放置时方案数最小，即为数列首项。

同理，相邻的 E 或 B 尽量相同时，方案数最大，即为数列末项。

代码

#include <iostream>
#include <cstring>using namespace std;const int N = 300010;int n, hh, tt;
char s1[N], s2[N];int main()
{int sub = 0, hh = 0, tt = 0; // 公差、首项、末项scanf("%d%s", &n, s1);if (s1[0] == 'F' || s1[n - 1] == 'F') sub = 1; // 首尾 -> 公差为 1else sub = 2; // 否则公差为 2while (tt < n - 1 && s1[tt] == 'F') tt ++ ; // 找到第一个不是 F 的位置开始贪心for (int i = 0; i < n; i ++ ) s2[i] = s1[i];for (int i = tt + 1; i < n; i ++ ){if (s1[i] == 'F'){s2[i] = s2[i - 1]; // 最小值尽量相等if (s1[i - 1] == 'E') s1[i] = 'B'; // 最大值尽量交替出现if (s1[i - 1] == 'B') s1[i] = 'E';}if (s1[i] == s1[i - 1]) hh ++ ; // 向首项末项累加答案if (s2[i] == s2[i - 1]) tt ++ ;}int k = (tt - hh) / sub + 1; // 计算等差数列项数printf("%d\n", k);for (int i = hh; i <= tt; i += sub)printf("%d\n", i);return 0;
}