HDU 5754 Life Winner Bo (找规律and博弈)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5754

给你四种棋子,棋子一开始在(1,1)点,两个人B和G轮流按每种棋子的规则挪动棋子,棋子只能往右下方移动,谁最后先挪动棋子到(n,m)位置,谁就胜利。要是两个人都不可能赢,就输出D。

king的情况在纸上模拟了一下,感觉就是当n*m为奇数时先手输,否则就赢。

rook的情况比较简单,相当于在两堆石子中取石子,只能在一堆中取。当n等于m时,先手必败,因为先手怎么取,后手都会跟上取 使得两堆石子相同。

knight的情况也是在纸上模拟了一下,发现4*4  7*7  10*10...这些情况先手都是输,因为先手无论怎走,后手都会调整方向,所以(n == m && (n - 1) % 3 == 0)时,先手输。

还有2*3  5*6  8*9...都是先手赢。其余都是平局。

queen的情况,比赛的时候没发现,原来是威佐夫博弈,问题可以转化为两堆石子,可以从中一堆取,或者从两堆中取同样的数目。具体可以百度一下,套个公式就可以了,注意n和m要减1。

 //#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ; void king(int n, int m) {
if((n * m) % )
printf("G\n");
else
printf("B\n");
} void rook(int n, int m) {
if(n == m)
printf("G\n");
else
printf("B\n");
} void knight(int n, int m) {
if(n < m)
swap(n , m);
if(n == m && (n - ) % == )
printf("G\n");
else if(n - m == && n % == )
printf("B\n");
else
printf("D\n");
} void queen(int n, int m) {
n-- , m--;
double x = ( + sqrt(5.0))/2.0;
if(n < m)
swap(n , m);
if(m == int((n - m)*x))
printf("G\n");
else
printf("B\n");
} int main()
{
int t , n , m , c;
scanf("%d" , &t);
while(t--) {
scanf("%d %d %d" , &c , &n , &m);
if(c == ) {
king(n , m);
}
else if(c == ) {
rook(n , m);
}
else if(c == ) {
knight(n , m);
}
else {
queen(n , m);
}
}
return ;
}
上一篇:python pandas 数据处理


下一篇:C#的默认编码