题目链接：hdu 2177
这题不是普通的 Nim 博弈，我想它应该是另一种博弈吧，于是便推 sg 函数打了个 20*20 的表来看，为了方便看一些，我用颜色作了标记，打表代码如下：
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<algorithm>
#include<windows.h>
using namespace std; int sg[][]; int dfs(int i, int j) {
if(i > j) swap(i,j);
if(sg[i][j] != - || sg[j][i] != -)
return sg[j][i] = sg[i][j]; bool *vis = new bool[];
for(int g = ; g < ; ++g)
vis[g] = ; for(int x = ; x <= i; ++x)
vis[dfs(i - x, j)] = vis[dfs(i - x, j - x)] = ;
for(int y = ; y <= j; ++y)
vis[dfs(i, j - y)] = ; for(int g = ; ; ++g) {
if(!vis[g]) {
delete[] vis;
return sg[j][i] = sg[i][j] = g;
}
}
} map<string, WORD> m;
inline void init() {
m["blue"] = | FOREGROUND_INTENSITY;
m["green"] = | FOREGROUND_INTENSITY;
m["cyan"] = | FOREGROUND_INTENSITY;
m["red"] = | FOREGROUND_INTENSITY;
m["pink"] = | FOREGROUND_INTENSITY;
m["yellow"] = | FOREGROUND_INTENSITY;
m["white"] = | FOREGROUND_INTENSITY;
} HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); inline void setColor(const string &color) {
SetConsoleTextAttribute(hConsole, m[color]);
} int main() {
int a,b;
memset(sg, -, sizeof sg);
sg[][] = ; init();
printf(" ");
setColor("yellow");
for(int i = ; i <= ; ++i)
printf("%2d ",i);
puts("");
for(int i = ; i <= ; ++i) {
setColor("yellow");
printf("%2d ",i);
for(int j = ; j <= ; ++j) {
if(dfs(i,j) == ) setColor("red");
else setColor("white");
printf("%2d ", dfs(i,j));
}
puts("");
} puts("");
setColor("cyan");
for(int i = ; i <= ; ++i)
for(int j = i; j <= ; ++j)
if(dfs(i,j) == ) printf("%d %d\n",i,j);
setColor("white"); return ;
}
运行结果如下：
看不出有什么规律，逐百度之，发现原来是威佐夫博奕，最后判定时需要用到黄金分割数什么的，不过是 O(1) 的复杂度，但杭电这道题还要输出第 1 步操作后的结果，也就是还要模拟一下，不知道它的数据量有多少，觉得直接暴力枚举应该会超时吧，便想写个二分，可是写了好久越写越乱，于是干脆试下暴力，竟然秒过了，后台数据估计少得可怜。需要输出的答案最多不会超过 3 组，但为了方便，我还是用 vector 来存下了符合要求的答案：
#include<cstdio>
#include<cmath>
#include<set>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = ;
const double p = (sqrt(5.0) + ) / ; bool ok(int a, int b) {
if(a > b) swap(a,b);
int k = b - a;
int c = int(k * p);
return c == a;
} int main() {
int a,b;
while(~scanf("%d %d",&a,&b),a) {
if(a > b) swap(a,b);
if(ok(a,b)) puts("");
else {
puts("");
for(int i = ; i < a; ++i)
if(ok(a - i, b - i)) printf("%d %d\n", a - i, b - i);
vector<pair<int,int> > v;
for(int i = ; i < a; ++i)
if(ok(a - i, b)) v.push_back(make_pair(a - i, b));
for(int i = ; i < b; ++i)
if(ok(a, b - i)) {
if(a > b - i) v.push_back(make_pair(b - i, a));
else v.push_back(make_pair(a, b - i));
}
sort(v.begin(), v.end());
int m = unique(v.begin(), v.end()) - v.begin();
for(int i = ; i < m; ++i)
printf("%d %d\n", v[i].first, v[i].second);
}
}
return ;
}