题目描述
rqdmap和他的小女友正在玩一个游戏。有n个正整数。这两个人轮流取数字。为了显示他的绅士风度，rqdmap要求他的小女友先取数字。
每当rqdmap的小女友可以选择剩下的数字中的任意一个来拿走（记为x），rqdmap需要从剩下的数字中选择一个数字（记为y），并且满足以下两个条件中的至少一个：
1.|x − y| ≤ 3，即x和y的绝对值之差不能超过3。
2.x ≡ y (mod 3)，即x和y对3取模得到的余数相同。
如果rqdmap无法从剩下的数字中选择合格的数字，rqdmap的小女友赢；否则，rqdmap赢。rqdmap和他的小女友都很聪明。现在在游戏开始之前，您已经获得了这些数字，请判断最终谁会赢得游戏。
题解
考虑用将所有数字根据除三的余数分为三组：属于同一个组的所有数字可以连续拿走，不同属一个组的数字必须满足绝对值之差不超过3才可以拿走。
- 当三组含有的数字数量均为偶数：可知先手方不论如何取，后手方都可以取和先手方同一组的数字，三组的元素数量会始终保持为偶数。先手必败。
- 当三组含有的数字数量为奇，奇，偶：只要在两个奇数组中各取一个数，或在奇数，偶数组各取一个数，便可以回到情况1，先手必败的可能。因此只需要判断是否可满足此种情况。
- 其余情况：n为奇数或找不到先手必败点，则先手必胜。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
bool flag=false;
int n;
cin>>n;
map<int,int>ma;
vector<int> v[3];
int cnt[3]={0,0,0};
for(int i=1;i<=n;i++){
int a;
cin>>a;
ma[a]++;
v[a%3].push_back(a);
cnt[a%3]++;
}
if(n%2){
cout<<"His little girlfriend\n";
continue;
}
else if(cnt[0]%2==0&&cnt[1]%2==0&&cnt[2]%2==0){
cout<<"rqd\n";
continue;
}
else{
int x=0;
while(cnt[x]%2)x++;
int p=-1,q=-1;
for(int i=0;i<v[x].size();i++){
if(ma[v[x][i]+2]||ma[v[x][i]-1]){
p=i;
break;
}
}
for(int i=0;i<v[x].size();i++){
if(i==p)continue;
if(ma[v[x][i]+1]||ma[v[x][i]-2]){
q=i;
break;
}
}
if(p!=-1&&q!=-1)flag=true;
x=(x+1)%3;
for(int i=0;i<v[x].size();i++){
if(ma[v[x][i]+1]||ma[v[x][i]-2]){
flag=true;
break;
}
}
if(flag)cout<<"rqd\n";
else cout<<"His little girlfriend\n";
}
}
}