HDU - 6266 Hakase and Nano【思维】

题目

Problem C. Hakase and Nano Hakase and Nano are playing an ancient pebble game (pebble is a kind of rock). There are n packs of pebbles, and the i-th pack contains ai pebbles. They take turns to pick up pebbles. In each turn, they can choose a pack arbitrarily and pick up at least one pebble in this pack. The person who takes the last pebble wins. This time, Hakase cheats. In each turn, she must pick pebbles following the rules twice continuously. Suppose both players play optimally, can you tell whether Hakase will win? Input The first line contains an integer T (1 ≤ T ≤ 20) representing the number of test cases. For each test case, the first line of description contains two integers n(1 ≤ n ≤ 106) and d (d = 1 or d = 2). If d = 1, Hakase takes first and if d = 2, Nano takes first. n represents the number of pebble packs. The second line contains n integers, the i-th integer ai (1 ≤ ai ≤ 109) represents the number of pebbles in the i-th pebble pack. Output For each test case, print “Yes” or “No” in one line. If Hakase can win, print “Yes”, otherwise, print “No”.

输入 2 3 1 1 1 2 3 2 1 1 2 输出 Yes No

题意：t组输入，每次先输入两个数n，m，分别表示有n堆石子，m等于一时第一个人先操作，等于2时第二个人先操作，每次操作可以从任意一堆石子中拿出任意个石子，第一个人每次操作两次，第二个人每次操作一次，如果第一个人赢输出Yes否则输出No

思路：模拟之后发现当第一个人先手时只有当n个数全都为一且n%3==0时2赢 否则1赢，第二个人先手时我们只要考虑是否可以转化为第一种情况即可，第二个人先手转化为第一种情况则至少有n-1个1并且（n-1）%3=0只有这时第二个人操作后轮到第一个人操作，转化为第一个人必输的情况，否则1赢，具体看代码

AC code

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<sstream> #include<queue> #include<stack> using namespace std; void solve() { int s=0,n,m,x; cin>>n>>m; for(int i=0;i<n;i++) { cin>>x; if(x==1)s++;//记录一的数量 } if(m==1) { if((s==n)&&(s%3==0))printf("No\n");//1输 else printf("Yes\n"); } else { int q=n-1; if((s>=q)&&((q%3==0)||(n%3==0)))printf("No\n"); else printf("Yes\n"); } } int main() { ios::sync_with_stdio(0); int t; cin>>t; while(t--) { solve(); } }