首页 > ACM题库 > HDU-杭电 > HDU 1404 Digital Deletions-字符串-[解题报告] C++
2013
12-09

HDU 1404 Digital Deletions-字符串-[解题报告] C++

Digital Deletions

问题描述 :

Digital deletions is a two-player game. The rule of the game is as following.

Begin by writing down a string of digits (numbers) that’s as long or as short as you like. The digits can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and appear in any combinations that you like. You don’t have to use them all. Here is an example:

On a turn a player may either:
Change any one of the digits to a value less than the number that it is. (No negative numbers are allowed.) For example, you could change a 5 into a 4, 3, 2, 1, or 0.
Erase a zero and all the digits to the right of it.

The player who removes the last digit wins.

The game that begins with the string of numbers above could proceed like this:

Now, given a initial string, try to determine can the first player win if the two players play optimally both.

输入:

The input consists of several test cases. For each case, there is a string in one line.

The length of string will be in the range of [1,6]. The string contains only digit characters.

Proceed to the end of file.

输出:

Output Yes in a line if the first player can win the game, otherwise output No.

样例输入:

0
00
1
20

样例输出:

Yes
Yes
No
No

/*
HDU 1404
*/
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string.h>
using namespace std;

const int MAXN=1000000;
int sg[MAXN];
int get_length(int n)//得到整数n的位数 
{
    if(n/100000) return 6;
    if(n/10000) return 5;
    if(n/1000)  return 4;
    if(n/100)   return 3;
    if(n/10)  return 2;
    return 1;
}    

void _extend(int n)//sg[n]=0;表示n为后者必胜
                   //那么所以可以一步变成n的都是前者必胜 
{
    int len=get_length(n);
    int i;
    for(i=len;i>=1;i--)//每一个位上加上一个数 
    {
        int m=n;
        int base=1;
        for(int j=1;j<i;j++)  base*=10;
        int tmp=(m%(base*10))/base;
        for(int j=tmp;j<9;j++)
        {
            m+=base;
            sg[m]=1;//m为前者必胜点 
        }    
    }  
    if(len!=6)//长度小于6,则可以在后面加0开头的
    {
        int m=n;
        int base=1;
        for(int i=len;i<6;i++)
        {
            m*=10;
            for(int b=0;b<base;b++)
                sg[m+b]=1;
            base*=10;
        }    
    }      
}   
void fun()
{
    memset(sg,0,sizeof(sg));
    sg[0]=1;
    for(int i=1;i<MAXN;i++)
    {
        if(!sg[i])  _extend(i);
    }    
}  
int main()
{
    char str[8];
    int n;
    fun();
    while(scanf("%s",&str)!=EOF)
    {
        if(str[0]=='0')  //第一个数字是0,则前者必胜 
        {
            printf("Yes\n");
            continue;
        }    
        int len=strlen(str);//第一个数字非0,再转化成整型数 
        n=0;
        for(int i=0;i<len;i++)
        {
            n*=10;
            n+=str[i]-'0';
        }        
        if(sg[n]) printf("Yes\n");
        else  printf("No\n");
    }    
    return 0;
}

解题报告转自:http://www.cnblogs.com/kuangbin/archive/2011/08/28/2156443.html


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。