P12612 [CCC 2025 Junior] Sunny Days 题解

Zskioaert1106 · 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 记录。