1 条题解

  • 0
    @ 2022-11-19 20:19:37

    首先,虽然我们有很多颗棋子,但我们只需要移动最优的,也就是离某一个边界最近的棋子就行了。因为我只需要把一颗棋子移出去,移动其他的棋子只会减少我去移动最优的棋子的次数,对我是不利的。

    现在,假设我把一颗棋子移到了不在角落的边界格上,那对方没有办法,只能把我贴着的这条边界边给拦上,不然下次我移的时候我就出去了。那么他把这条边拦上了,我就向左边或右边一直走,他也只能一路拦。直到我来到了角落的位置,我下一次可以选择两个方向出去,而他只能拦一边,这种时候我就赢了。

    那什么样的时候我赢不了呢?就是我最优的棋子也在比较内部的地方,在我把它往最近的边界移的时候,对方有足够的时间把四个角都各封一条边。这需要耗费对方四个轮次,因此,如果最优的棋子和边界边之间隔了4个以上的空白格,我就赢不了了。

    注意这题的数据范围是可能出现棋盘上一颗棋子都没有的情况的。这种时候移棋子的人当然赢不了。

    // Author: yukito8069
    
    //#include <bits/stdc++.h>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    #define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    #define int long long
    typedef long long ll;
    typedef double dd;
    typedef pair<int, int> pii;
    int n, m, k;
    signed main() {
    	IOS;
        cin >> n >> m >> k;
        if(k == 0) {
            cout << "Left one is smarter\n";
            return 0;
        }
        int disr = 2e9, disc = 2e9;
        for (int i = 1; i <= k; i++) {
            int r, c; cin >> r >> c;
            disr = min({n - r, r - 1, disr});
            disc = min({m - c, c - 1, disc});
        }
        if(disr < 5 || disc < 5) {
            cout << "Right one is smarter\n";
        }
        else {
            cout << "Left one is smarter\n";
        }
    }
    
    • 1

    信息

    ID
    78
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    10
    已通过
    4
    上传者