【hdu 1850】Being a Good Boy in Spring Festival
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7095 Accepted Submission(s): 4300
Problem Description
一年在外 父母时刻牵挂
春节回家 你能做几天好孩子吗
寒假里尝试做做下面的事情吧
陪妈妈逛一次菜场
悄悄给爸爸买个小礼物
主动地 强烈地 要求洗一次碗
某一天早起 给爸妈用心地做回早餐
如果愿意 你还可以和爸妈说
咱们玩个小游戏吧 ACM课上学的呢~
下面是一个二人小游戏:桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负,我只想问大家:
——“先手的人如果想赢,第一步有几种选择呢?”
Input
输入数据包含多个测试用例,每个测试用例占2行,首先一行包含一个整数M(1< M<=100),表示扑克牌的堆数,紧接着一行包含M个整数Ni(1<=Ni<=1000000,i=1…M),分别表示M堆扑克的数量。M为0则表示输入数据的结束。
Output
如果先手的人能赢,请输出他第一步可行的方案数,否则请输出0,每个实例的输出占一行。
Sample Input
3
5 7 9
0
Sample Output
1
【题目链接】:http://acm.hdu.edu.cn/showproblem.php?pid=1850
【题解】
要让先手赢;
则先手进行一次操作之后,剩余n个堆(或n-1)的数字的异或值,必然为0,这样先手输(这时对方是先手了);
可以这样
先枚举对第i个堆进行操作;
肯定是将这个堆的数字减小;
然后这个数字与其余的n-1个数字的异或值为0;
则我们先处理出其余n-1个数字的异或值;
(先处理出n个数字的异或值,然后和这第i个数字异或一下就得到了其余n-1个数字的异或值);
如果这第i个数字大于其余n-1个数字的异或值;
则这第i个数字可以通过减小;
和其余n-1个数字的异或值一样大;
当其和其他n-1个数字的异或值一样大的时候,再异或一下就变成0了;
且也只有这一种方式(对单个堆操作的话);
累计有多少个堆的数字符合上述要求就可以了;
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 1e2+10;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
int m;
int a[MAXN];
int main()
{
//freopen("F:\\rush.txt","r",stdin);
rei(m);
while (m!=0)
{
int temp = 0;
rep1(i,1,m)
{
rei(a[i]);
temp ^= a[i];
}
int cnt = 0;
rep1(i,1,m)
{
if (a[i]>(temp^a[i]))
cnt++;
}
cout << cnt << endl;
rei(m);
}
return 0;
}
相关文章
- Spring之IOC自动装配
- Spring Security实现分布式系统授权
- Spring AOP原理分析
- Spring Batch 5.0 发布,使用 JDK 17 作为基线版本并支持原生 Java
- Spring Cloud Config 配置中心搭建
- 配置Spring Cloud Feign(一)
- Spring Cloud Sleuth与Prometheus集成
- 简单封装Spring的SimpleJdbcTemplate详解编程语言
- MySQL删除IN操作: 简易指南(mysql删除in)
- 语法应用Oracle中IN语法的多种方式(oracle中in)
- Spring Boot 如何快速集成 Redis 哨兵?
- MySQL中IN查询的使用方法(mysql查询in)
- Oracle中使用IN函数查找元素(oracle 函数 in)
- MSSQL中的ID IN查询使用技巧(mssql id in)
- Spring框架致力于搭建基于MSSQL的稳健开发体系(spring mssql)
- MySQL中IN操作符的用法与注意事项(mysql中in的写法)
- MySQL中使用IN操作会影响性能吗(mysql中in性能)
- Oracle的IN走索引技术(in走索引 oracle)
- 深入理解Oracle中IN运算符的用法(oracle中的in用法)
- 语法 在Oracle中使用IN子句实现查询(oracle中支持in)
- 使用Oracle中的IN方法精准查找数据(oracle中in方法)