P11361 [NOIP2024] 修改字符串
标题粗心
具体标题传送门
两个 \(01\) 串,能够对两个串中恣意相邻的字符进行交流,没有价值能够进行恣意屡次。但是两个串有的方位的字符是定死的,无法被交流,求恣意次操作后最多让两个串的多少个方位 \(01\) 持平。即 \(\sum [a_i=b_i]\)。
\(n\leq 10^5\)
思路
首要依据冒泡排序的性质,假定 \([l,r]\) 内的一切字符都能够被交流,那么这儿的一切字符能够排成恣意一个摆放。
然后咱们就能够将本题转成将两个串分红一些连通块,上下摆放,每个块内能够依照恣意次序进行摆放,求最多持平。
感觉就像是能够贪心的姿态。先去考虑能不能假定固定一个串,只动第二个。发现显着不可,如果是形如