题解 AT5158 【[AGC037A] Dividing a String】

[更护眼的阅读效果](https://blog.csdn.net/kkkksc03/article/details/105588843)。 ## description - 给定一个字符串 $S$，请你找出一个最大的 $k$，使得将这个字符串划分成 $k$ 段后能够保证相邻的两段不相同。 - $1\le |S| \le 2\times 10^5$，且保证 $S$ 串内均为小写字母。 - translate by @[ShineEternal](https://www.luogu.com.cn/user/45475)。 ## solution 我们贪心的进行划分，每次遇到一个和上一次不一样的串就可以单独提取出来一次了。 ## code ```cpp #include<cstdio> #include<iostream> #include<string> #include<cstring> using namespace std; char s[200005]; int main() { int cnt=0; scanf("%s",&s); int n=strlen(s); string a="",b=""; for(int i=0;i<n;i++) { a+=s[i]; if(a!=b) { b=a; cnt++; a=""; } } printf("%d\n",cnt); return 0; } ```