POJ2425 A Chess Game(SG函数+记忆化深搜)

时间:2022-11-12 09:11:28

题目链接:传送门

题目大意:

  在一个有N个点的拓扑图上(拓扑图以邻接表的形式输入),放M个棋子(棋子与棋子之间无关,可以重合)。

  两人轮流移动棋子,每次只能移动一个棋子经过一条边。

  问先手是否必胜。

思路:

  因为图是确定的,而且是拓扑图,直接沿着边跑记忆化dfs求每个点的SG值就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set> using namespace std;
const int MAX_N = ; int N, M;
int Edge[MAX_N][MAX_N];
int SG[MAX_N]; int dfs(int u)
{
if (SG[u] >= )
return SG[u];
bool vis[MAX_N];
memset(vis, false, sizeof vis);
for (int i = ; i <= Edge[u][]; i++) {
int v = Edge[u][i];
int x = dfs(v);
vis[x] = true;
}
int g = ;
while (vis[g])
g++;
return SG[u] = g;
} int main()
{
while (~scanf("%d", &N)) {
for (int i = ; i < N; i++) {
SG[i] = -;
scanf("%d", &Edge[i][]);
for (int j = ; j <= Edge[i][]; j++) {
scanf("%d", &Edge[i][j]);
}
}
for (int i = ; i < N; i++)
dfs(i); while (~scanf("%d", &M)) {
if (M == )
break;
int ans = ;
while (M--) {
int cur;
scanf("%d", &cur);
ans ^= SG[cur];
}
if (ans)
puts("WIN");
else
puts("LOSE");
}
}
return ;
}

POJ2425 A Chess Game(SG函数+记忆化深搜)的更多相关文章

  1. poj 3249 Test for Job &lpar;记忆化深搜&rpar;

    http://poj.org/problem?id=3249 Test for Job Time Limit: 5000MS   Memory Limit: 65536K Total Submissi ...

  2. POJ 2311 Cutting Game(Nim博弈-sg函数&sol;记忆化搜索)

    Cutting Game 题意: 有一张被分成 w*h 的格子的长方形纸张,两人轮流沿着格子的边界水平或垂直切割,将纸张分割成两部分.切割了n次之后就得到了n+1张纸,每次都可以选择切得的某一张纸再进 ...

  3. HDU 5724 Chess(SG函数)

    Chess Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submi ...

  4. HDU 5724 Chess(SG函数&plus;状态压缩)

    http://acm.split.hdu.edu.cn/showproblem.php?pid=5724 题意: 现在有一个n*20的棋盘,上面有一些棋子,双方每次可以选择一个棋子把它移动到其右边第一 ...

  5. 2016多校联合训练1 B题Chess &lpar;博弈论 SG函数&rpar;

    题目大意:一个n(n<=1000)行,20列的棋盘上有一些棋子,两个人下棋,每回合可以把任意一个棋子向右移动到这一行的离这个棋子最近的空格上(注意这里不一定是移动最后一个棋子),不能移动到棋盘外 ...

  6. P4363 &lbrack;九省联考2018&rsqb;一双木棋chess(对抗搜索&plus;记忆化搜索)

    传送门 这对抗搜索是个啥玩意儿…… 首先可以发现每一行的棋子数都不小于下一行,且局面可由每一行的棋子数唯一表示,那么用一个m+1进制数来表示当前局面,用longlong存,开map记忆化搜索 然后时间 ...

  7. POJ-3635 Full Tank&quest; (记忆化广搜)

    Description After going through the receipts from your car trip through Europe this summer, you real ...

  8. HDU 5724 Chess (sg函数)

    Chess 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5724 Description Alice and Bob are playing a s ...

  9. POJ 2425 A Chess Game 博弈论 sg函数

    http://poj.org/problem?id=2425 典型的sg函数,建图搜sg函数预处理之后直接求每次游戏的异或和.仍然是因为看不懂题目卡了好久. 这道题大概有两个坑, 1.是搜索的时候vi ...

随机推荐

  1. radio值未出现JQ获取值问题

    $('input:radio[name="modelExtend.manageType"]:checked').val(); 选中的获取的值不是空或者null而是on

  2. webbench 压力测试

    原文 webbench最多可以模拟3万个并发连接去测试网站的负载能力,个人感觉要比Apache自带的ab压力测试工具好用,安装使用也特别方便,并且非常小. 主要是 -t 参数用着比较爽,下面参考了张宴 ...

  3. 算法与数据结构之顺序查找(C语言)

    #include<stdio.h> #include<stdlib.h> //顺序查找基本思想:从线性表的一端开始,逐个检查关键字是否满足给定的条件 int Sequentia ...

  4. 省略号 对单行 多行的css

    .twoline{ display: -webkit-box !important;; overflow:hidden; text-overflow: ellipsis; word-break: br ...

  5. Jquery 移除 html中绑定的onClick事件

    HTML绑定示例: <button class="edit" onClick="showTurnEdit(this)">编辑</button& ...

  6. Swift - 使用UIScrollView实现页面滚动切换

    UIScrollView提供了以页面为单位滚动显示各个子页面内容的功能,每次手指滑动后会滚动一屏的内容.   要实现该功能,需要如下操作: 1,将UIScrollView的pagingEnabled属 ...

  7. javascript 正则test、exec、search、match区别?

    都可以放正则表达示 exec是RegExp类的匹配方法 match是字符串类的匹配方法 test() 方法用于检测一个字符串是否匹配某个模式.返回 true,否则返回 false. var resul ...

  8. IT江湖--这个冬天注定横尸遍野

    今年江湖大事繁起,又至寒冬,冻的不仅是温度,更是人心. 这两天上班途中看到多个公众号和媒体发了很多 "XXX公司裁员50%" 等等诸如此类的文章,也真是撼动人心.寒冬,比以往来的更 ...

  9. python——虚拟环境之virtualenv(windows10&comma;64位)

    1 问题 当我们拥有两个甚至多个项目A.B.C......,各个项目正常运行需求的python运行环境都不相同.而默认情况下,不管哪个项目,使用的都是全局的Python环境.上述情况,造成的问题就是, ...

  10. JS基础:(一)

    开发了很多项目,感觉javascript脚本语言用处太大了,所以,把一些心得写出来,尤其是调试的技巧. 本次开发工具:Webstorm 1.  官网:http://www.jetbrains.com/ ...