hdu 1850 题解
2024-08-29 12:03:16
题意:n堆扑克牌,每次可以取走一堆中任意张数的扑克牌,问先手胜利第一步有几种可能。
这一题如果除去后面一问就直接问先手赢还是后手赢,这就是一道简单的 $ NIM $ 博弈问题。
定理
$ \ \ \ \ \ \ \ \ \ NIM $ 博弈先手必胜,当且仅当 $ A_1 xor A_2 xor A_3....xorA_ixor.....A_n \neq 0 $
具体证明李煜东书上有,这里不做阐述。(可用数学归纳法进行证明
在了解到这个定理后我们还要知道一个式子
$ a \ xor \ b =c \ ,b \ xor \ c =a \ ,a \ xor \ c =b \ , $
首先如果当前场面先手必败,那么答案就是 $ 0 $
如果当前场面先手必胜那么 $ A_1 xor A_2 xor A_3....xorA_ixor.....A_n \neq 0 $ ,我们可以假设存在一个 $ A_j $ 使得 $ A_1 xor A_2 xor A_3....xorA_jxor.....A_n = 0 $ 那么我们可以设 $tmp= A_1 xor A_2 xor A_3....xorA_ixor.....A_n \neq 0 $ 就可以得到 $ tmp \ xor A_i= 0 \ xor A_j $ 即 $ tmp \ xor A_i= A_j $ 那么很显然我们就是要去统计有多少个合法的 $ A_j $那么依据题意我们知道保证 $ A_i > A_j $ 即可。
代码
#include<bits/stdc++.h>
using namespace std;
int n,a[110];
int main(){
while(scanf("%d",&n)&&n){
int tmp=0,ans=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
tmp^=a[i];
}
for(int i=1;i<=n;++i){
if(a[i]>(tmp^a[i])) ans++;
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- SqlHelper类
- ORACLE10g创建表空间,角色与授权
- STM32F103xx bxCAN(Basic Extended CAN) 滤波机制
- NUC_HomeWork1 -- POJ1088(DP)
- Java [Leetcode 118]Pascal&#39;s Triangle
- 【WinForm】C# 采用POST登录京东
- CircleProgressBar
- cordova 创建ios项目
- Libev学习笔记3
- asp.net下cookie 的基础使用
- javascript 省市区三级联动 附: json数据
- UIGestureRecognizer - BNR
- Spring系列之AOP的原理及手动实现
- Struts2之action 之 感叹号 ! 动态方法调用
- IC卡T0协议中的过程字与状态字
- Java交流分享(522818473)
- 每天一个linux命令-ls命令
- 【Python】sasa版:文件中csv读取在写入csv读取的数据和执行是否成功。
- [调参]CV炼丹技巧/经验
- 解决IE8不支持console
热门文章
- SpringSecurity 整合 JWT
- BZOJ 5495: [2019省队联测]异或粽子 可持久化trie+堆
- 有效的minidump(二)
- rust cargo 一些方便的三方cargo 子命令扩展
- 异步编程(回调函数,promise)
- 2017.10.2 国庆清北 D2T1 (a*b)|x
- uwsgi example
- GoCN每日新闻(2019-10-05)
- Linux 磁盘格式化、检验、挂载
- unity2019新建LWRP项目出错:Failed to resolve project template