多边形之战(bzoj 2927)
2024-09-08 07:24:04
Description
多边形之战是一个双人游戏。游戏在一个有n个顶点的凸多边形上进行,这个凸多边形的n-3条对角线将多边形分成n-2个三角形,这n-3条对角线在多边形的顶点相交。三角形中的一个被染成黑色,其余是白色。双方轮流进行游戏,当轮到一方时,他必须沿着画好的对角线,从多边形上切下一个三角形。切下黑色三角形的一方获胜。
注:如果连接一个多边形中任意两点的线段都完全包含于这个多边形,则称这个多边形为凸多边形。
求解任务:
请设计一个程序:
·读入对一个多边形的描述。
·确定先走的一方是否能够获胜。
·将结果输出。
Input
第一行是一个整数, 4 <= n <= 50000。表示多边形的顶点数,多边形的顶点从0到n-1顺时针标号。接着的n-2行描述组成多边形的三角形。第i+1行, 1 <= i <= n-2,有三个空格分隔的非负整数a、 b、 c,它们是第i个三角形的顶点编号。第一个给出的三角形是黑色的。
Output
唯一一行应包含一个单词:
TAK(波兰文“是”),表示先走的一方有必胜策略,或者
NIE(波兰文“否”),表示先走的一方没有必胜策略。
Sample Input
6
0 1 2
2 4 3
4 2 0
0 5 4
0 1 2
2 4 3
4 2 0
0 5 4
Sample Output
TAK
/*
自己手推出来的第一道博弈论
①:如果黑三角形的三条边只有一条是对角线,则先手必胜。
②:如果n是偶数,则先手必胜。
第一条很好理解,下面写一下我倒退的第二条证明过程:
1:设对角线有t1条是三角形上的,t2条不在三角形上 。
2:如果先手必胜,则最后一次取数时,t1=1,t2=0,因为如果t2>0的话,后手的人上一步就一定取m中的。
3:倒数第二次取数,t1=2,t2=0,因为如果t1=1,则后手就取走了。
4:(t1,t2)可等效于(t1,t2%2)
由此一直推可推出如果刚开始的t1+t2是奇数的话,先手必胜,因为t1+t2=n-3,则如果n是偶数,则先手必胜。
*/
#include<iostream>
#include<cstdio>
using namespace std;
int v[];
int main(){
int n,a,b,c,t=;
scanf("%d%d%d%d",&n,&a,&b,&c);
for(int i=;i<=n-;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
v[x]++;v[y]++;v[z]++;
}
if(!v[a])t++;
if(!v[b])t++;
if(!v[c])t++;
if(t==||n%==) printf("TAK");
else printf("NIE");
return ;
}
最新文章
- MMU内存管理单元相关知识点总结
- css文本格式详解
- OceanBase架构(二)
- 【转】设计模式(十一)代理模式Proxy(结构型)
- kaili 2.0 metasploit连接postgres数据库
- [ZOJ 1002] Fire Net (简单地图搜索)
- ASP.NET Session的七点认识
- angular localStorage使用方法
- Gulp自动构建Web前端程序
- C#对图片进行马赛克处理,可控制模糊程度
- 提高运维效率(二)桌面显示IP
- linux服务器添加一块新硬盘不用重新启动机器的操作
- Web测试常见问题点汇总
- 深入学习主成分分析(PCA)算法原理(Python实现)
- glog学习(一):glog的编译及demo
- 【Dubbo&;&;Zookeeper】6、 给dubbo接口添加白名单——dubbo Filter的使用
- Solr之.net操作
- OC侧滑删除
- 【转】XMPP_3920_最靠谱的中文翻译文档
- Anaconda的使用和包的更新;conda 创建虚拟环境