题解：P10841 【MX-J2-T2】Turtle and Strings

Fur_Zes · 2024-08-04 19:39:18 · 题解

简单贪心。

其他的题解已经有证明过前后字符相同的话就一个取一一个取二，这里给一种更简单的程序实现。

既然已知了规律，那我们直接按照上面的写就好了，不用像其他题解一样记录上一个区间是否和当前区间相同：先取单个字符 s_i，然后看 s_i=s_{i+1} 是否成立，如果成立的话我们可以直接把 s_{i+1} 和 s_{i+2} 当成一个区间，然后 s_{i+3} 仍然按照前面的方法取单个字符。

正确性显然，s_{i+1} 和 s_{i+2} 组成的区间与 s_{i+3} 不可能相同，所以并不需要记录上一区间进行比较，直接取就好。

#include<bits/stdc++.h>
using namespace std;
int t,n;
string s;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>s;
        int ans=1,j=0;
        for(int i=1;i<n;i++)
        {
            if(j>0) ans++,j--;
/*
照应下面 j=2，在 j=2 的时候就是到了长度为 2 的区间的最后一个字符时 ans+1，
在 j=1 的时候就是长度为 2 的区间后边跟着取一个长度为 1 的区间，
最后我们在判断是否能取到长度为 1 的区间。
*/
            else
            {
                if(s[i]==s[i-1]) j=2;
                else ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

这里还有 @saixingzhe 大佬给出的更简洁的代码，思路基本一样，就是如果前后字符相同就合并为长度为二的区间，同时答案减 1，这里设初始的答案为字符串的长度 n，表示最优情况下整个字符串都可以拆分成长度为 1 的区间。

#include<bits/stdc++.h>
using namespace std;
int T,n;
string s;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>s;
        int ans=n;
        for(int i=1;i<n;i++)
        if(s[i]==s[i-1]) ans--,i+=2;
        cout<<ans<<endl;
    }
    return 0;
}