外面的世界伴奏,8c000002,楚汉传奇虞姬扮演者
洛谷题目页面传送门 & codeforces题目页面传送门
定义一个\(1\sim n\)的排列\(a\)的平方\(a^2=b\),当且仅当\(\forall i\in[1,n],b_i=a_{a_i}\),即\(a^2\)为将\(a\)在\([1,2,\cdots,n]\)上映射\(2\)次所得的排列。现在给定一个\(1\sim n\)的排列\(a\),求\(b\)使得\(b^2=a\),即求\(a\)的平方根。若有多解,输出任意一个。若无解,输出\(-1\)。
\(n\le10^6\)。
看到关于映射的题目,首先想到转化为图论。\(\forall i\in[1,n]\),从\(i\)到\(a_i\)建一条有向边,得到一张有向图\(g=(v=[1,n],e=\{(x,y)\mid a_x=y\})\)。很显然,对于一个排列建出的图一定是由若干个环组成的,因为每个节点的入度、出度均为\(1\)。那么将\(a\)平方之后,每个节点会指向它原来指向的节点原来指向的节点。考虑平方之后每个环会变成什么样子:很显然,若此环大小为奇,则仍然是一个奇环;若此环大小为偶,则会分裂成\(2\)个大小为原来一半的环。
现在我们得到\(a\)的图,需要根据上述变形规律还原出它的平方根。考虑每个环,分\(2\)种情况:
显然,需要合并的情况都是\(2\)个大小相同的环合并,所以不同大小的环是互相独立的,我们可以对于每个大小分别考虑还原。分\(2\)种情况:
每个节点都被访问常数次,所以时间复杂度为\(\mathrm o(n)\)。
下面贴代码:
#include<bits/stdc++.h> using namespace std; #define pb push_back void read(int &x){//快读 x=0;char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); } void prt(int x){//快写 if(x>9)prt(x/10); putchar(x%10^48); } const int n=1000000; int n; int a[n+1];//平方之后的排列 bool vis[n+1];//dfs时的标记数组 vector<int> v;//此scc(环)中的点 void dfs(int x){//dfs if(vis[x])return; vis[x]=true; v.pb(x); dfs(a[x]); } vector<vector<int> > vv;//所有环 vector<int> havsz[n+1];//大小为[i]的所有环的编号 int ans[n+1];//a的平方根 int main(){ read(n); for(int i=1;i<=n;i++)read(a[i]); for(int i=1;i<=n;i++)if(!vis[i]){//找出每个环 v.clear(); dfs(i); if(v.size()&1){//如果是奇环直接自己还原 vector<int> v0(v.size());//还原之后的环 for(int j=0,now=0;j<v.size();j++,(now+=2)%=v.size())v0[now]=v[j]; for(int j=0;j<v.size();j++)ans[v0[j]]=v0[(j+1)%v.size()];//将还原之后的环用排列的形式存到a的平方根里 } else vv.pb(v);//否则存下来等到后面找其他环合并 } for(int i=0;i<vv.size();i++)havsz[vv[i].size()].pb(i); for(int i=2;i<=n;i+=2)//枚举偶数大小 if(havsz[i].size()&1)return puts("-1"),0;//不能两两配对 else for(int j=0;j<havsz[i].size();j+=2){//枚举环对 vector<int> &v0=vv[havsz[i][j]]/*第1个环*/,&v1=vv[havsz[i][j+1]]/*第2个环*/,v2(2*v0.size())/*还原之后的环*/; for(int k=0,now=0;k<v0.size();k++,now+=2)v2[now]=v0[k],v2[now+1]=v1[k]; for(int k=0;k<v2.size();k++)ans[v2[k]]=v2[(k+1)%v2.size()];//将还原之后的环用排列的形式存到a的平方根里 } for(int i=1;i<=n;i++)prt(ans[i]),putchar(' ');//输出答案 return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论