NCPC

链接：https://ac.nowcoder.com/acm/contest/120562/B 来源：牛客网 题目概述 有 n 个选手，每个选手有一个美味值 a[i]，两两对决，若值不同，值小的淘汰；若值相同，两个都淘汰。我们需要判断每个选手能否成为最后唯一剩下的人，输出一个长度为n的 01 字符串。 思路分析 通过观察可知只有全局最大值的选手才可能获胜。若某选手的值不是全局最大，他迟早会遇见一个值更大的对手——因为值更大的选手无法在遇到他之前被全部消灭。一旦相遇，值小者淘汰，他必输。因此，胜利者必须出自全局最大值集合。而最大值选手只会在与另一个最大值对决时被淘汰（同归于尽）。 所以我们设最大值为 max，共有 sum 个选手等于 max。若 sum 是奇数，可以安排他们两两厮杀，最终恰好剩一人；若 sum 是偶数，他们可以全部成对淘汰，无一生还。 当最大值有机会全灭时，剩余选手有机会拥有魔王护，令最大值之一淘汰除此之外的所有选手后与其他所有最大值同归于尽，这一选手即可幸存。而这个机会是所有非最大值选手所共享的。 总结概括 这道题的本质是最大值的统治力与偶数淘汰的完美配合。我的代码抓住了一个极其简洁的充要条件：最大值个数为奇数时，胜者必是最大值；为偶数时，胜者必不是最大值，且每一个非最大值都有机会。它跳出了递归分治的复杂框架，用一次遍历直接输出答案，干净利落。一句话，最大值奇数，唯我独尊；最大值偶数，互撕陨落。 C++代码展示如下:

#include<bits/stdc++.h>
using namespace std;
int main() {
	long long T;
	cin>>T;
	for (long long i=0; i<T; i++) {
		long long n;
		cin>>n;
		long long a[n];
		long long max=0;
		long long sum=0;
		for(long long j=0; j<n; j++) {
			cin>>a[j];
			if(max<=a[j]) {
				max=a[j];
			}
		}
		for(long long j=0; j<n; j++) {
			if(a[j]==max) {
				sum++;
			}
		}
		for(long long j=0; j<n; j++) {
			if(sum%2==1) {
				if(a[j]==max) {
					cout<<1;
				} else {
					cout<<0;
				}
			} else {
				if(a[j]==max) {
					cout<<0;
				} else {
					cout<<1;
				}
			}
		}
		cout<<endl;
	}
}