洛谷 P4136：谁能赢呢？← 棋盘配对博弈（多米诺覆盖博弈）

【题目来源】https://www.luogu.com.cn/problem/P4136【题目描述】小明和小红经常玩一个博弈游戏。给定一个 n×n 的棋盘一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合选手只能把石头向上下左右四个方向移动一格并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头而且两个选手都以最优策略走步问最后谁能赢【输入格式】输入文件有多组数据。输入第一行包含一个整数 n表示棋盘的规模。当输入 n 为 0 时表示输入结束。【输出格式】对于每组数据如果小明最后能赢则输出 Alice否则输出 Bob每一组答案独占一行。​​​​​​​【输入样例】20​​​​​​​【输出样例】Alice​​​​​​​【数据范围】对于 20% 的数据保证 1≤n≤10对于 40% 的数据保证 1≤n≤1000对于 100% 数据保证 1≤n≤10000。【算法分析】● 采用棋盘配对博弈多米诺覆盖博弈分析1n 为偶数整张 n*n 棋盘可以完美被若干 1*2 骨牌铺满。先手随便走入某一块骨牌的其中一格后手都可以走到同一块骨牌剩下的另一格。无论先手怎么走后手永远有格子可走最终先手一定会先无路可走 → 先手败后手必胜。2n 为奇数去掉起点格子后剩余棋盘恰好可以被 1*2 骨牌完美覆盖。先手第一步占据中心 / 起点后后手走入任意骨牌一格先手都能对应走到骨牌另一格后手率先无路可走 → 后手败先手必胜。简化判定规则n为偶数先手赢n为奇数后手赢。【算法代码】#include bits/stdc.h using namespace std; int main() { int n; while(cinn n) { if(n%20) coutAlice\n; else coutBob\n; } return 0; } /* in: 2 0 out: Alice */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/163572528https://blog.csdn.net/hnjzsyjyj/article/details/158802453