首页 > ACM题库 > HDU-杭电 > HDU 1517 A Multiplication Game-数论-[解题报告] C++
2013
12-12

HDU 1517 A Multiplication Game-数论-[解题报告] C++

A Multiplication Game

问题描述 :

Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches p >= n.

输入:

Each line of input contains one integer number n.

输出:

For each line of input output one line either

Stan wins.

or

Ollie wins.

assuming that both of them play perfectly.

样例输入:

162
17
34012226

样例输出:

Stan wins.
Ollie wins.
Stan wins.

这道题真的是想了很久,一直束缚在SG函数上了,殊不知有的时候寻找P-position和N-position的规律更加方便。看了大牛的代码,寻找必胜区间,还有就是&位运算把自己搞糊涂了,惭愧。。。。以后判断奇偶数还是用%的好。。。

转自:http://blog.pfan.cn/cruxd/22157.html

 这题好X难。

    题目大概意思是:两人轮流乘一个2-9的数,从1开始乘,求谁的乘积先大于N。

    如果是加法就好做了。凑到剩下的数能整除11,然后对称着加。问题是乘法。

    所以寻找必胜点(段)。以1000为例。

    1000 | 999 … 112 |    若占住999到112,则对手必胜。必须让对手占领此段。

    1000 | 999 … 112 | 111 … 56 |   因此必占段是 111 -? 。如果56被对手占住,则56×2=112,入必败段。问题转化成为占56。

    如此循环。如下 1000 | 999 … 112 | 111 … 56 | 55 … 7 | 6 … 4 | 3 … 1

   仔细考虑端点,我在处理端点情况时想了好久。

    这是我的代码。

/*
  * AUthor:lonelycatcher
  * problem:hdu 1517
  * Type:博弈
  */
 #include <iostream>
 #include<stdio.h>
 #include<cstdlib>
 using namespace std;
 long long  n;
 int main()
 {
     setbuf(stdout,NULL);
     while(cin>>n)
     {
         if(n==1)
         {
             printf("Stan wins.\n");
             continue;
         }
         int steps=0;
         while(n>1)
         {
             steps++;
             if(steps&1)
             {
                 n=(n-1)/9+1;
             }
             else n=(n+1)/2;
         }
         if(steps&1)printf("Stan wins.\n");
         else printf("Ollie wins.\n");
     }
     return 0;
 }

解题报告转自:http://www.cnblogs.com/lonelycatcher/archive/2011/08/20/2147430.html


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3