pku 2425 A Chess Game (SG)
2024-09-06 02:06:50
题意:
给一个由N个点组成的一张有向图,不存在环。点的编号是0~N-1。
然后给出M个棋子所在的位置(点的编号)【一个点上可同时有多个棋子】。
每人每次可移动M个棋子中的一个棋子一步,移动方向是有向边指向的方向。最后无法移动棋子的人输。
思路:
一眼就可看出的裸的SG,直接看代码吧。
代码:
int sg[1005];
vector<int> graph[1005]; int dfs(int x){ // position x
if(sg[x]!=-1)
return sg[x];
int L=graph[x].size();
if(L==0)
return sg[x]=0;
bool vis[1005] = {0};
rep(i,0,L-1){
vis[dfs(graph[x][i])] = true;
}
for(int i=0;;++i){
if(!vis[i])
return sg[x]=i;
}
} int n,Xi,a,m,pos;
int main(){
while(scanf("%d",&n)!=EOF){
rep(i,0,n-1) graph[i].clear();
rep(i,0,n-1){
scanf("%d",&Xi);
while(Xi--){
scanf("%d",&a);
graph[i].push_back(a);
}
}
mem(sg,-1); while(scanf("%d",&m),m){
int ans=0;
rep(i,1,m){
scanf("%d",&pos);
ans=ans^dfs(pos);
}
if(!ans)
puts("LOSE");
else
puts("WIN");
}
}
}
最新文章
- Your app declares support for audio in the UIBackgroundModes key in your Info.plist 错误
- jquery 抽奖示例
- css3 操作动画要点
- Python使用中文注释和输出中文(原创)
- dp式子100个……
- lucene 3.0.2 search 各种各样的Query类型
- 如何判断一个GPS点是否在以另一个GPS点为圆心100米为半径的圆内(Java代码)
- Java模拟登陆【转载】
- [转载]async &; await 的前世今生
- ModelSim之命令行仿真入门
- vue中的数据监听以及数据交互
- MySql 学习之路-基础
- 7zip 18.3性能测试
- HTML5 &; CSS3初学者指南(4) – Canvas使用
- Asp.Net Core微信服务中间件-.NetCore2.1
- SAP 数据类型
- python学习笔记——fork()创建多进程
- (转)WPF学习资源整理
- 简易的RPC调用框架(大神写的)
- GET 对比 POST
热门文章
- python matplotlib.pyplot 条形图详解
- JSON,XML设计模式详解
- Roslyn(CSharpScript).Net脚本编译引擎使用过程内存增涨与稳定的方式
- 腾讯云启动jenkins
- php 页面公共部分 转化为js document.write(); 并由匿名函数包裹
- P7405-[JOI 2021 Final]雪玉【二分】
- P2179-[NOI2012]骑行川藏【导数,二分】
- P3760-[TJOI2017]异或和【树状数组】
- MFC读写.txt文件时进度条显示实时进度
- 通俗易懂,Layui前端框架!