hdu 2177 取(2堆)石子游戏（威佐夫博奕）-白红宇

hdu 2177 取(2堆)石子游戏（威佐夫博奕）

阅读量：6947 次

发布时间：2019-06-27

本文共 3165 字，大约阅读时间需要 10 分钟。

　　题目链接：

　　这题不是普通的 Nim 博弈，我想它应该是另一种博弈吧，于是便推 sg 函数打了个 20*20 的表来看，为了方便看一些，我用颜色作了标记，打表代码如下：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
          5 #include
          
            6 #include
           
             7 using namespace std; 8 9 int sg[103][103];10 11 int dfs(int i, int j) {12 if(i > j) swap(i,j);13 if(sg[i][j] != -1 || sg[j][i] != -1)14 return sg[j][i] = sg[i][j];15 16 bool *vis = new bool[103];17 for(int g = 0; g < 103; ++g)18 vis[g] = 0;19 20 for(int x = 1; x <= i; ++x)21 vis[dfs(i - x, j)] = vis[dfs(i - x, j - x)] = 1;22 for(int y = 1; y <= j; ++y)23 vis[dfs(i, j - y)] = 1;24 25 for(int g = 0; ; ++g) {26 if(!vis[g]) {27 delete[] vis;28 return sg[j][i] = sg[i][j] = g;29 }30 }31 }32 33 map
            
              m;34 inline void init() {35 m["blue"] = 1 | FOREGROUND_INTENSITY;36 m["green"] = 2 | FOREGROUND_INTENSITY;37 m["cyan"] = 3 | FOREGROUND_INTENSITY;38 m["red"] = 4 | FOREGROUND_INTENSITY;39 m["pink"] = 5 | FOREGROUND_INTENSITY;40 m["yellow"] = 6 | FOREGROUND_INTENSITY;41 m["white"] = 7 | FOREGROUND_INTENSITY;42 }43 44 HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);45 46 inline void setColor(const string &color) {47 SetConsoleTextAttribute(hConsole, m[color]);48 }49 50 int main() {51 int a,b;52 memset(sg, -1, sizeof sg);53 sg[0][0] = 0;54 55 init();56 printf(" ");57 setColor("yellow");58 for(int i = 0; i <= 20; ++i)59 printf("%2d ",i);60 puts("");61 for(int i = 0; i <= 30; ++i) {62 setColor("yellow");63 printf("%2d ",i);64 for(int j = 0; j <= 20; ++j) {65 if(dfs(i,j) == 0) setColor("red");66 else setColor("white");67 printf("%2d ", dfs(i,j));68 }69 puts("");70 }71 72 puts("");73 setColor("cyan");74 for(int i = 0; i <= 30; ++i)75 for(int j = i; j <= 30; ++j)76 if(dfs(i,j) == 0) printf("%d %d\n",i,j);77 setColor("white");78 79 return 0;80 }

View Code

　　运行结果如下：

　　看不出有什么规律，逐百度之，发现原来是威佐夫博奕，最后判定时需要用到黄金分割数什么的，不过是 O(1) 的复杂度，但杭电这道题还要输出第 1 步操作后的结果，也就是还要模拟一下，不知道它的数据量有多少，觉得直接暴力枚举应该会超时吧，便想写个二分，可是写了好久越写越乱，于是干脆试下暴力，竟然秒过了，后台数据估计少得可怜。需要输出的答案最多不会超过 3 组，但为了方便，我还是用 vector 来存下了符合要求的答案：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 const int N = 1000006; 9 const double p = (sqrt(5.0) + 1) / 2;10 11 bool ok(int a, int b) {12 if(a > b) swap(a,b);13 int k = b - a;14 int c = int(k * p);15 return c == a;16 }17 18 int main() {19 int a,b;20 while(~scanf("%d %d",&a,&b),a) {21 if(a > b) swap(a,b);22 if(ok(a,b)) puts("0");23 else {24 puts("1");25 for(int i = 1; i < a; ++i)26 if(ok(a - i, b - i)) printf("%d %d\n", a - i, b - i);27 vector
            
             
               > v;28 for(int i = 1; i < a; ++i)29 if(ok(a - i, b)) v.push_back(make_pair(a - i, b));30 for(int i = 1; i < b; ++i)31 if(ok(a, b - i)) {32 if(a > b - i) v.push_back(make_pair(b - i, a));33 else v.push_back(make_pair(a, b - i));34 }35 sort(v.begin(), v.end());36 int m = unique(v.begin(), v.end()) - v.begin();37 for(int i = 0; i < m; ++i)38 printf("%d %d\n", v[i].first, v[i].second);39 }40 }41 return 0;42 }

View Code

转载于:https://www.cnblogs.com/Newdawn/p/4914725.html

你可能感兴趣的文章