首页 > ACM题库 > HDU-杭电 > HDU 4259-Double Dealing-模拟-[解题报告]HOJ
2015
05-23

HDU 4259-Double Dealing-模拟-[解题报告]HOJ

Double Dealing

问题描述 :

Take a deck of n unique cards. Deal the entire deck out to k players in the usual way: the top card to player 1, the next to player 2, the kth to player k, the k+1st to player 1, and so on. Then pick up the cards �C place player 1′s cards on top, then player 2, and so on, so that player k’s cards are on the bottom. Each player’s cards are in reverse order �C the last card that they were dealt is on the top, and the first on the bottom.
How many times, including the first, must this process be repeated before the deck is back in its original order?

输入:

There will be multiple test cases in the input. Each case will consist of a single line with two integers, n and k (1≤n≤800, 1≤k≤800). The input will end with a line with two 0s.

输出:

There will be multiple test cases in the input. Each case will consist of a single line with two integers, n and k (1≤n≤800, 1≤k≤800). The input will end with a line with two 0s.

样例输入:

1 3
10 3
52 4
0 0

样例输出:

1
4
13

http://acm.hdu.edu.cn/showproblem.php?pid=4259

题意:给你n张卡片, 分给k个人, 从1-n轮流分。 然后,重新把卡片放在一起。第1个人的放在最上边,后面的依次放下面。 再重新分,再放, 问多少次后会回复原样。

Idea:

朴素思想:模拟对每个点进行变换,分别求得周期Ci,然后求他们的最小公倍数。(TLE)

优化:可以得知当某个位置上的卡牌由A变回到A是,会经历一个A->B->C->…->A的密闭循环,这样对于循环内的每个元素,只需要计算其中任一元素即可。

【顺便吐槽下HDU 坑爹的long long 输出,用printf("%lld",ans)一定是WA,无论G++还是C++。然后pirntf("%I64d",ans),cout<<ans;都没事。真TM坑啊,我改了一个多小时就去试出了个这】

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

long long gcd(long long a,long long b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
    freopen("test.txt","r",stdin);
    int N,K;
    while (scanf("%d%d",&N,&K),N|| K)
    {
        static int rec[810][810];
        static int a[810];
        int num = 1;
       for (int i = 1;;i++)
        {
            for (int j = 1;j <= K;j++)
            {
                rec[i][j] = num++;
                if (num >N) break;
            }
            if (num > N) break;
        }
        num = 1;
        for (int i = 1;i <= K;i++)
        {
            for (int j = (N-i)/K+1;j >= 1;j--)
            {
                a[num++] = rec[j][i];
            }
        }

        static bool vd[810];
        memset(vd,0,sizeof(vd));
        long long ans = 1;
        for (int i = 1;i <= N;i++)
        {
            if (vd[i]) continue;
            num = i;
            long long count = 0;
            do
            {
                num = a[num];
                vd[num] = true;
                count++;
            }
            while (num != i);
            ans = ans/gcd(ans,count)*count;
        }
        printf("%I64d\n",ans);
    }

    return 0;
}
/*
        for (int i = 1;i <= K;i++)
        {
            for (int j = (N- i)/K *K + i;j > 0;j -= K)
            {
                a[num++] = j;
            }
        }
*/

Add:位置轮换的原理与实现

a[i] = j;表示的是位置i将被位置j的卡牌所替换;

i<-j <-k;如果要求i变换两次后被那个卡牌所替换,也就是求j一次变换将被哪个卡牌所替换了。当然这里的i,j,k都是第一次的初始位置编号,也可以理解成卡牌。

实现的话,1)main()中用的是先分在倒序读的方法,这样比较直观。

2)看了下其他人的程序,用的都是一步到位的方法,

for (int i = 1;i <= K;i++)

{

 for (int j = (N- i)/K *K + i;j > 0;j -= K)

{ a[num++] = j; }

}

其实只要知道对于第i列,它拥有的元素个数是(N-i)/K +1,就很好理解了

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xdu_truth/article/details/7933410