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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

bjfu-1100 圆环  

2012-12-11 17:16:16|  分类: ACM-bjfu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

圆环

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:30            测试通过:11

描述

一个圆环上有n个位置,这n个位置按顺时针依次标号为1, 2, …, n。初始时圆环的每个位置上都有一个1至n之间的整数,且每个整数只出现一次。

任何时刻,你可以将圆环上的数全部逆时针旋转一个位置,即第i个位置上的数变为原来第i + 1个位置上的数,第n个位置上的数变为原来第1个位置上的数。也可以将圆环上的数全部顺时针旋转一个位置,即第i个位置上的数变为原来第i ? 1个位置上的数,第1个位置上的数变为原来第n个位置上的数。另有一个装置,可以交换圆环上第a个位置和第b个位置上的数。

下图给出了三种操作的示例,圆环上有6个位置,初始数字分别为1, 2, 4, 3, 5, 6,能交换第2个和第3个位置上的数。经过一次逆时针旋转后变为2, 4, 3, 5, 6, 1,交换后变为2, 3, 4, 5, 6, 1,再经过一次顺时针旋转后变为1, 2, 3, 4, 5, 6。

请问通过旋转和交换,能否使得第i个位置上的数正好是i。

输入

输入包含多组数据。

每组数据的第一行包含一个整数n,表示圆环上的数字个数。

第二行包含两个整数a, b(1 ≤ a < b ≤ n),表示可以交换圆环上第a个位置和第b个位置上的数。

接下来n行描述圆环上每个位置的初始值,其中第i行包含一个整数ai,表示初始时刻第i个位置上的数。

最后一组数据之后的一行为一个0,表示输入结束。

输出

对于每个测试用例,输出一行,如果能满足要求,这行中应只包含一个单词Yes,如果不能满足要求,这行中应只包含一个单词No。

样例输入

6
2 3
1
2
4
3
5
6
4
1 3
1
2
4
3
0

样例输出

Yes
No

提示

对于100%的数据,1 ≤ n ≤ 1,000。

题目来源

Baidu Astar 2011

————————————————————————————————

这是一道2011年百度之星的题目(圆环)

刚开始解的时候,想拿abs(b-a)对n个数进行dfs,但是发现打不下去,即使打出来也会超时。。。。

一时间没想到什么解法,然后搜了下,但是都只有代码,木有解题思路(可能是自己太水了吧。。。)

看到大家贴的代码都差不多,

就是判断 k=gcd(n,abs(b-a)), k==1?,如果成立就输出Yes,否则需要判断以k为间隔将序列分成的k个集合,每个集合里每个元素对k取余的值是否是一样的,一样则输出Yes,否则输出No。

仔细想了下,发现这个想法成立,推导如下:

首先可以把问题转换成这样:令t=abs(b-a),对给出的序列,可以任意交换相隔t个数的两个数,看交换后能否使得序列满足条件。

接着,可以发现能交换的数其实是可以组成一个或者若干个个集合的,集合里的任意两个数可以随意交换;

当k==1时,n个数只能组成一个集合,根据上面的结论,集合里的任意两个数可以随意交换,而现在n个数都在一个集合里,自然可以组成任意的序列了,满足条件;而如果不满足k==1这个条件的话,那么n个数可以组成k个集合,需要继续分别判断这k个集合,每个集合里的元素对k取余的值如果一致,则满足条件,否则不能组成题目给定的序列。

举几个例子就能发现该规律:

例如当n=6,t=4时,1,2,3,4,5,6

因为t=4,则1可以和5交换,5可以和3交换,3可以和1交换,即有1,5,3组成一个集合A;

另外,2可以和6交换,6可以和4交换,4可以和2交换,即有2,6,4组成一个集合B。

n个数分成2个集合,集合A内的三个数可以任意交换,集合B内的三个数可以任意换,不能组成题目要求的序列。


又如当n=6,t=5时,1,2,3,4,5,6

因为t=5,则1可以和6交换,6可以和5交换,5可以和4交换,4可以和3交换,3可以和2交换,2可以和1交换,即有1,6,5,4,3,2组成一个集合A。

n个数组成一个集合A,集合A内n个数可以任意交换,自然能够组成题目要求的序列。


再如当n=6,t=2时,3,2,1,4,5,6

求得k等于2,则需要进一步判断,讲原序列分为2个集合A{3,1,5}和B{2,4,6},发现集合A里每个元素对k取余都是1,集合B里则是0,所以满足条件。

/*
* fudq.cpp
*
* Created on: 2012-12-11
* bjfuoj-1100
*/
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
#define N 1010
int f[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testin.txt","w",stdout);
#endif
int i,a,b,n,f[N];
while(scanf("%d",&n)!=EOF && n)
{
scanf("%d%d",&a,&b);
for(i=0;i<n;i++)
scanf("%d",&f[i]);
int tmp=gcd(n,abs(a-b));
if(tmp == 1)
printf("Yes\n");
else
{
int p=f[0]%tmp;
for(i=1;i<n;i++)
{
if(f[i]%tmp != (i+p)%tmp)//如果当前值对tmp取余 等于 第0项+当前位置对tmp取余,则符合
break;
}
if(i == n)
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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