codeforces 765 D. Artsem and Saunder(数学题)

时间:2023-03-09 23:04:05
codeforces 765 D. Artsem and Saunder(数学题)

题目链接:http://codeforces.com/contest/765/problem/D

题意:题目中给出你两个公式,g(h(x))==x,h(g(x))==f(x)。现给你f(x)

让你求符合条件的g序列和h序列。

题解:一道数学构造题。

很明显从h(g(x))==f(x),g(h(x))==x,(g(h(x)) 1~m)可以得到h(1~m)要取所有f(x)的值

所以m的值就是f(x)中不重复的值。

然后就是h(x)的取值了,由于取值方法太多所以可能是任意取法都行或者有什么约束条件,不妨

设h(x1)=a , h(x2) = b -> g(a) = x1 , g(b) = x2 -> h(x1)=f(a) , h(x2)=f(b);

又设h(x2) = a , h(x1) = b -> g(a) = x2 , g(b) = x1 -> h(x2)=f(a) , h(x1)=f(b);

可以任意两个位置交换并不影响结果,所以h可以任意取值。所以最后只要取好h然后再给对应的

g附上值然后再利用h(g(x))==f(x)来验证一下就行

#include <iostream>
#include <cstring>
using namespace std;
const int M = 1e5 + 10;
int f[M] , h[M] , g[M] , du[M];
bool vis[M];
int main() {
int n;
cin >> n;
memset(vis , false , sizeof(vis));
memset(g , 0 , sizeof(g));
int m = 0 , count = 0;
for(int i = 1 ; i <= n ; i++) {
cin >> f[i];
if(!vis[f[i]]) {
h[++m] = f[i];
du[f[i]] = m;
vis[f[i]] = true;
}
}
for(int i = 1 ; i <= m ; i++) {
g[h[i]] = i;
}
int flag = 0;
for(int i = 1 ; i <= n ; i++) {
if(g[i]) {
if(h[g[i]] != f[i]) {
flag = 1;
break;
}
}
}
if(flag) {
cout << -1 << endl;
}
else {
cout << m << endl;
for(int i = 1 ; i <= n ; i++) {
if(!g[i]) {
g[i] = du[f[i]];
}
}
for(int i = 1 ; i <= n ; i++) {
cout << g[i] << ' ';
}
cout << endl;
for(int i = 1 ; i <= m ; i++) {
cout << h[i] << ' ';
}
cout << endl;
}
return 0;
}