题解：AT_arc216_a [ARC216A] Reversi 3

· · 题解

更好的阅读方式

显然 A_1\neq B_1\vee A_n\neq B_n 输出 -1。

首先只考虑 A 串的东西，设 a_i=A_i\oplus A_{i-1} 那么若 A_i 可以取反当且仅当 a_{i-1}=a_{i}，取反之后仍有 a_{i-1}=a_i。

但是这样做还不够明显，我们把奇数位的数都给取反（00 变为 10），那这样就好看了，同 A 的东西有 b_i 让所有的 a_i=b_i 的操作次数就是答案。

\mathscr{Code:} 
#include <bits/stdc++.h>

#define LL long long
//#define int LL
#define pb push_back
#define PII pair<int, int>
#define i64 unsigned long long
#define YY puts("Yes"), exit(0)
#define NN puts("No"), exit(0)
using namespace std;
const int Mod = 1e9 + 7;
const int Inf = 0x3f3f3f3f;
const LL InfLL = 0x3f3f3f3f3f3f3f3f;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//#define getchar() gc()
LL read() {
    LL s = 0; char ch = getchar(); bool fu = false;
    while (ch < '0' || ch > '9') ch == '-' ? fu = true : 0, ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return fu ? -s : s;
}

const int N = 1e6 + 10;
int n, a[N], b[N];
char A[N], B[N];

inline void Main() {
    n = read();
    scanf("%s\n%s", A + 1, B + 1);
    if (A[1] != B[1] || A[n] != B[n]) {
        puts("-1");
        return;
    }
    for (int i = 2; i <= n; ++i) {
        a[i] = A[i - 1] ^ A[i];
        b[i] = B[i - 1] ^ B[i];
    }
    a[1] = b[1] = 1;
    vector<int> vec1, vec2;
    for (int i = 1; i <= n; i += 2)
        a[i] ^= 1, b[i] ^= 1;
    for (int i = 1; i <= n; ++i) {
        if (a[i]) vec1.push_back(i);
        if (b[i]) vec2.push_back(i);
    }
    if (vec1.size() != vec2.size()) {
        puts("-1");
        return;
    }
    LL ans = 0;
    for (int i = 0; i < vec1.size(); ++i)
        ans += abs(vec1[i] - vec2[i]);
    printf("%lld\n", ans);
}

signed main() {
//  freopen("input.in", "r", stdin);
//  ios::sync_with_stdio(false);
//  cin.tie(0), cout.tie(0);
    int T = read();
    while (T--)
        Main();
    return 0;
}