好串时间限制1 秒空间限制1024 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述Bingbong 定义一个字符串为好串当且仅当该字符串为10或者01。现在有一个长度为n nn的01 0101字符串s ss他每次操作会执行如下选择一个索引i ( 0 ≤ i n ) i\ (0 \le i n)i(0≤in)若s i ’0’ s_i \texttt{0}si​’0’则将其修改为’1’ \texttt{1}’1’否则修改为’0’ \texttt{0}’0’。现在他想知道至少需要多少次修改才能使得字符串s ss中至少包含三个子串为好串。输入描述本题输入包含多组数据。第一行输入一个整数T ( 1 ≤ T ≤ 10 4 ) T\ (1 \le T \le 10^4)T(1≤T≤104)表示测试数据组数。对于每组数据格式如下第一行输入一个整数n ( 4 ≤ n ≤ 10 6 ) n\ (4 \le n \le 10^6)n(4≤n≤106)表示字符串的长度第二行输入一个长度为n nn的字符串s ss保证输入仅含字符0和1。对于单个测试文件保证所有测试数据组的n nn之和不超过10 6 10^6106。输出描述输出共T TT行每行一个整数表示至少需要多少次修改才能使得字符串s ss中至少包含三个子串为好串。示例示例 1输入2 4 1100 4 0101输出2 0说明对于第一组数据1100可以将其修改为1010此时子串10第1 ∼ 2 1 \sim 21∼2位、01第2 ∼ 3 2 \sim 32∼3位、10第3 ∼ 4 3 \sim 43∼4位均为好串共3 33个好串。需要修改第2 22位和第3 33位共2 22次。对于第二组数据0101字符串中已经包含子串01第1 ∼ 2 1 \sim 21∼2位、10第2 ∼ 3 2 \sim 32∼3位、01第3 ∼ 4 3 \sim 43∼4位共3 33个好串因此不需要修改输出0 00。数据范围与提示1 ≤ T ≤ 10 4 1 \le T \le 10^41≤T≤1044 ≤ n ≤ 10 6 4 \le n \le 10^64≤n≤106所有测试数据的n nn之和不超过10 6 10^6106字符串s ss仅由0和1组成。好串10或01等价于相邻两个字符不同。因此问题可转化为至少修改多少个字符使得字符串中至少存在三个位置i ii满足s i ≠ s i 1 s_i \ne s_{i1}si​si1​。解题思路本题是字符串修改 相邻差异计数的构造题。好串10或01等价于相邻两个字符不同因此目标是在字符串中制造至少三个“相邻字符不同”的位置对。通过统计当前相邻不同对数结合长度限制可以推导出最小修改次数。1. 问题等价转化好串定义10或01即相邻字符不同。目标至少存在三个位置i ii满足s i ≠ s i 1 s_i \ne s_{i1}si​si1​。最小修改次数每次翻转一个字符问最少翻转几次达到条件。2. 长度为 4 的特殊情况当n 4 n4n4时共有3 33个相邻位置对。要至少有3 33个好串意味着所有相邻字符都必须不同即整个字符串必须是交替串0101或1010。因此直接比较原串与这两个目标串的差异字符数取较小值即为答案。3. 长度n ≥ 5 n \ge 5n≥5的一般情况令c n t cntcnt为当前字符串中相邻不同对的个数。若c n t ≥ 3 cnt \ge 3cnt≥3已经满足条件无需修改输出0 00。若c n t 0 cnt 0cnt0字符串全为同一种字符全0或全1。此时一次修改最多只能产生2 22个不同对若修改中间位置仍不足3 33个因此至少需要2 22次修改。两次修改可以做到例如在长度足够的相同串中翻转两个不相邻的位置可产生至少4 44个不同对。所以答案是2 22。若c n t 1 cnt 1cnt1或c n t 2 cnt 2cnt2字符串不是全同且已经有一些不同对。由于n ≥ 5 n \ge 5n≥5一定有连续的相同段。我们可以在某个连续的相同段内部翻转一个字符这样会在该段内部新增两个不同对同时不会破坏已有的不同对。所以只需1 11次修改即可将不同对总数提升到至少3 33。因此答案是1 11。4. 算法步骤读入n nn和字符串s ss。若n 4 n 4n4计算s ss与0101、1010的汉明距离取最小值输出。否则遍历字符串统计c n t ∑ i 0 n − 2 [ s i ≠ s i 1 ] cnt \sum_{i0}^{n-2} [s_i \ne s_{i1}]cnt∑i0n−2​[si​si1​]。若c n t ≥ 3 cnt \ge 3cnt≥3输出0 00若c n t 0 cnt 0cnt0输出2 22否则输出1 11。5. 复杂度分析时间复杂度每组数据O ( n ) O(n)O(n)所有数据n nn之和不超过10 6 10^6106。空间复杂度O ( 1 ) O(1)O(1)额外空间仅需几个变量。总结将“好串”转化为相邻字符不同通过计数当前不同对个数分情况讨论最小修改次数。长度为4 44时需完全交替其余情况最多需要2 22次修改且大部分情况只需0 00或1 11次规律简洁。代码简要说明常量模式预定义p1 0101,p2 1010。每组数据处理若n 4 n4n4分别统计与两个模式不同的字符数输出较小值。否则统计相邻不同对数cnt。按cnt的值输出0、2或1。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;conststring p10101,p21010;while(T--){ll n;string s;cinns;if(n4){ll c10,c20;for(ll i0;i4;i){if(s[i]!p1[i])c1;if(s[i]!p2[i])c2;}coutmin(c1,c2)\n;continue;}ll cnt0;for(ll i0;in-1;i)if(s[i]!s[i1])cnt;if(cnt3)cout0\n;elseif(cnt0)cout2\n;elsecout1\n;}return0;}