hdu1404 博弈

2017年08月27日 14点热度 0人点赞 0条评论
/*
题意:给一个长度不超过6字符的数字字符串。两种操作二选一:
1、把任意一位变成比他本身小的数字。比如205,可以把5变成0,1,2,3,4,成了200,201.so on。
2、把任意一个0后及他本身去掉。比如205,去掉2和他后面的数字变成了2。
问最后去掉数字的算赢。问先手有木有必胜策略。
题解:可以通过SG函数的性质。暴力吧1-1e6每个数字的状态求出来。能一步到达必败状态的都为必胜点。sg[1]明显是必败点,每次从必败点去找。怎么找?
1、可以将每位上的数字+1,直到等于9.
2、如果位数小于6,可在末尾+0.再加上若干数。最后只要知道sg值是0或者1就OK了。
*/
#include
#include
#include
#include
#include
using namespace std;
const int mn=1e6+2;
int sg[mn];
char s[10];
void dfs(int x)
{
    sprintf(s,"%d",x);
    int len=strlen(s),num;
    for(int i=0; i

未经允许不得转载!hdu1404 博弈

update

纸上得来终觉浅, 绝知此事须躬行。