本文共 2785 字，大约阅读时间需要 9 分钟。

A. Dense Array

对于相邻的两个元素，如果两个中的最小值的二倍小于最大值，则答案增加1，最小值再乘2，一直循环下去。

#include
   
    using namespace std;//const int maxn = 55;//int a[maxn];int n,a;int main(){   	int t;	cin>>t;	while(t--)	{   		int ans = 0;		cin>>n>>a;		int pre = a;		for(int i=2;i<=n;i++) 		{   			cin>>a;			int mx = max(pre,a);			int mn = min(pre,a);			while(mn*2
   

B. Balanced Remainders

统计其中模三分别余0,，1，2的个数，进行三次判断，因为每次只能相邻的两个元素进行平衡。

#include
   
    using namespace std;const int maxn = 3e4+5;//int a[maxn];int n,a;int main(){   	int t;	cin>>t;	while(t--)	{   		int ans=0;		cin>>n;		int c1=0,c2=0,c0=0;		for(int i=1;i<=n;i++)		{   			cin>>a;			if(a%3==0) c0++;			if(a%3==1) c1++;			if(a%3==2) c2++;		}				for(int i=0;i<3;i++)		{   			if(c2>n/3) ans += c2-n/3,c0 += c2-n/3,c2=n/3;			if(c0>n/3) ans += c0-n/3,c1 += c0-n/3,c0=n/3;			if(c1>n/3) ans += c1-n/3,c2 += c1-n/3,c1=n/3;			if(c1==c2 && c0==c1) break;		}		cout<
    
     <<'\n';	}		return 0;}
    
   

C.Sum of Cubes

将最多的i * i * i（立方数）存入到无序集合中，循环一个数，计算出另一个数判断另一个数是否是立方数，即是否在无序集合中。

#include
   
    #include
    
     using namespace std;typedef long long ll;const ll INF = 1e12+5;ll x;unordered_set < ll > cubes; void solve(){   	for(ll i=1;i*i*i<=x;i++)	{   		if(cubes.count(x-i*i*i))		{   			cout<<"Yes\n";			return;		}	}	cout<<"No\n";}int main(){   	for(ll i=1;i*i*i<=INF;i++)		cubes.insert(i*i*i);	int _;	cin>>_;	while(_--)	{   		cin>>x;		solve();	}	return 0; }
    
   

D. Permutation Transformation

建一棵树，使数组中的最大值始终在树的根部，保证左边的值永远在左子树，右边的值永远在右子树。

#include
   
    using namespace std;const int maxn = 105;int a[maxn];int tree[maxn];void build(int l,int r,int curD){   	if(l>r) return ;//特殊判断，当最大值在第一个或者是最后一个时	if(l==r)	{   		tree[l] = curD;		return ;	}	int t = l;	for(int i=l+1;i<=r;i++)	{   		if(a[t]
    
     >n;	for(int i=1;i<=n;i++) cin>>a[i];	build(1,n,0);	for(int i=1;i<=n;i++) cout<
     
      <<" ";	cout<<"\n";}int main(){   	int _;	cin>>_;	while(_--)	{   		solve();	}	return 0; }
     
    
   

E.Accidental Victory

n个人进行锦标赛，每个人身上有ai枚币，谁的币多谁就获胜，随机组合n-1场比赛，每场比赛胜利的可以获得失败的人的所有币，求谁获胜的概率不为0。输出获胜概率不为0的下标号。

思路:

构建一个二元组，按值排序，建立前缀和数组，从后往前遍历，如果当前的前缀和数组大于后面的数组值的话，这个人就可能获胜，将下标存入一个数组中进行维护，相反就退出，因为这个人的分值永远超不过后面的人，前面的人就不可能获胜。

#include
   
    using namespace std;typedef long long ll;const int maxn = 2e5+5;ll sum[maxn];pair
    
     p[maxn];int n;bool cmp(pair
     
      a,pair
      
       b){   	return a.first < b.first;}void solve(){   	memset(sum,0,sizeof(sum));	for(int i=1;i<=n;i++) 	{   		cin>>p[i].first;		p[i].second = i;	}	sort(p+1,p+1+n,cmp);	for(int i=1;i<=n;i++)		sum[i] = sum[i-1] + p[i].first;	vector
       
        id;	id.push_back(p[n].second);	for(int i=n-1;i>=1;i--)	{   		if(sum[i]>=p[i+1].first) id.push_back(p[i].second); 		else break;	}	sort(id.begin(),id.end());	cout<
        
         <<'\n'; for(int i=0;i
         
          >_; while(_--) { cin>>n; solve(); } return 0; }