HDU1210 Eddys 洗牌问题【规律】

题目链接:

?pid=1210

题目大意:

有2*N张牌,初始序列为1、2、3、…、N、N+1、…、2*N-1、2*N。通过一次洗牌可将

牌洗为N+1、1、N+2、2、N+3、3、N+4、4、…、N+N、N。按新的牌序列这样循环

洗牌,最终可将牌洗成初始序列。那么问题来了:给你整数N,问经过多少次可以将牌洗

为初始序列。

思路:

考虑当N = 5的时候,

初始序列为: 1 2 3 4 5 6 7 8 9 10

一次洗牌后: 6 1 7 2 8 3 9 4 10 5

发现1 2 3 4 5的位置都由原来的1 2 3 4 5变为了2 4 6 8 10,即换到2*原来位置的位置。

而6 7 8 9 10的位置都有原来的6 7 8 9 10变为了1 3 5 7 9,即从1开始间隔排列,换到了

(原来位置-N)*2-1的位置。

只考虑1的位置,发现第一次洗牌后:1->2,那么第二次洗牌后1的位置就是初始序列中2

的变化位置:2->4。则1的总体变化位置为1->2->4->8->5->10->9->7->3->6->1

发现:当1的当前位置pos在小于等于N的时候,经过一次洗牌位置变为2*pos,,而在大于N

的时候,经过一次洗牌位置变为(pos-N)*2-1。

用一个循环,找到1从位置1通过循环再次到达位置1的次数,也就是洗牌次数。

AC代码:

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;int main(){int N;while(cin >> N){int pos = 2,times = 1;while(pos != 1){if(pos <= N)pos <<= 1;elsepos = ((pos-N)<<1)-1;times++;}cout << times << endl;}return 0;}

你挤进地铁时,西藏的山鹰一直盘旋云端,

HDU1210 Eddys 洗牌问题【规律】

相关文章:

你感兴趣的文章:

标签云: