C++(clang++ 11.0.1) 解法, 执行用时: 1852ms, 内存消耗: 78736K, 提交时间: 2023-05-16 13:16:08

#include<bits/stdc++.h>
using namespace std;

static bool cmp(multiset<int> v1, multiset<int> v2){
	return v1.size()%2 < v2.size()%2;
}

int check(multiset<int> v1, multiset<int> v2){
	for(int x: v1){
		for(int i = x - 2; i <= x + 2; i++){
			if(v2.count(i) > 0) return i;
		}
	}
	return 0;
}
void print(int i){
	cout<<(i ? "rqd" : "His little girlfriend")<<endl;;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		vector<multiset<int>> a(3);
		cin>>n;
		for(int i = 0; i < n; i++){
			int data;
			cin>>data;
			a[data%3].insert(data);
		}
		if(n&1) { print(0); continue;}
		sort(a.begin(), a.end(), cmp);
		int num1= check(a[1], a[0]), num2 = check(a[1], a[2]), num3 = check(a[2], a[0]);
		if(a[2].size() % 2 == 0 || num2) { print(1); continue;}
        if(!num1 || !num3) {print(0); continue;}
		if(num1 != num3) { print(1); continue;}
        int c = a[0].erase(num1); 
		if(num1 == num3 &&   c >= 2) { print(1); continue;}
        if(check(a[1], a[0])||check(a[2], a[0])){ print(1); continue;}
		print(0);	
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 435ms, 内存消耗: 19912K, 提交时间: 2022-10-25 18:38:54

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int solve()
{
	int n;
	scanf("%d",&n);
	vector<int>v[3];
	for(int i=0,t;i<n;i++){
		scanf("%d",&t);
		v[t%3].pb(t);
	}
	if(n&1)return 0;
	int u=-1,y=-1;
	for(int i=0;i<3;i++)
		if(v[i].size()%2)
			if(u==-1)u=i;
		else y=i;
	if(u==-1)return 1;
	vector<int>&a=v[u];
	for(auto &x:v[y])a.pb(x);
	for(auto &x:v[3-u-y])a.pb(x);
	sort(a.begin(),a.end());
	vector<int>cnt[3];
	for(int i=0;i<n-1;i++)
		if(a[i]%3!=a[i+1]%3&&a[i+1]-a[i]<3)
			cnt[a[i]%3].pb(i+1),cnt[a[i+1]%3].pb(i);
	if(cnt[u].size()&&cnt[y].size()){
		if(cnt[u].size()==1&&cnt[y].size()==1)
			if(cnt[u][0]==cnt[y][0])
				return 0;
		return 1;
	}
	return 0;
}
int main()
{
	int tt;
	scanf("%d",&tt);
	while(tt--){
		printf("%s\n",solve()?"rqd":"His little girlfriend");
	}
}