注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 1282  

2010-06-25 13:42:37|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一开始时顺序为1,2,3...n,然后又平p种置换a1,a2...ap问按顺序经过多少次置换可以变为最初的1,2,3...n(当进行第p+1次置换时就是进行第一次置换)
可以认为是进行了k轮p次置换,然后又进行了i次置换(i<p),所以可以先逆向处理出什么顺序可以通过i次置换变为1,2,3...n,然后枚举i
这样问题变为经过多少轮的p次置换可以变成所需序列,求得周期和位置后,这样就可以用同余方程组来解决
#include<cstdio>
#include<cstring>
int a[201][201],b[201][201],c[201][201],d1[201],d2[201],n,m,k,p;
int egcd(int a,int b,int& x,int& y){
if(b==0){
x=1;
y=0;
return a;
}
int t=egcd(b,a%b,y,x);
y-=(a/b)*x;
return t;
}
int solve(int w1[],int w2[],int n)
{
    int x,y,d,t,ret=w1[0],temp=w2[0];
    for (int i = 1; i <n; ++i)
    {
        d = egcd(temp,w2[i],x,y);
        if ((w1[i] - ret) % d != 0)
        {
            return -1;
        }
        t = w2[i] / d;
        x = (x * (w1[i] - ret) / d % t + t) % t;
        ret = x * temp + ret;
        temp = temp * w2[i] / d;
        ret = (ret % temp + temp) % temp;
    }
    return ret;
}
int find(int w1[],int w2[],int k,int &y,int &x){
x=1;
y=-1;
if(k==w2[k])
y=0;
int t=w1[k];
while(t!=k){
if(t==w2[k])
y=x;
t=w1[t];
x++;
}
if(y==-1)
return 0;
return 1;
}
int main(){
scanf("%d%d",&n,&p);
for(int i=0;i<n;++i){
for(int j=0;j<p;++j){
scanf("%d",&a[j][i]);
a[j][i]--;
}
}
for(int i=0;i<n;++i)
b[0][i]=a[0][i];
for(int i=1;i<p;++i)
for(int j=0;j<n;++j)
b[i][j]=a[i][b[i-1][j]];
for(int i=0;i<p;++i)
for(int j=0;j<n;++j)
c[i][b[i][j]]=j;
int mm=100000000;
for(int i=0;i<p;++i){
int mark=1;
for(int j=0;j<n;++j){
mark=find(b[p-1],c[i],j,d1[j],d2[j]);
if(!mark)
break;
}
if(!mark)
continue;
int tt=solve(d1,d2,n);
if(tt!=-1&&tt*p+i+1<mm)
mm=tt*p+i+1;
}
if(mm!=100000000)
printf("%d\n",mm);
else printf("No one knows.\n");
return 0;
}
  评论这张
 
阅读(492)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018