题解：P11361 [NOIP2024] 编辑字符串

考场上写这题也是花了4h，并且还有bug，实在找不出来了，只有多余的时间去写一个15分的暴搜，光荣退役，终于又在车上面想到了bug点。考场写了300+行4.4kb的代码还是寄了。

这题可以先把所有不能换的位置用两个数组存起来，再递推求解。

具体地，用四个变量分别存储s1、s2中尚未配对的1、0的数量，先赋初值，循环遍历不能换的位置，用两个变量指针指向目前两个数组分别到达了哪个不能换的位置，并且判断哪个位置此时在前面，再用位置靠前的一个对应的未配对1、0的数目和位置靠后的数目配对，累加计算入答案，同时保留靠后的位置对应的剩余0、1数量，将靠前位置的剩余0、1数量重新赋值（即对应序列中下一个不能换的位置和当前位置之间的数量）重新比较重复以上过程。如果遇到两个序列位置相同，则可以直接计算加答案并同时跳到下一个位置

当循环遍历到其中仅有一个序列（不妨设为s2)已经遍历完所有不能换的位置时，可将s1目前遍历到的位置记录并记录未使用的0、1数，易知该位置在s2最后不能换的位置之后，可以此时记录s2剩余所有0、1的数量，由于s1中在目前遍历到位置之前的0、1数可能很多，但最多只能在s2最后不能换的位置和s1当前的位置之间自由配对，因此需要依据s1剩余0、1数量多少、s2最后0、1数量多少以及之间的空间长度分配0、1的匹配，匹配累加答案后再把s2匹配后剩余的0、1数和s1最后剩余的0、1数自由匹配，注意到s1在此时遍历到的位置之后可能还有不能换的位置，但由于交换次数无限制，s2剩余0、1在数量允许的情况下可全部用于与s1剩余数量配对。

当两个序列都已经遍历完所有不能换的位置时，易知此时必定满足这两个位置相同，因此只要统计两个序列中这两个位置之后的剩余0、1数量并且自由匹配计算最大相同数量累加入答案。

最后输出答案即可，记得要清空。

需要注意的是，如果存在序列全部位置都可以交换，则需要特殊判断处理。

退役！