POJ 1740 A New Stone Game 又是博弈论配对找规律orz 博弈论 规律
2024-08-27 16:04:50
http://poj.org/problem?id=1740
这个博弈一眼看上去很厉害很高大上让人情不自禁觉得自己不会写,结果又是找规律……
博弈一般后手胜都比较麻烦,但是主要就是找和先手的对应关系,依然看了题解……
如果所有石头堆两两配对的话后手对先手的每一步都可以对应走一步,那么此时后手必胜。
如果不是两两配对,先手可以通过一次操作使石头堆两两配对,此时的两两配对局面面对的是后手,所以先手必胜。
不是两两配对时的操作:首先将所有非配对推按大小排序(只有一堆直接取没就可以了);
然后显然不配对的堆数为奇数时,最大堆能把前面的填成两两配对(剩下的扔了)。为偶数时,最大堆留下和最小堆一样多的,然后依然能把剩余的填成两两配对。
太鬼畜了orz
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
using namespace std;
const int maxn=;
int n;
int a[maxn]={};
int main(){
while(~scanf("%d",&n)){
if(!n)return ;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
if(n&)printf("1\n");
else{
sort(a+,a++n);
int f=;
for(int i=;i<=n;i+=){
if(a[i]!=a[i-]){
f=;break;
}
}
printf("%d\n",f);
}
}
return ;
}
最新文章
- [LeetCode] Valid Number 验证数字
- 关于Xcode5的离线帮助
- Delphi IDE 设置
- 开发Android必知的工具
- Python基础:序列(列表、元组)
- JNI环境变量——JNIEnv*的使用 &;&;配置jd环境变量
- JavaScript系列:replace()函数(第二个参数为函数)
- FastDFS的安装配置
- 【转】操作ini文件
- MyException
- UVA 10716 Evil Straw Warts Live(贪心)
- Performing a thread dump in Linux or Windows--reference
- 了解ASP.NET 5
- html 细线表格
- Android View框架总结(二)View焦点
- 第k小整数
- CentOS6.5上安装MySQL
- django模板常用过滤器—add、cut、date
- ubuntu16.04下安装artoolkit5
- 前端路由的两种模式: hash 模式和 history 模式