2021暑期积分赛一

A - Constructing the Array （CF353D）

There is an array a of size n consiting of all zeros. You have to perform n operations on this array. On the ith operation, you need to perform the following steps:

Choose the maximum size subarray consisting of all zeros. If there are multiple such subarrays of the same size, select the leftmost one.
Let the subarray be [l,r]. If the length of the subarray is and odd number, then perform
a[(l + r) / 2] = i [that is assign the value i to the ((l + r) / 2)th index of the array], otherwise perform a[(l + r - 1) / 2] = i [that is assign the value i to the ((l + r - 1) / 2)th index of the array]
For example, let the initial array a be of length 5 (a = [0, 0, 0, 0, 0]). Then the operations are

The chosen subarray is [1, 5] and we assign a[3] = 1. The array becomes [0, 0, 1, 0, 0]
The chosen subarray is [1, 2] and we assign a[1] = 2. The array becomes [2, 0, 1, 0, 0]
The chosen subarray is [4, 5] and we assign a[4] = 3. The array becomes [2, 0, 1, 3, 0]
The chosen subarray is [2, 2] and we assign a[2] = 4. The array becomes [2, 4, 1, 3, 0]
The chosen subarray is [5, 5] and we assign a[5] = 5. The array becomes [2, 4, 1, 3, 5]
Your task is to find the final array after all n operations. It is guaranteed that the answer always exists and is unique.

Input
The first line of the input contains an integer t (1 ≤ t ≤ 104) — the number of test cases. Then t test cases follow.

Each test case contains only one line containing one integer n (1 ≤ n ≤ 2 × 105) — the length of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 2 × 105 (∑n ≤ 2 × 105)

Output
For each test case, print the final array after performing all the n operations.

Sample Input
6
1
2
3
4
5
6
Sample Output
1
1 2
2 1 3
3 1 2 4
2 4 1 3 5
3 4 1 5 2 6
AC代码

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct node
{
	int l,r;
	bool operator<(const node&o)const
	{
		if(r-l==o.r-o.l)	return l>o.r;
		else	return r-l<o.r-o.l;
	}
};
priority_queue<node> dq;
int ans[200010];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		memset(ans,0,sizeof(ans));
		dq.push({1,n});
		int k=0;
		while(!dq.empty())
		{
			node q=dq.top();
			dq.pop();
			int l=q.l;
			int r=q.r;
			int m=(l+r)/2;
			k++;
			ans[m]=k;
			if(l!=r)
			{
				if(m==l)	dq.push({m+1,r});
				else
				{
					dq.push({l,m-1});
					dq.push({m+1,r});
				}
			}
			
		}
		cout<<ans[1];
		for(int i=2;i<=n;i++)	cout<<" "<<ans[i];
		cout<<endl;
	}
	return 0;
}

B - Taxi （CF158B）

学校有n个小组外出游玩，第i个小组有si (1 ≤ si ≤ 4)个人，同学们想要打出租出回来，每辆车最多坐4个人，每个小组必须坐在同一辆车上，求最少需要多少辆车才能让同学们都回来；
Input
第一行一个整数n (1 ≤ n ≤ 1e5)，接下来n个数表示si (1 ≤ si ≤ 4)，
Output
输出一个整数表示结果

Input
5
1 2 4 3 3
Output
4
AC代码

#include <iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int cnt=0;
	int one=0,two=0,three=0,four=0;
	while(n--)
	{
		int s;
		cin>>s;
		switch(s)
		{
			case 1:one++;break;
			case 2:two++;break;
			case 3:three++;break;
			case 4:four++;break;
		}
	}
	cnt=four+three+two/2;	//最少这么多，再把多余的1拼入three和two 
	if(three<one)	one-=three;//1在拼入three后仍有剩余 
	else	one=0;
	if(two&1)	//two是奇数，剩余一组two未算上 
	{
		cnt++;
		if(one-2>0)	one-=2;	//如果1的个数大于2，剩余1的个数为one-2
		else	one=0; 
	}
	cnt+=one/4;		//最后剩余的1互相组队 
	if(one%4!=0)	cnt++;
	cout<<cnt<<endl;
	return 0;
}

C - Running Median HDU - 3282

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.
Input
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M, (1 ≤ M ≤ 9999), giving the total number of signed integers to be processed.
The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space.
The last line in the dataset may contain less than 10 values.
Output
For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output.
Sample Input
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
Sample Output
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3
AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
using namespace std;		
int x;
int main()
{
	int p;
	cin>>p;
	while(p--)
	{
		int id,n;
		cin>>id>>n;
		cout<<id<<' '<<(n+1)/2<<endl;
		
		//用两个优先队列存放数组 
		priority_queue<int,vector<int>,greater<int> > gq;	//升序，大先出 
		priority_queue<int,vector<int>,less<int> > lq;	//降序，小先出 
		int cnt=0;	//记录输出数字的个数，用于判断是否输出endl 
		
		for(int i=1;i<=n;i++)
		{
			cin>>x;
			if(i==1)	lq.push(x);	//第一个数直接丢进lq 
			else
			{
				if(x>lq.top())	gq.push(x);	 
				else	lq.push(x);
			}			
			
			if((int)gq.size()-(int)lq.size()>=1)	//如果gq中元素比lq中多 
			{										//把gq中top元素挪进lq 
				int temp=gq.top();					//始终维护lq中元素比gq多 
				lq.push(temp);
				gq.pop();
			}
			if((int)lq.size()-(int)gq.size()>1)		//如果lq中元素比gq多 
			{										//那么始终维护lq中元素之比gq中多一 
				int temp=lq.top();					//多出来的top元素就是所求中位数 
				gq.push(temp);
				lq.pop();
			}	
			
			
			if(i%2==1)	//如果i是奇数 
			{
				cout<<lq.top();
				cnt++;
				if(cnt%10==0)	cout<<endl;		//当输出十个数字 换行 
				else if(i==n)	cout<<endl;		//所有所求数字输出完毕，换行 
				else	cout<<" ";				//否则，输出空格 
			}
			
		}
		
	}
	return 0;
}

D - What Are You Talking About HDU - 1075

小智有一只神奇的电耗子（就决定是你了，皮卡丘！），它每天都会写很多东西，但是他看不懂这只黄皮耗子整天在写些什么。有一天他突然收到一个快递。他拆开后发现是一个字典，他就好奇地翻了起来，结果发现把皮卡丘写的东西和字典里的东西一对比，竟然能翻译成英文，他很想把皮卡丘写的东西全部翻一下来，你能帮他把皮卡丘写的东西翻译成英文吗？
Input
本题只有一组数据，所有单词只包含小写字母。测试用例由两部分组成，字典部分以一个单行字符串“START”开头，此字符串应该被忽略。然后下面每行包含两个单词，第一个是英文单词，第二个是皮卡丘的语言。字典以一个单行字符串“END”结束。字典不包含“START”和“END”。皮卡丘的文章同样以“START”开头，以“END”结束，然后是一篇皮卡丘写的文章。你应该将文章翻译成英文。如果你在字典中找到该单词，则应将其翻译并将新单词写入你的翻译，如果你无法在字典中找到该单词，则无需翻译它，只需将旧单词复制到你的翻译中即可。空格，制表符和回车及所有标点符号不应该被翻译。每行最多包含3000个字符
Output
你应该输出翻译的文章
Sample Input
START
from fiwo
hello difh
dream riwosf
you fnnvk
like fiiwj
END
START
difh, i’m fiwo riwosf.
i fiiwj fnnvk!
END
Sample Output
hello, i’m from dream.
i like you!
AC代码

#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
map<string,string> mp;
string s1,s2,s;
int judge(char c)
{
	if(c>='a'&&c<='z')	return 1;
	else return 0;
}
int main()
{
	while(cin>>s1)
	{
		if(s1=="START")	continue;
		if(s1=="END")	break;
		cin>>s2;
		mp[s2]=s1;
	}
	getchar(); //cin读不入回车，需要加个getchar读入回车，否则会直接getline一行空白 
	while(getline(cin,s))
	{
		if(s=="START")	continue;
		if(s=="END")	break;
		int i=0;
		while(i<s.size())
		{
			if(judge(s[i]))
			{
				string str="";
				while(judge(s[i]))
				{
					str=str+s[i];
					i++;
				}
				if(mp[str]!="")	cout<<mp[str];
				else	cout<<str;
			}
			else
			{
				cout<<s[i];
				i++;
			}	
		}
		cout<<endl;
	}
	return 0;
}

E - A + B Problem II HDU - 1002

Input
输入数据的第一行为一个整数T（1≤T≤20），表示测试数据总数，紧接着的T行数据，每行包含由空格隔开的两个整数a和b，每组数据占一行。注意了，a和b可能非常大，大到超过32位整数可以表示的范围，我们假定a和b的位数不超过1000。
Output
对于每组数据，你需要输出两行，第一行显示"Case #:"（注意输出为英文字符），第二行为一个等式"a + b = Sum"，这里的Sum就是指a + b的结果（注意这个等式中的空格）。请在每两组输出数据间输出一个空行。
Sample Input
2
1 2
112233445566778899 998877665544332211
Sample Output
Case 1:
1 + 2 = 3

Case 2:
112233445566778899 + 998877665544332211 = 1111111111111111110
AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
using namespace std;
int t;
string a,b;
int aa[1111],bb[1111];
int cc[1111];
int k=0;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>a>>b;
		int la=a.size(),lb=b.size();
		k++;
		int lm=max(la,lb);
		
		memset(aa,0,sizeof(aa));	//注意这里是将数组全部内存空间置0，不是简单的到la、lb 
		memset(bb,0,sizeof(bb));	//因为如果上次的长度大，数据可能会对这次产生影响 
		
		for(int i=0;i<la;i++)	aa[i]=a[la-i-1]-'0';	//“1234”存放数字的数组第一位应该是字符串的最后一位4 
		for(int i=0;i<lb;i++)	bb[i]=b[lb-i-1]-'0';
				
		int jin=0,cnt=0;
		for(int i=0;i<lm;i++)	//注意这里是小于lm    因为前述步骤已经对多余位置置0，所以不会有影响 
		{											//“123”+“3” ==>  123+003 
			int sum=aa[i]+bb[i]+jin;
			jin=sum/10;
			cc[i]=sum%10;
			cnt++;
		}
		if(jin)		//如果最后一位进位不为0 
		{
			cc[cnt]=1;
			cnt++;
		}	
		cout<<"Case "<<k<<':'<<endl;
		cout<<a<<" + "<<b<<" = ";
		for(int i=cnt-1;i>=0;i--)	cout<<cc[i];	//倒序输出 
		cout<<endl;
		if(t>0)	cout<<endl;
	}
	return 0;
}

F - 首字母变大写 HDU - 2026

输入一个英文句子，将每个单词的第一个字母改成大写字母。
Input
输入数据包含多个测试实例，每个测试实例是一个长度不超过100的英文句子，占一行。
Output
请输出按照要求改写后的英文句子。
Sample Input
i like acm
i want to get an accepted
Sample Output
I Like Acm
I Want To Get An Accepted
AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string s;
int main()
{
	while(getline(cin,s)) //读入一行带空格字符串 
	{
		s[0]-=32;
		for(int i=1;i<s.size();i++)	//字符串长度用.size() 
		{
			if(s[i-1]==' ')	s[i]-=32;
		}	
		cout<<s<<endl;		
	}	
	return 0;
}
/*
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string s;
int main()
{
	while(getline(cin,s)) 
	{
		s[0]-=32;
		for(int i=1;i<s.size();i++)
		{
			if(s[i-1]==' ')	s[i]-=32;
		}	
		cout<<s<<endl;		
	}	
	return 0;
}
*/

G - Solving Order HDU - 5702

Input
The first line is an integer T which indicates the case number.
And as for each case, the first line is an integer n, which is the number of problems.
Then there are n lines followed, with a string and an integer in each line, in the i-th line, the string means the color of ballon for the i-th problem, and the integer means the ballon numbers.

It is guaranteed that:
T is about 100.
1≤n≤10.
1≤ string length ≤10.
1≤ bolloon numbers ≤83.(there are 83 teams :p)
For any two problems, their corresponding colors are different.
For any two kinds of balloons, their numbers are different.
Output
For each case, you need to output a single line.
There should be n strings in the line representing the solving order you choose.
Please make sure that there is only a blank between every two strings, and there is no extra blank.
Sample Input
3
3
red 1
green 2
yellow 3
1
blue 83
2
red 2
white 1
Sample Output
yellow green red
blue
red white
AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <set>
using namespace std;
struct Bo
{
	string color;
	int num;
}ballon[11];
bool cmp(Bo a,Bo b)
{
	return a.num>b.num;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=0;i<n;i++)
			cin>>ballon[i].color>>ballon[i].num;
			
		sort(ballon,ballon+n,cmp);
		cout<<ballon[0].color;
		for(int i=1;i<n;i++)
			cout<<" "<<ballon[i].color;
		cout<<endl;
	}
	return 0;
}

H - 排序 HDU - 1106

输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。

你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。

Input
输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。

输入数据保证：分割得到的非负整数不会大于100000000；输入数据不可能全由‘5’组成。
Output
对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。
Sample Input
0051231232050775
Sample Output
0 77 12312320
AC代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> v;	
string s;
int main()
{
	while(cin>>s)
	{	
		v.clear();
		int l=s.size();
		int ind=0;	//下标 
		while(ind<l)
		{
			if(s[ind]=='5')	ind++;	//如果该字符等于‘5’，ind++，遍历下一个字符 
			else
			{
				string x="";	//空字符串，用于存放分割出来的字符串 
				int cnt=0;
				while(s[ind]!='5'&&ind<l)
				{
					x=x+s[ind];
					cnt++;
					ind++;
				}
				int sum=0;
				for(int i=0;i<cnt;i++)	//把字符串转化为数字 
				{
					int xx=x[i]-'0';
					sum=sum*10+xx;
				}
				v.push_back(sum);
			}
		}
		sort(v.begin(),v.end());
		vector<int>::iterator it;
		it=v.begin();
		cout<<*it;
		for(it++;it!=v.end();it++)
			cout<<' '<<*it;
		cout<<endl;
	}
	return 0;
}

I - 前m大的数 HDU - 1280

给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N*(N-1)/2个和，求出其中前M大的数(M<=1000)并按从大到小的顺序排列。
Input
输入可能包含多组数据，其中每组数据包括两行：
第一行两个数N和M，
第二行N个数，表示该序列。

Output
对于输入的每组数据，输出M个数，表示结果。输出应当按照从大到小的顺序排列。
Sample Input
4 4
1 2 3 4
4 5
5 3 6 4
Sample Output
7 6 5 5
11 10 9 9 8
AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
int n,m;
int a[3333];
int v[10000000];	//注意v的取值范围 
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=0;i<n;i++)	scanf("%d",&a[i]);
	
		int k=0;
		for(int i=0;i<n-1;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				v[k]=a[i]+a[j];
				k++;
			}
		}
		sort(v,v+k,cmp);
		printf("%d",v[0]);
		for(int it=1;it<m;it++)
			printf(" %d",v[it]);
		printf("n");	
	}
	return 0;
}

最后

以上就是明亮饼干为你收集整理的2021暑期积分赛一的全部内容，希望文章能够帮你解决2021暑期积分赛一所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。