1 条题解
-
0
首先,虽然我们有很多颗棋子,但我们只需要移动最优的,也就是离某一个边界最近的棋子就行了。因为我只需要把一颗棋子移出去,移动其他的棋子只会减少我去移动最优的棋子的次数,对我是不利的。
现在,假设我把一颗棋子移到了不在角落的边界格上,那对方没有办法,只能把我贴着的这条边界边给拦上,不然下次我移的时候我就出去了。那么他把这条边拦上了,我就向左边或右边一直走,他也只能一路拦。直到我来到了角落的位置,我下一次可以选择两个方向出去,而他只能拦一边,这种时候我就赢了。
那什么样的时候我赢不了呢?就是我最优的棋子也在比较内部的地方,在我把它往最近的边界移的时候,对方有足够的时间把四个角都各封一条边。这需要耗费对方四个轮次,因此,如果最优的棋子和边界边之间隔了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"; } }
信息
- ID
- 78
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 10
- 已通过
- 4
- 上传者