已通过 100%
思路：
1. 对于 1 的位：答案直接固定为 0
2. 对于 0 的位，则遍历整个操作序列：
i. 变异：由于题目询问的是最少操作次数，因此可以使用变异操作的 0 只需一次操作就能变成 1
ii. 重组：遍历 [l1, r1] [l2, r2] 区间，对对应区间进行一次交换，并与原始值比对，取最小值：
a) sAction[l1 + i] = min(sAction[l1 + i], tAction[l2 + i] + 1)
b) tAction[l2 + i] = min(tAction[l2 + i], sAction[l1 + i] + 1)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
string S, T;
cin >> S;
cin >> T;
int m;
cin >> m;
vector<int> sAction(n + 1, 0x7fffffff);
vector<int> tAction(n + 1, 0x7fffffff);
for (int i = 1; i <= n; ++i)
if (S[i - 1] == '1')
sAction[i] = 0;
for (int j = 1; j <= n; ++j)
if (T[j - 1] == '1')
tAction[j] = 0;
while (m--) {
int action;
cin >> action;
if (action == 0) { // 重组
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
for (int i = 0; i < r1 - l1 + 1; ++i) {
int temp = sAction[l1 + i];
if (tAction[l2 + i] != 0x7fffffff)
sAction[l1 + i] = min(sAction[l1 + i], tAction[l2 + i] + 1);
if (temp != 0x7fffffff)
tAction[l2 + i] = min(tAction[l2 + i], temp + 1);
}
} else { // 变异
int id, x;
cin >> id >> x;
if (id == 0) {
sAction[x] = min(sAction[x], 1);
} else {
tAction[x] = min(tAction[x], 1);
}
}
}
for (int i = 1; i <= n; ++i)
printf("%s%d", i == 1 ? "" : " ", sAction[i] == 0x7fffffff ? -1 : sAction[i]);
puts("");
for (int j = 1; j <= n; ++j)
printf("%s%d", j == 1 ? "" : " ", tAction[j] == 0x7fffffff ? -1 : tAction[j]);
puts("");
return 0;
} 
全部评论
(4) 回帖