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)


相关推荐

  • web安全概述_网络安全和web安全

    web安全概述_网络安全和web安全域名什么是域名?域名(DomainName),又称网域,是由一串用点分隔的名字组成的Internet上某一台计算机或计算机组的名称,用于在数据传输时对计算机的定位标识(有时也指地理位置)。例:www.baidu.comDNS什么是DNS?域名系统(DomainNameSystem,缩写:DNS)是互联网的一项服务。它作为将域名和IP地址相互映射的一个分布式数据库,能够使人更方便地访问互联网。DNS使用UDP端口53。当前,对于每一级域名长度的限制是63个字符,域名总长度则不能超过2

  • IOC 控制反转[通俗易懂]

    IOC 控制反转[通俗易懂]SpringFramework概述https://blog.csdn.net/centrl/article/details/115519480通过前面的学习,我们至少已经知道IOC,下面我们就来说说IOC是个什么东西。1.写在前面首先来想一件事,作为程序员,怎么开发程序才最巴适?我觉得最起码有两点:开发简单、升级简单。开发简单,就是我们只管写业务逻辑(培养只会写if-else的程序员)。 升级简单,这里也包含两点:我们使用的技术(可理解为框架)出了什么问…

  • 深度学习是什么

    深度学习是什么[toc]前言加里·卡斯帕罗夫vs深蓝(1997年)1997年,美国IBM公司的“深蓝”(DeepBlue)超级计算机以2胜1负3平战胜了当时世界排名第一的国际象棋大师卡斯帕罗夫

  • 学习 Web 开发技术的16个最佳教程网站和博客

    学习 Web 开发技术的16个最佳教程网站和博客互联网经过这么多年的发展,已经出现了众多的Web开发技术,像.Net/Java/PHP/Python/Ruby等等。对于Web开发人员来说,不管是初学者还是有一定经验的开发人员都需要时刻学

  • 多线程和多进程的差别(小结)

    多线程和多进程的差别(小结)

  • JShell介绍「建议收藏」

    JShell介绍「建议收藏」文章目录一、JShell是什么?二、为什么使用JShell三、使用步骤1.安装jdk9.0以上版本2.cmd命令行中进入JShell3.就可以直接敲击单行代码了引用一、JShell是什么?JavaShell工具(JShell)是用于学习Java编程语言和原型化Java代码的交互式工具。该工具使用命令行运行。二、为什么使用JShell使用JShell,可以一次输入一个程序元素,立即查看结果,并根据需要进行调整。三、使用步骤1.安装jdk9.0以上版本例如我的是15.0版本:2.cm

    2022年10月31日

发表回复

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

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