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; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}