Description
两个长为n的01串A和B
进行3种操作:
- A循环左移
- B循环右移
- 使一个Bi=1的i所对应的ai值异或1
以最小操作使A变成B
Solution
对于此类问题,因为明确了目标状态
我们的一个套路是求出A中每一位到状态B的代价,去构造最优解
对于整个数组我们枚举一个移动数
然后去观察每一个位上若要达到最终态需要的花费
发现需要进行异或操作的位必须在左移或者右移的过程中异或
所以用stl维护一下,最终统计往右移的最大值和往左移的最大值就可以了
Code
1 |
|
众生之外,此界之中
两个长为n的01串A和B
进行3种操作:
对于此类问题,因为明确了目标状态
我们的一个套路是求出A中每一位到状态B的代价,去构造最优解
对于整个数组我们枚举一个移动数
然后去观察每一个位上若要达到最终态需要的花费
发现需要进行异或操作的位必须在左移或者右移的过程中异或
所以用stl维护一下,最终统计往右移的最大值和往左移的最大值就可以了
1 | #include<bits/stdc++.h> |