目录

[TOC]

题目链接

题解

可以发现一次操作相当于一次置换

对于每个a上的位置映射到b对应

可以找到置换群中的所有轮换

一个k个元素的轮换需要k+1步完成

那么答案就是边数+轮换数-1

-1的话发现当最一个数为缺少的数时不需吧最后一步换回来

代码

#include<map>

#include<cstdio>

#include<algorithm>

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = gc;

	while(c < '0' || c > '9')c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

	return x * f;

}

void print(int x) {

	if(x < 0) {

		pc('-');

		x = -x;

	}

	if(x >= 10) print(x / 10);

	pc(x % 10 + '0');

}

const int maxn = 1000007;

int a[maxn],b[maxn],c[maxn],d[maxn];

int n;

std::map<int,int>f;

int fa[maxn];

int find(int x) {

	if(fa[x] != x) fa[x] = find(fa[x]);

	return fa[x];

}

int main() {

	n = read();

	for(int i = 1;i <= n;++ i) a[i] = read();

	for(int i = 1;i <= n;++ i) b[i] = read();

	int t = 0;

	for(int i = 1;i <= n;++ i) t ^= a[i];

	a[n + 1] = t;

	t = 0;

	for(int i = 1;i <= n;++ i) t ^= b[i];

	b[++ n] = t;

	for(int i = 1;i <= n;++ i) c[i] = a[i],d[i] = b[i];

	std::sort(c + 1,c + n + 1);

	std::sort(d + 1,d + n + 1);

	for(int i = 1;i <= n;++ i) {

		if(c[i] != d[i]) {

			puts("-1");

			return 0;

		}

	}

	int tot = 0;

	int ans = 0;

	for(int i = 1;i <= n;++ i) {

		 if(a[i] != b[i] || i == n)  {

		 	if(i < n) ans ++;

		  	if(!f[a[i]])f[a[i]] = ++tot;

		  	if(!f[b[i]])f[b[i]] = ++tot; 

		 }

	}

	if(!ans) {

		pc('0');

		return 0;

	}

	for(int i = 1;i <= tot;++ i) fa[i] = i;

	for(int i = 1;i <= n;++ i) {

		if(a[i] != b[i]) fa[find(f[a[i]])] = find(f[b[i]]);

	}

	for(int i = 1;i <= tot;++ i) if(fa[i] == i) ans ++;

	print(ans - 1);

	return 0;

}

巴特西

AGC016D - XOR Replace 置换/轮换

目录

[TOC]

题目链接

题解

代码

最新文章

热门文章

巴特西

AGC016D - XOR Replace 置换/轮换

目录 [TOC]

题目链接

题解

代码

最新文章

热门文章

目录

[TOC]