小蓝与忍者游戏 tag 博弈论，贪心，枚举 题意简述 在一个 $n \times m$ 的棋盘上，在 $(1, 1)$ 处有一个棋子，A 和 B 轮流操作，A可以将棋子向下移动或者放弃操作，B可以向右移动或者放弃操作。同时场上存在障碍物，棋子不能移动到障碍物上或者越界。A的目的是最大化移动次数，B的目的是最小化移动次数。当两人在同一回合均放弃操作时，游戏结束。问A的移动次数。 题解思路 A的目的是最大化移动次数，因此A的移动策略一定是能动则动，这样一定是最优的。因此对于A来说，若不考虑列标的影响，A一定会将棋子移动到本列向下的第一个障碍物前或者是边界处。再来分析B，对于B而言，实际上游戏的结束权力在B手上。因为，B可以控制棋子所在的列数，当B移动到第 $y$ 列时，A的结果已经是确定的了，可以用set容器的二分方法二分当前 A 所在的行标直接得到答案。而B最后要最小化棋子移动的次数，那么他一定会在A能移动的最小的一列停下。 因此，我们只需要模拟棋子的移动过程（因为每个回合都一定会让棋子向下和向右移动一个单位，除非有障碍物），然后记录每一列A能移动的次数，取最小值即可。 参考代码 ```cpp void solve() { int n, m, k; cin >> n >> m >> k; vector<set<int>> pos(m + 1); // 记录每一列的障碍物的行标 for(int i = 1; i <= m; i ++) { pos[i].insert(n + 1); // 插入n+1作为每一列的边界 } int ans = 1e9; while(k--) { int x, y; cin >> x >> y; pos[y].insert(x); } int x = 1, y = 1; int last_x = -1; for(int i = 1; i <= n; i ++) { // 如果当前行有障碍物，则移动到障碍物前，答案就是障碍物的坐标-2 // 注意一下，如果列没有发生改变（也就是右边存在障碍物的时候），则答案不变，因为第一次的答案是最大的 if(x != last_x) ans = min(ans, *pos[y].lower_bound(x) - 2); last_x = x; // 模拟移动过程，如果目的地没有障碍物或者越界，则移动 // 注意由于是A先手，因此一定是先移动列（向下），再移动行（向右） if(x + 1 <= n and pos[y].count(x + 1) == 0) x++; if(y + 1 <= m and pos[y + 1].count(x) == 0) y++; } // 最后还有回合结束双方都放弃的操作次数，因此答案要+1 cout << ans + 1 << '\n'; } ```