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_1\oplus A_2\oplus \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("-1\n"); 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 %d\n", 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("%d\n", res);

	return 0;

}

巴特西

AGC 16 D - XOR Replace

Problem Statement

Solution

最新文章

热门文章