自动搬运

查看原文

来自洛谷，原作者为

	Zskioaert1106 值得一提的是，我在四个洛谷有 Remote Judge 的国外 OJ 上的账号都不是我的洛谷用户名。

搬运于2025-08-24 23:16:50，当前版本为作者最后更新于2025-05-26 20:49:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门：P12612 [CCC 2025 Junior] Sunny Days

坑坑坑。

做题过程

不难想到简单的贪心：如果两段 $\texttt S$ 之间只隔有一个 $\texttt P$，则可以将这两段合并。于是我们可以用如下方法统计：

• 记 $p$ 代表上一个字符是否是 $\texttt S$，$s1$ 和 $s2$ 分别代表上述两段 $\texttt S$ 的前一段和后一段。

• 若当前元素为 $\texttt S$：
  如果 $p$ 为真，则 $s2 \leftarrow s2+1$；
  否则 $s2$ 初始化为 $1$，$p$ 改为真。

• 若当前元素为 $\texttt P$：
  如果 $p$ 为真，$s1 \leftarrow s2$，将 $p$ 设为假； 否则将 $s1$ 和 $s2$ 同时清零。（两段中间隔了不止一个 $\texttt P$）

每次遇到 $\texttt S$ 都更新答案：$ans = \max(ans,s1+s2+1)$。

好的，这样你可以拿到 $13$ 分了。

我们漏掉了什么？

首先，因为必须修改一位，所以如果全是晴天的话，结果是 $n-1$。

其次，按照上面的算法，如果全是阴雨结果为 $0$，但实际上是 $1$。

没了。

代码实现

#include<iostream>
using namespace std;
int s1,s2,ans;
bool p,p1;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        char a;
        cin>>a;
        if(a=='S'){
            if(p)s2++;
            else s2=1,p=1;
            ans=max(ans,s1+s2+1);
        }
        else{
            p1=1;
            if(p){
                p=0;
                s1=s2;
            }
            else s1=s2=0;
        }
    }
    if(!ans)ans=1;
    if(!p1)ans=n-1;
    cout<<ans;
    return 0;
}

AC 记录。