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

思路

超级大水。建议评红。

因为每个人都会采取最优策略，所以最后的时候输的那一方面对的肯定是一棵树。否则就还能接着删。而我们知道树有

n-1

（

n

为节点数）条边，所以我们只需要求出第

m-n+1

个人的阵营，那就是输的一方（这时候成为了一棵树）。

要不是不输入完会错，不然我们甚至可以用

O(T)

的时间复杂度就可以通过本题。

代码

CPP

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

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

文章操作

思路

代码

相关推荐

评论

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