HDU 1524 A Chess Game【SG函数】
2024-10-11 06:01:14
题意:一个N个点的拓扑图,有M个棋子,两个人轮流操作,每次操作可以把一个点的棋子移动到它的一个后继点上(每个点可以放多个棋子),直到不能操作,问先手是否赢。
思路:DFS求每个点的SG值,没有后继的点为必败点。
注意搜索中初始化的问题。
#include<stdio.h>
#include<string.h>
const int N=,M=N*N;
struct node{
int v,next;
}e[M];
int head[N],cnt,in[N],out[N],n,sg[N],p[N];
void add(int u,int v){
e[cnt].v=v,e[cnt].next=head[u];
head[u]=cnt++;
}
int SG(int u){
if(!out[u]) return sg[u]=;
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
if(sg[v]==-) sg[v]=SG(v);
}
memset(p,,sizeof(p));
for(int i=head[u];i!=-;i=e[i].next){
p[sg[e[i].v]]=;
}
for(int i=;i<n;i++){
if(!p[i]){
return sg[u]=i;
}
}
}
int main(){
int m,k,i,u,v;
while(~scanf("%d",&n)){
memset(head,-,sizeof(head));
memset(sg,-,sizeof(sg));
memset(in,,sizeof(in));
cnt=;
for(i=;i<n;i++){
scanf("%d",&k);out[i]=k;
while(k--){
scanf("%d",&v);
add(i,v);in[v]++;
}
}
for(i=;i<n;i++){
if(!in[i]){
SG(i);
}
}
while(~scanf("%d",&m)&&m){
int ans=;
while(m--){
scanf("%d",&u);
ans^=sg[u];
}
if(ans) puts("WIN");
else puts("LOSE");
}
}
return ;
}
最新文章
- atitit.attilax的软件 架构 理念.docx
- linux ssh远程免登陆
- Mac Pro 编译安装 Redis-3.2.3
- vc中获取磁盘IO统计计数
- phpcms的评论改为留言板研究
- 树形DP+二分(Information Disturbing HDU3586)
- 中文系统下,UTF-8编码文本文件读取导致的错误
- UVALive 4223 Trucking 二分+spfa
- App是什么,可以分为几类?及其相关解释。
- PHP提高编程效率的方法,你知道多少呢?
- 云计算之路-阿里云上-容器难容:容器服务故障以及自建 docker swarm 集群故障
- 071、如何定制calico网络的IP池(2019-04-16 周二)
- C++设计模式——访问者模式
- docker常用操作备忘
- BZOJ 2521: [Shoi2010]最小生成树(最小割)
- 利用LVS+Keepalived搭建Mysql双主复制高可用负载均衡环境
- Python 19 Django 详解
- 鸟哥Linux私房菜基础学习篇学习笔记2
- Linux运维之每日小技巧-检测网站状态以及PV、UV等介绍
- udp用户数据报协议
热门文章
- 背水一战 Windows 10 (37) - 控件(弹出类): MessageDialog, ContentDialog
- 【Java每日一题】20161213
- luogg_java学习_09_泛型_集合
- css3相册图片3D旋转展示特效
- 原生JS:JSON对象详解
- Android开发重点难点1:RelativeLayout(相对布局)详解
- SharePoint 2013 安装中间出错了怎么办? 每一次安装都是一段曲折的路【1603(0x643) 】
- 列表屏幕(List Screen)
- Java—字符串小结
- app:clean classes Exception