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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4259  

2012-08-25 19:16:37|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这道题是热身赛的一题,热身赛做了一下午,比赛时这题一直超时,结束了还没做出来,最后好好分析了下,发现不需要没次都需要求出序列编号,求出一次即可,改了后就A了
拿10 3这组数据来说
刚开始序列是1 2 3 4 5 67 8 9 10(序列一),
一次变换后变为10 7 4 1 8 5 2 9 6 3(序列二)
实际上只需要知道一次变换后的结果就行了,可以根据这个结果分析出下一次的结果为3 2 1 10 9 8 7 6 5 4 3(序列三)
(可以发现,序列一10对应下面的3就是序列三里的第一个,因此只需要知道一次变换后的结果)
还有一点,每一次循环节里的数的循环次数都是一样的,比如上个例子里,1->4->3->10就是一个循环节,1,4,3,10这四个数的循环次数是一样的;
这样只要求出了所有不同循环次数的最小公倍数就是最后的结果了

/*
* fudq.cpp
*
* Created on: 2012-08-25
*/
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
using namespace std;
#define N 802
int n,k,f[N],a[N][N];
bool vis[N];

void make()
{
int i,j,t,p;
//fuzhi
t=1;
for(i=1;t<=n;i++)
for(j=1;j<=k && t<=n;j++)
a[j][i]=t++;
//gengxin f
p=1;
for(i=1;i<=k;i++)
{
if(i<=n%k)
t=n/k+1;
else
t=n/k;
for(j=t;j>=1;j--)
f[p++]=a[i][j];
}
}

int Do(int u)
{
int p,s=0;
p=u;
vis[u]=true;
while(1)
{
if(p==u && s!=0)
return s;
p=f[p];
vis[p]=true;
s++;
}
}

__int64 gcd(__int64 x,__int64 y)
{
return !y?x:gcd(y,x%y);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int i,t;
__int64 res;
while(scanf("%d%d",&n,&k)!=EOF)
{
if(n==0 && k==0)
break;
if(n<=k)
{
printf("1\n");
continue;
}
memset(vis,false,sizeof(vis));
make();
for(i=1,res=1;i<=n;i++)
{
if(vis[i])
continue;
t=Do(i);
res=res/gcd(res,t)*t;

}
printf("%I64d\n",res);
}
return 0;
}



  评论这张
 
阅读(110)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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