D - Game on a Graph-蒲公英云

D - Game on a Graph

水深无声 2022-01-30 08:09 285阅读 0赞

在这里插入图片描述

Output

For each test case output one line containing one integer. If the 1st group wins, output “1” (without quotes); If the 2nd group wins, output “2” (without quotes).

Sample Input

3
5
11212
4 6
0 1
0 2
0 3
1 2
1 3
2 3
5
11121
5 7
0 2
1 3
2 4
0 3
1 2
3 2
4 1
3
121
4 3
0 1
0 2
1 3

Sample Output

2
1
2

题意：给你一个连通图，按照给定的次序开始割边，谁先让图不连通谁就输了，给定的次序可以循环（这个地方当时没读懂，就gg了）。

思路，不用看连通图的位置，只需要看他有几个点几条边就行，如果把一个连通图分开，把他的边割到n-1条。分析它的必败态，如果割到了只剩下 n-1条边（n个点）这个时候轮到谁割谁就输。如果边的条数正好等于n-1条，那么谁第一个割，谁就必败。本题结束。

AC代码：

#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll k,n,m;
        string s;
        cin>>k;
        cin>>s;
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            ll l,r;
            cin>>l>>r;
        }
        if(n>m)
        {
            if(s[0]=='1')
                cout<<"2"<<endl;
            else    
                cout<<"1"<<endl;
            continue;
        }    
        ll num=(m-n+1)%k;
        if(s[num]=='1')
            cout<<"2"<<endl;
        else    
            cout<<"1"<<endl;    
    }
    return 0;
 }