D - Game on a Graph

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]: /images/20220130/e2da733b07974482954719dc54cf42b6.png

发表评论取消回复

表情：

评论列表（有 0 条评论，218人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF862 div2 D. A Wide, Wide Graph

[Problems - Codeforces][] ![d54b2f1d55aa48239a91dc1fcb026829.png][] 思路：因为要我们输出k为1~n的

╰+攻爆jí腚メ/ 2024年03月24日 14:04/ 0 赞/ 92 阅读

相关 A Game

A Game IOI'96 - Day 1 Consider the following two-player game played with a sequence of

￡神魔★判官ぃ/ 2022年09月19日 12:25/ 0 赞/ 187 阅读

相关论文“Trinity: A Distributed Graph Engine on a Memory Cloud”解析

摘要 Trinity是微软亚洲研究院在SIGMOD13上发表的一篇论文，它不是图数据库而是被称之为图数据引擎“Graph Engine”，作者是邵斌等人。Trinity声

港控/mmm°/ 2022年08月06日 08:24/ 0 赞/ 173 阅读

相关 1141A Game 23

A. Game 23 time limit per test 1 second memory limit per test 256 megabytes input

电玩女神/ 2022年03月02日 08:57/ 0 赞/ 239 阅读

相关 D - Game on a Graph

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

水深无声/ 2022年01月30日 08:09/ 0 赞/ 218 阅读

相关 CF1067D Computer Game

[link][] 题意：有 n 道题，每个题可以做很多次但只能领悟一次，一开没有领悟任何题。对于第 i 个题，正确率为 $p\_i$ 。领悟之前，做对这个题

迷南。/ 2022年01月07日 14:19/ 0 赞/ 212 阅读

相关 CUDA Anisotropic Diffusion on a 2D Image

Anisotropic Diffusion有一个重要的应用就是实现Edge-Preserved Blur（保持边缘的模糊），可以用于边缘检测与HDR到LDR的转换。经过测试发现

本是古典何须时尚/ 2021年12月11日 15:31/ 0 赞/ 205 阅读

相关 Playing PC Games on Linux

[http://blog.tangcs.com/2008/01/30/playing-pc-games-linux/][http_blog.tangcs.com_2008_01

偏执的太偏执、/ 2021年11月09日 14:44/ 0 赞/ 151 阅读

相关 D - AB Graph (构造、图)

[题目][Link 1] 思路：分为两种情况： 1.当m为奇数时，直接12121212…构造出的一定是回文。 2.当m为偶数时，可以知道n>=3时一定

不念不忘少年蓝@/ 2021年07月16日 13:14/ 0 赞/ 467 阅读

相关 D. Tokitsukaze, CSL and Stone Game （思维、game）

[题目][Link 1] 思路：先手必输的情况： 1.有两个以上两堆石子数目相同。 2.有3堆以上石子数目相等、有两堆0石子。 3.有一个两堆数

今天药忘吃喽~/ 2021年07月16日 12:13/ 0 赞/ 426 阅读