hdu1524博弈SG

hdu1524博弈SG

A Chess Game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1100    Accepted Submission(s): 504

Problem Description
Let’s design a new chess game. There are N positions to hold M chesses in this game. Multiple chesses can be located in the same position. The positions are constituted
as a topological graph, i.e. there are directed edges connecting some positions, and no cycle exists. Two players you and I move chesses alternately. In each turn the player
should move only one chess from the current position to one of its out-positions along an edge. The game does not end, until one of the players cannot move chess any
more. If you cannot move any chess in your turn, you lose. Otherwise, if the misfortune falls on me… I will disturb the chesses and play it again. Do you want to challenge
me? Just write your program to show your qualification!
 

 

Input
Input contains multiple test cases. Each test case starts with a number N (1 <= N <= 1000) in one line. Then the following N lines describe the out-positions of each
position. Each line starts with an integer Xi that is the number of out-positions for the position i. Then Xi integers following specify the out-positions. Positions are
indexed from 0 to N-1. Then multiple queries follow. Each query occupies only one line. The line starts with a number M (1 <= M <= 10), and then come M integers,
which are the initial positions of chesses. A line with number 0 ends the test case.
 

 

Output
There is one line for each query, which contains a string “WIN” or “LOSE”. “WIN” means that the player taking the first turn can win the game according to a clever
strategy; otherwise “LOSE” should be printed.
 

 

Sample Input
4 2 1 2 0 1 3 0 1 0 2 0 2 0 4 1 1 1 2 0 0 2 0 1 2 1 1 3 0 1 3 0

 

 

Sample Output
WIN WIN WIN LOSE WIN

 用SG函数做的:

hdu1524博弈SG
hdu1524博弈SG

 1 #include <iostream>  2 #include <stdio.h>  3 #include <algorithm>  4 #include <string.h>  5 #include <math.h>  6 #include <vector>  7 #include <stack>  8 #include <queue>  9 using namespace std; 10 #define ll long long int 11 vector<int> a[1100]; 12 int z[1100]; 13 int n; 14 int dfs(int x) 15 { 16 if(z[x]!=-1)return z[x]; 17 int size=a[x].size(); 18 int i; 19 int c[n]; 20 memset(c,0,sizeof(c)); 21 for(i=0;i<size;i++) 22  { 23 c[dfs(a[x][i])]=1; 24  } 25 for(i=0;i<n;i++) 26 if(!c[i]) 27  { 28 z[x]=i; 29 break; 30  } 31 return z[x]; 32 } 33 int main() 34 { 35 while(cin>>n) 36  { 37 bool b[n]; 38 memset(z,-1,sizeof(z)); 39 memset(b,0,sizeof(b)); 40 int i,j,m,x; 41 for(i=0;i<n;i++) 42  { 43  a[i].clear(); 44 cin>>m; 45 for(j=0;j<m;j++) 46  { 47 cin>>x; 48  a[i].push_back(x); 49 b[x]=1; 50  } 51  } 52 for(i=0;i<n;i++) 53  { 54 if(!b[i]) 55  dfs(i); 56  } 57 while(cin>>m&&m) 58  { 59 int sum=0; 60 for(i=0;i<m;i++) 61  { 62 cin>>x; 63 sum^=z[x]; 64  } 65 if(sum) 66 cout<<"WIN"<<endl; 67 else cout<<"LOSE"<<endl; 68  } 69  } 70 }

View Code

 

 

 

转载于:https://www.cnblogs.com/ERKE/p/3263476.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110045.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • thinkphp5中的配置如何使用

    thinkphp5中的配置如何使用

  • 新手小白学电脑_新手小白开公司

    新手小白学电脑_新手小白开公司1set接口1.1 概述Set是一个不包含重复数据的CollectionSet集合中的数据是无序的(因为Set集合没有下标)Set集合中的元素不可以重复–常用来给数据去重1.2 Set集合的特点数据无序且数据不允许重复HashSet:底层是哈希表,包装了HashMap,相当于向HashSet中存入数据时,会把数据作为K,存入内部的HashMap中。当然K仍然不许重复。TreeSet:底层是TreeMap,也是红黑树的形式,便于查找数据1.3 常用方法学习Collecti

  • Expected BEGIN_ARRAY but was BEGIN_OBJECT at line 1 column 21 path $.data

    Expected BEGIN_ARRAY but was BEGIN_OBJECT at line 1 column 21 path $.data

  • 模逆矩阵「建议收藏」

    模逆矩阵「建议收藏」整数a对同余n之乘法模逆元是指满足以下公式的整数b乘法模逆元又称为数论倒数,其实可以看作是普通倒数在模算术中的推广。同理,乘法模逆矩阵可以看作是普通逆矩阵在模算术中的推广。例如求如下矩阵K的模26的乘法逆此时,求逆矩阵的如下公式依然有效,不过,里面的符号含义要推广到模算术中:这里,ad-bc=3×5-2×3=9,的含义不再是普通的倒数,而是数论倒数所以…

  • txs0108 替代芯片_什么是芯片,怎么造出来的

    txs0108 替代芯片_什么是芯片,怎么造出来的TXS0108双向电压转换芯片用于IIC时的问题TXS0108是双向电平转换芯片,在我的案例中用于1.8V电平与3.3V电平的转换。最先,我在3.3V和1.8V的SCL和SDA总线上均使用了4.7kΩ的上拉电阻,上拉到对应的高电平。调试发现SDA出现如下波形:可以看到图上出现了次高电平。非常不正常。分析后发现,中间四个次高电平都是IIC芯片发出的ACK信号,应该被拉低,但是并没有拉低到0V。导…

  • wake on lan 远程唤醒/远程开机中的所有设置细节(arp静态绑定解决长时间关机无法唤醒)

    wake on lan 远程唤醒/远程开机中的所有设置细节(arp静态绑定解决长时间关机无法唤醒)远程开机这个功能实在屌爆了,工作中会经常遇到需要远程开机的情景,比如说,晚上在家里,突然接到领导的电话需要改东西,然而家里的电脑又没有工作环境,各种工具软件都没有安装,这时如果往公司跑一趟真是麻烦,或者需求等不及你往公司跑一趟,也许这途中公司会损失更多。或者,晚上在家里工作了,第二天忘记把资料带回公司,这时远程开机也显得尤为重要。总之,如果你有远程办公的需求,就会用到远程开机。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号