题解：P14045 [SDCPC 2019] Game on a Graph

· · 题解

思路

超级大水。建议评红。

因为每个人都会采取最优策略，所以最后的时候输的那一方面对的肯定是一棵树。否则就还能接着删。而我们知道树有 n-1（n 为节点数）条边，所以我们只需要求出第 m-n+1 个人的阵营，那就是输的一方（这时候成为了一棵树）。

要不是不输入完会错，不然我们甚至可以用 O(T) 的时间复杂度就可以通过本题。

代码

#include <bits/stdc++.h>
using namespace std;
void mian()
{
    int k, edge, x, y;
    string s;
    cin >> k >> s >> x >> y;
    for (int i = 1; i <= y; i ++) 
    {
        int xx, yy;
        cin >> xx >> yy;
    }
//核心代码其实就三行：
    edge = y - x + 1;
    if (s[edge % k] == '2') cout << "1" << endl;
    else cout << "2" << endl;
//核心代码结束（其实其他的全是输入）
}
int main()
{
    int T;
    cin >> T;
    for (int i = 1; i <= T; i ++) mian();
    return 0;
}