Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)A-C

A. Maximum Cake Tastiness

简单来说就是找到最大值和次大值，输出他们的和

#include
#include
#include
#include
#include
int main()
{
	int tt;scanf("%d",&tt);
	int n,d,maxa,maxb;
	for(int j=0;j=maxa){
				maxb=maxa;maxa=d;
			}
			else if(dmaxb) maxb=d;
		}
		printf("%dn",maxa+maxb);
	}
	return 0;
}
 
 

B. Prefix Removals

 假设位置字符串位置i，如果在i之后没有与i相同的字符，就从这个位置开始输出字符串剩余部分，否则查i+1

实际上只要储存a到z所有字符最后出现的位置，找到其中最小的位置，从该位开始输出

#include
#include
#include
#include
#include

char x[200005];

int main()
{
	int tip[26]={0},num[26]={0};
	int tt;scanf("%d",&tt);getchar();
	for(int j=0;j 
C. Alice and the Cake
 
 
 
 
 
一块蛋糕每次只能对半切
 
思路应该没问题，但是快排O（n^2*logn）第六个点超时，改成插入(n*(logn)^2)之后第九个点超时，改不动了
 
#include
#include
#include
#include
#include

long long int num[200005]={0},tip[200005]={0};


int cmpfuncnum (const void * a, const void * b)
{
	return ( *(long long int*)b - *(long long int*)a );
}
int cmpfunctip (const void * a, const void * b)
{
	return ( *(long long int*)a - *(long long int*)b );
}

int main()
{
	int tt;scanf("%d",&tt);
	while(tt--){
		int n,tipl=2,nb=0;scanf("%d",&n);
		long long int all=0;
		if(n==1) {
			scanf("%lld",&all);
			printf("YESn");
			continue;
		}
		for(int i=1;i<=n;i++){
			scanf("%lld",&num[i]);
			all+=num[i];
			tip[i]=0;
		}
		if(all/n==1&all%n==0){
			printf("YESn");
			continue;
		}
		qsort(num+1, n, sizeof(long long int), cmpfuncnum);
		if(all%2==1){
			tip[1]=all/2;tip[2]=all/2+1;
		}
		else{
			tip[1]=tip[2]=all/2;
		}
		for(int i=1;i<=n;i++){
			if(tip[tipl]==num[i]){
				tip[tipl]=0;
				tipl--;
			}
			else{
				while(tip[tipl]>num[i]){
					if(tip[tipl]%2==0){
						tip[tipl]=tip[tipl]/2;
						tip[tipl+1]=tip[tipl];
						int ip=tipl-1;long long int kk;
						while(tip[ip]>tip[ip+2]){
							kk=tip[ip];tip[ip]=tip[ip+2];tip[ip+2]=kk;ip--;
						}
					}
					else{
						tip[tipl]=tip[tipl]/2+1;
						tip[tipl+1]=tip[tipl];
						int ip=tipl-1;long long int kk;
						while(tip[ip]>tip[ip+2]){
							kk=tip[ip];tip[ip]=tip[ip+2];tip[ip+2]=kk;ip--;
						}
						kk=tip[ip+1];
						while(tip[ip]==tip[ip+1]) ip--;
						tip[ip+1]=kk-1;
					}
					tipl++;
					//printf("tipl:%dn",tipl);
					//for(int j=1;j<=tipl;j++) printf("%d ",tip[j]);
					//printf("n");
					if(tipl>n){
						printf("NOn");
						nb=1;
						break;
					}
				}
				
				if(nb==1) break;
				if(tip[tipl]==num[i]){
					tip[tipl]=0;
					tipl--;
				}
				else{
					printf("NOn");
					nb=1;
					break;
				}
			}
		}
		if(nb==0) printf("YESn");
	}
	return 0;
}
 
3-28：
 
花时间看了一下c++中map和queue的操作，把这个题目写出来了
 
#include
using namespace std;

long long int num[200005]={0};

int main()
{
	long long int tt;scanf("%lld",&tt);
	while(tt--){
		map  fid;
		long long int n,all=0;scanf("%lld",&n);
		for(int i=1;i<=n;i++) {
			scanf("%lld",&num[i]);
			fid[num[i]]++;
			all+=num[i];
		}
		queue que;que.push(all);
		for(int i=1;i<=10*n&&que.size()>0;i++){
			all=que.front();que.pop();
			if(fid[all]) fid[all]--;
			else{
				que.push(all/2);
				que.push((all+1)/2);
			}
		}
		if(que.size()) printf("NOn");
		else printf("YESn");
	}
	return 0;
}