首页 > ACM题库 > HDU-杭电 > hdu 2486 A simple stone game-数学相关-[解题报告]C++
2014
01-26

hdu 2486 A simple stone game-数学相关-[解题报告]C++

A simple stone game

问题描述 :

After he has learned how to play Nim game, Mike begins to try another stone game which seems much easier.

The game goes like this: Two players start the game with a pile of n stones. They take stones from the pile in turn and every time they take at least one stone. The one who goes first can take at most n-1 stones for his first move. From then on a player can take at most k times as many stones as his opponent has taken last time. For example, if one player take m stones in his turn, then the other player can take at most k × m stones next time. The player who takes the last stone wins the game. Suppose that those two players always take the best moves and never make mistakes, your job is to find out who will definitely win the game.

输入:

The first line contains a integer t, indicating that there are t test cases following.(t<=20).

Each test case is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).

输出:

The first line contains a integer t, indicating that there are t test cases following.(t<=20).

Each test case is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).

样例输入:

5
16 1
11 1
32 2
34 2
19 3

样例输出:

Case 1: lose
Case 2: 1
Case 3: 3
Case 4: lose
Case 5: 4

题目:hdu 2486 A simple stone game

思路:类似于斐波那契博弈的一个扩展,比较专业的名字叫“k倍动态减法游戏”   百度文库里有一篇专门的论文 再次膜拜
中学生

同时参考了
这里 

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int maxn = 1000010 ;
int a[maxn],b[maxn];
int n,k;
int solve(int n)
{
    int i=0,j=0;
    a[0]=1,b[0]=1;
    while(a[i]<n)
    { // a[i]表示当前能用来构造的最大项
      // b[i]表示由0...i,由a中数列所构成的最大值
        i++;
        a[i]=b[i-1]+1; // b[i-1]+1不能表示成a中的前i-1中某不连续几项的和,故需要构造
        while(a[j+1]*k<a[i])
            j++; // 找到最近的恰好与第i项差值在k倍以上的
        if(a[j]*k<a[i])
            b[i]=b[j]+a[i]; //用到了a中前i-2项,保证和为a中某不连续的话,可以取当前的j
        else // 倒数第二项和最后一项差值恰好为k倍时,能构造的最大项不变
            b[i]=a[i];
    }
    if(n==a[i])
        return -1;
    int ans;
   while(n)
   {
       if(n>=a[i])
            n-=a[i],ans=a[i];
       i--;
   }
   return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d%d",&n,&k);
        int ans = solve(n);
        printf("Case %d: ",cas);
        if(ans==-1)
            printf("lose\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}

解题转自:http://blog.csdn.net/shiyuankongbu/article/details/11647595


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法