【题目链接】:http://codeforces.com/contest/765/problem/D
【题意】
给你一个函数f(x);
要让你求2个函数g[x]和h[x],使得g[h[x]] = x对1..m成立
h[g[x]] = f[x]对1..n成立;
这里
g[x]:[n]->[m];
h[x]:[m]->[n];
让你求h[x]的m的值,顺便输出两个函数的各个值
【题解】
这里要对f(x)做文章;
考虑f(x)==x的情况;
这时要想让
g[h[x]] = x对1..m成立
h[g[x]] = f[x]对1..n成立;
可以新加一个m;
h[++m] = x;
g[x] = m;
这样
g[h[m]] = m
h[g[x]] = x = f(x)
也成立了;
整个程序就以此为发生器;
求出了部分的g函数和全部的h函数(即只有f[x]==x的时候才能得出一个h函数);
之后对于那些还没有得到的g函数;
rep1(i,1,n)
{
if (g[i]!=0) continue;
if (h[g[f[i]]] == f[i])
g[i] = g[f[i]];
else
return puts("-1"),0;
}这里
因为
g[x]:[n]->[m];
h[x]:[m]->[n];
所以h[g[f[i]]]返回的也是一个1..n的值,f[i]也是在1..n;
如果
h[g[f[i]]] == f[i]成立的话;
显然可以让g[i]=g[f[i]];
因为这样
h[g[i]] = f[i]就成立了；
(上面的过程就相当于在构造一个g[i]出来让h[g[i]]=f[i]成立);
而对于g[h[i]]=i (i∈[1..m])这个条件则不用管它了;
因为所有的h数组已经全部知道了,在上面f[i]==i那个判定的时候就已经保证了
g[h[i]]=i是恒成立的了;
脑洞比较大。。想不出来
当时做的时候就想着那么多人AC了;
肯定挺简单的吧;
就随便让g[1]=1,然后以这个为发生器搞整个g和h;
还是太年轻了。
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e6+100;
int n,m;
int f[N],g[N],h[N];
int main()
{
//freopen("F:\\rush.txt","r",stdin);
rei(n);
rep1(i,1,n)
{
rei(f[i]);
if (f[i]==i)
{
//g[h[i]] = i
//h[g[i]] = f[i]
h[++m] = i;
g[i] = m;
}
}
rep1(i,1,n)
{
if (g[i]!=0) continue;
if (h[g[f[i]]] == f[i])
g[i] = g[f[i]];
else
return puts("-1"),0;
}
printf("%d\n",m);
rep1(i,1,n)
{
printf("%d",g[i]);
if (i==n)
puts("");
else
putchar(' ');
}
rep1(i,1,m)
{
printf("%d",h[i]);
if (i==m)
puts("");
else
putchar(' ');
}
return 0;
}