题解 | #NCPC#

本题是2026牛客寒假算法基础集训营2的B题

题目链接：https://ac.nowcoder.com/acm/contest/120562/B

题目大意：若干位选手拥有一个数值，然后相互PK，输的的人退出，数值一样的人同归于尽，最后活下来的人获胜。

题目分析：观察到赢得人不会退出，所以直接找最大值，如果最大值是奇数个，那么他可以将所有人都踢死，所以只有最大值可以获胜。如果是偶数个，那么最大值不可能获胜，它必定会与跟自己数值相同的人同归于尽，但他可以帮助比他弱小的人先除去其他人，最后跟与自己数值相同的人一起退出，这样只剩下了那个比最大值小的数，所以除了最大值，其他任何人都有可能获胜。

所以直接看代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
ll a[N];
void solve(){
	ll n;
	cin>>n;
	ll ma=-1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ma=max(ma,a[i]);
	}
	ll cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]==ma){
			cnt++;
		}
	}
	if(cnt%2!=0){
		for(int i=1;i<=n;i++){
			if(a[i]==ma){
				cout<<1;
			}
			else{
				cout<<0;
			}
		}
	}
	else{
		for(int i=1;i<=n;i++){
			if(a[i]==ma){
				cout<<0;
			}
			else{
				cout<<1;
			}
		}
	}
	
	cout<<"\n";
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	}
}
// 1 1 4 5 1 4 
// 3 3 3 3 3
// 1 2 4 5 5
// 1 4 4 5 5 
// 1 3 3 4 4 6 7