神仙|B2. Tokitsukaze and Good 01-String (hard version) 1800+|算法|c++|cf

传送门
题面描述

文章图片

输入样例

5 10 1110011000 8 11001111 2 00 2 11 6 100110

输出样例

3 2 0 3 0 1 0 1 3 1

题意
给定一个长度为偶数且仅包含0 0 0 和1 1 1 的字符串，每次操作可以任选一个字符并翻转，要求最后该字符串能够划分为若干段，每一段内都是偶数个相同字符，问符合题意的最小操作次数，以及在该操作次数下划分得到的最少段的数量。
结论妙妙题（即使标的知识点是d p dp dp）
由于最终需要形成每一段内为偶数个相同字符，因此可以考虑遍历所有下标为偶数（默认从0 0 0 开始）的字符，并判断该字符是否与后一字符相同。当不相同时，说明需要对这两个相邻字符进行至少一次改动。
例： 111000 111000 111000，最少需要对中间的10 10 10 中选择一个进行翻转，由此可以得到需要的最少操作次数，因为相邻的两个不同一定能够通过翻转一个，使得这两个字符构成一个合法段。
当然，也可能存在类似该情景的特殊情况，如： 001000 001000 001000，在确定了最少操作次数的情况下，该样例可能得到的最少段数量为1 1 1 或2 2 2，具体需要判断其两侧存在的段情况。
由例： 111000 111000 111000 可得，对于中间的10 10 10 字符，可以通过选定翻转字符的方式，令其向前融合（ 111100 111100 111100）或向后融合（ 110000 110000 110000）。容易扩展到，对于任意两个相邻但不相等的字符，一定能够让其融合于任一侧。（不要忘记这两个相邻字符需要满足前一个字符的下标为偶数）
【神仙|B2. Tokitsukaze and Good 01-String (hard version)】因此可以将本题转化为，求字符串中已经固定的不同段的数量。例： 111000011000 111000011000 111000011000，可划分为111000011000 11\ 10\ 00\ 01\ 10\ 00 11 10 00 01 10 00，由于其中01 01 01、 10 10 10 的特殊性，可以先做忽略，得到110000 11\ 0000 11 0000 共两个不同段。

#include #define int long longusing namespace std; vector q; void solve(){ int n,ans=0,cnt=0; cin>>n; string s; cin>>s; q.clear(); for(int i=0; i>T; while(T--) solve(); return 0; }