AGC 16 D - XOR Replace

AGC 16 D - XOR Replace

附上attack(自为风月马前卒爷) 的题解

Problem Statement

There is a sequence of length N: a=(a1,a2,…,aN). Here, each ai is a non-negative integer.

Snuke can repeatedly perform the following operation:

Let the XOR of all the elements in a be x. Select an integer i (1≤i≤N) and replace ai with x.
Snuke's objective is to match a with another sequence b=(b1,b2,…,bN). Here, each bi is a non-negative integer.

Determine whether the objective is achievable, and find the minimum necessary number of operations if the answer is positive.

Solution

[ A' = A oplus A_i oplus A \ Rightarrow A' = A_i ]
转化一下思路, 就可以把异或这个东西去掉了, 操作就变成了这样的形式

• (x = A_1oplus A_2oplus cdots oplus A_n)
• (A_p'=x, x = A_p)

就想到一个做法, 对于一个长度为 n 的轮换, 答案是 n 或者 n + 1
但是如何找这个轮换呢?
我想了2个多小时.
并没有想到用图论的做法做.

最后写了写
只有80分(数据水的吓人) .可能是哪里写错了吧.

#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;


/*
A' = A oplus A_i oplus A
A' = A_i
......
对于一个长度为 n 的轮换, 答案是 n 或者 n + 1
*/

const int N = 1e5 + 7;
int A[N], B[N];
int a[N], b[N];

int QuChong(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i += 1)
        if (A[i] != B[i]) a[++cnt] = A[i], b[cnt] = B[i];
    return cnt;
}

map<int, int> S1, S2;
int vis[N], siz[N];

int main () {
    freopen("replace.in", "r", stdin);
    freopen("replace.out", "w", stdout);
    int n;
    int yihuohe = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i += 1) scanf("%d", &A[i]);
    for (int j = 1; j <= n; j += 1) scanf("%d", &B[j]);
    for (int i = 1; i <= n; i += 1) yihuohe ^= A[i];
    int cnt = QuChong(n);
    for (int i = 1; i <= cnt; i += 1) S1[a[i]] = i, S2[b[i]] = i;
    int numdiff = 0;
    for (int i = 1; i <= cnt; i += 1) if (not S2.count(a[i])) numdiff += 1;
    if (numdiff > 1) { printf("-1n"); return 0; }
    int res = cnt;
    int temp = yihuohe, tmp;
    for (int i = 1; i <= cnt; i += 1) {
        if (a[i] == b[i]) continue;
        while (S2[temp] and not vis[S2[temp]]) {
            tmp = temp, temp = a[S2[temp]];
            // printf("get: %d %dn", tmp, S2[tmp]);
            a[S2[tmp]] = tmp, vis[S2[tmp]] = true;
        }
        // for (int i = 1; i <= cnt; i += 1) printf("%d ", a[i]); puts("");
        if (a[i] == b[i]) continue;
        tmp = temp, res += 1, temp = a[i], a[i] = tmp;
    }
    printf("%dn", res);
    return 0;
}