洛谷 P3024：[USACO11OPEN] Cow Checkers S ← 威佐夫博弈

【题目来源】https://www.luogu.com.cn/problem/P3024【题目描述】有一天Bessie 准备玩一个叫做奶牛跳棋的游戏来挑战 Farmer John。这个游戏的棋盘大小为 M×N。最初棋盘上只有一个棋子在 (X,Y)棋盘的左下角坐标是 (0,0)右上角的坐标是 (M−1,N−1)。每次游戏 Bessie 都是先手之后两个人轮流进行操作。每次操作可以在以下三种移动中选择一种1向左走任意步。2向下走任意步。3向左走 k 步然后向下走 k 步k 为任意能保证不走出棋盘的正整数。首个无法操作的人为败者。游戏共有 T 次每次都会给出一个新的坐标 (X,Y)请输出每一轮胜者的名字。【输入格式】第 1 行两个用空格隔开的正整数代表 M 和 N。第 2 行一个正整数代表 T。第 3 行到第 (T2) 行分别有两个空格隔开的非负整数代表 XY。​​​​​​​【输出格式】共 T 行每一行输出那一轮的胜者。​​​​​​​【输入样例】3 311 1【输出样例】Bessie【数据范围】保证 1≤M,N≤10^60≤XM0≤YN1≤T≤10^3。【算法分析】● “洛谷 P3024 [USACO11OPEN] Cow Checkers S”本质就是威佐夫博弈的“棋盘平移版”。这是因为把两维坐标 (x, y) 看成两堆石子数量棋子在 (x, y)每次可以在以下三种操作中选择一种。1向左走任意步 → x 减小对应从一堆取石子2向下走任意步 → y 减小对应从另一堆取石子3向左走 k 步然后向下走 k 步 → x-k, y-k对应两堆同时取 k 个谁先到 (0,0) 谁赢。● 威佐夫博弈是一种两堆石子的公平组合博弈双方轮流操作既可以从任意一堆取走至少一颗石子也可以从两堆同时取走同等数量的石子取走最后一颗石子者获胜。威佐夫博弈的先手必败态也就是奇异局势可以由黄金分割比φ(1sqrt(5))/2刻画。即对于局面 (a,b)设 a≤b两堆石子的差值为 kb-a若⌊k・φ⌋等于较小数 a则该局面为先手必败态否则先手必胜。●黄金分割比φ 是无理数浮点数无法保存其精确值只能保存近似值。当差值 k 很大时乘法运算会把浮点数的微小固有误差放大。即 k・φ 的浮点计算结果会略低于数学上的真实整数。同时C 强制类型转换long long对浮点数采取直接截断小数部分的规则并不会四舍五入此时就会得到比正确值小 1 的整数造成答案错误WA。因此本题本题采用long double配合sqrtl()提升有效存储位数将误差压缩到不会改变整数部分的范围以此通过全部测试数据。例如k・φ 的数学真值为 100000000.00000000受浮点近似误差影响计算机计算得到 99999999.99999998。此外C 的 (long long) 强制转换直接截断小数部分于是 (long long)(99999999.99999998) 得到 99999999最终算出的 ⌊k・φ⌋ 相比真实数学结果少 1导致判题错误。补充备注该现象不是 double 一定会发生是大数场景下有概率发生。long double 也不是绝对无误差只是本题数据范围下误差不足以改变整数部分。【算法代码】#includebits/stdc.h using namespace std; typedef long long LL; int main() { ios::sync_with_stdio(0); cin.tie(0); int m,n,T; cinmnT; while(T--) { LL a,b; cinab; if(ab) swap(a,b); long double phi(1.0Lsqrtl(5.0L))/2.0L; LL k(LL)((b-a)*phi); if(ka) coutFarmer John\n; else coutBessie\n; } return 0; } /* in: 3 3 1 1 1 out: Bessie */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/163782250https://www.luogu.com.cn/problem/solution/P3024