| 题目名称 | 1720. 二分图游戏 |
|---|---|
| 输入输出 | graphgame.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：96， 提交：270， 通过率：35.56% | ||||
 Pepcy_Ch |
100 | 0.047 s | 2.66 MiB | C++ |
 AntiLeaf |
100 | 0.084 s | 2.61 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.085 s | 13.17 MiB | C++ |
 AAAAAAAAAA |
100 | 0.096 s | 0.09 MiB | C++ |
 Shirry |
100 | 0.096 s | 0.09 MiB | C++ |
|
Shirry |
100 | 0.096 s | 0.09 MiB | C++ |
 MistyEye |
100 | 0.098 s | 0.34 MiB | C++ |
 _Itachi |
100 | 0.121 s | 0.16 MiB | C++ |
 Hzoi_moyi |
100 | 0.121 s | 1.79 MiB | C++ |
 沉迷学习的假的Keller |
100 | 0.128 s | 0.33 MiB | C++ |
| 关于 二分图游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Rapiz :
哪有您神orz Shirry
2017-03-23 01:08
10楼
| ||||
|
你们都好神啊
| ||||
|
匈牙利
Shirry
2017-03-23 00:21
8楼
| ||||
|
VIP 一不小心刷榜成功...然而并无任何优化...
沉迷学习的假的Keller
2016-04-04 20:20
7楼
| ||||
|
我是@啊吧啦吧啦吧
| ||||
|
我就是阿拉巴拉巴拉
| ||||
|
| ||||
|
回复 @william :
Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz主DPS  Chenyao2333
2014-10-05 12:04
3楼
| ||||
 Asm.Def
2014-10-05 09:00
2楼
| ||||
|
比赛的时候看错题了，把删点看成删边……成功GG
Orz主DPS @武嘉鑫 | ||||
Rapiz
啊吧啦吧啦吧
_stranger
stdafx.h
cstdio【题目描述】
Nick和Peter在参加计算复杂性理论讲座的时候喜欢玩如下的游戏。他们在一张纸上画出一个无向的二分图G，并在一个顶点放上棋子。之后他们轮流走棋子。Nick先走。
每一步都是将棋子沿着图中的一条边移动。之后，在这一步之前棋子所在的顶点，偕同与之相连的所有边，都被从图中删去。没有边可走的玩家输掉游戏。
给出Nick和Peter画出的图。对图中的每个顶点，计算如果最初将棋子放在这里，谁将会赢。假设Nick和Peter都执行最优策略。
【输入格式】
输入文件的第一行有三个整数n1,n2,m——分别代表二分图左边的顶点数，右边的顶点数，和边数。1<=n1,n2<=500，0<=m<=50000.
接下来m行描述了这些边。每一行有两个数，即该边所连接的左顶点和右顶点。两边的顶点都从1开始标号。
【输出格式】
输出两行。第一行有n1个字符，如果最初把棋子放在左边的第i个顶点，Nick会赢，第i个字符就是'N'，如果Peter会赢就是'P'。第二行以相同的格式输出n2个字符，描述右边n个顶点的必胜者。
【样例输入】
3 3 5
1 1
1 2
1 3
2 1
3 1
【样例输出】
NPP
NPP
【来源】
Andrew Stankevich Contest 21