小蓝与忍者游戏

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能移动的次数，取最小值即可。

参考代码

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';
}