A Chess Game poj-2425

题目大意题目链接

注释:略。


想法:这个题就是为什么必须要用记忆化搜索。因为压根就不知道后继是谁。

我们通过SG定理可知:当前游戏的SG值等于所有子游戏的SG的异或和。

我们就可以dp了。

最后,附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1010
int sg[N],n,x,ans,m;
int SS[N];
int tot,to[N*N<<1],head[N],nxt[N*N<<1],cnt[N],num;
inline void add(int x,int y) {to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}
int dfs(int pos)
{
if(sg[pos]!=-1) return sg[pos];
bool vis[N];
for(int i=0;i<n;i++) vis[i]=false;
for(int i=head[pos];i;i=nxt[i]) vis[dfs(to[i])]=true;
for(int i=0;;i++) if(!vis[i]) return sg[pos]=i;
}
int main()
{
while(~scanf("%d",&n))
{
memset(sg,-1,sizeof sg);
memset(head,0,sizeof head);
memset(cnt,0,sizeof cnt);
tot=0;
for(int i=0;i<n;i++)
{
scanf("%d",&num);
for(int j=1;j<=num;j++)
{
scanf("%d",&x);
add(i,x);
cnt[x]++;
}
}
for(int i=0;i<n;i++) if(!cnt[i]) sg[i]=dfs(i);
while(scanf("%d",&m)&&m)
{
ans=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
ans^=sg[x];
}
if(ans) printf("WIN\n");
else printf("LOSE\n");
}
}
}

小结:血泪教训:dfs那个vis必须开局部!!不然搜的时候memset全炸了... ...

最新文章

  1. Redis_密码管理(转)
  2. centos 6.5安装node.js
  3. JS实现base64加密解密
  4. JS区别不同浏览器(微信、手机等)
  5. ExtJS笔记2 Class System
  6. iis7.5 应用程序池 经典模式和集成模式的区别
  7. 至芯FPGA培训中心-1天FPGA设计集训(赠送FPGA开发板)
  8. jquery幻灯片--渐变
  9. 一天一个类,一点也不累 之 LinkedList
  10. docker 现实---中小企业docker环境结构(五)
  11. php 生成.txt文件
  12. redis 工具类 单个redis、JedisPool 及多个redis、shardedJedisPool与spring的集成配置
  13. Spring Boot with Spring-Data-JPA学习案例
  14. Django REST framework+Vue 打造生鲜超市(十)
  15. [Swift]LeetCode336. 回文对 | Palindrome Pairs
  16. console.log()中的%d,%s等代表的输出类型
  17. 安装使用阿里云的yum源
  18. super 的用法
  19. postgresql ltree类型
  20. svn 提交代码 自动过滤技巧

热门文章

  1. 同余模定理 HDOJ 5373 The shortest problem
  2. Android内存管理(15)SparseArray系列代替HashMap系列
  3. 转 Shell调试篇
  4. JSP/Servlet Web应用中.properties文件的放置与读取
  5. TFS修改了工作区
  6. php循环结构
  7. 1619. [HEOI2012]采花
  8. Android中出现Error:In (declare-styleable) FontFamilyFont, unable to find attribute android:font
  9. Apache ab使用指南
  10. PHP——基本使用(一)