概述：ACM全真模拟，5小时10题，共AC 9题，排名第二
Test A
给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
Output
对每组测试数据按从大到小的顺序输出前m大的数。
Sample Input
5 3
3 -35 92 213 -644
Sample Output
213 92 3
Hint
请用VC/VC++提交
题解：
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
bool cmp(int x, int y) {
return x > y;
}
int main() {
int n, m;
int* a;
while (scanf("%d %d", &n, &m) != EOF) {
a = (int*)malloc(n*sizeof(int));
int i;
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n,cmp);
printf("%d", a[0]);
for (i = 1; i < m; i++) {
printf(" %d", a[i]);
}
printf("\n");
}
return 0;
}
一开始用的是multiset容器，不料这个容器的速度略慢，导致超时，所以应该使用数组
另外一点，就是末位是否输入空格的问题，这个问题在本次测验中体现的及其明显，而题解中给的方案恰好完美的解决了这一问题
Test B
These days, I am thinking about a question, how can I get a problem as easy as A+B? It is fairly difficulty to do such a thing. Of course, I got it after many waking nights.
Give you some integers, your task is to sort these number ascending (升序).
You should know how easy the problem is now!
Good luck!
Input
Input contains multiple test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. Each test case contains an integer N (1<=N<=1000 the number of integers to be sorted) and then N integers follow in the same line.
It is guarantied that all integers are in the range of 32-int.
Output
For each case, print the sorting result, and one line one case.
Sample Input
2
3 2 1 3
9 1 4 7 2 5 8 3 6 9
Sample Output
1 2 3
1 2 3 4 5 6 7 8 9
题解：
#include<iostream>
#include<queue>
#include <algorithm>
using namespace std;
int main() {
int n;
scanf("%d", &n);
while (n--) {
priority_queue<int, vector<int>, greater<int>> sq;
int m;
scanf("%d", &m);
int x;
for (int i = 1; i <= m; i++) {
scanf("%d", &x);
sq.push(x);
}
int i = 1;
printf("%d", sq.top());
sq.pop();
while (!sq.empty()) {
printf(" %d", sq.top());
sq.pop();
i++;
}
printf("\n");
}
return 0;
}
依然是末位空格的问题。。不解释
Test C
输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。
你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。
Input
输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。
输入数据保证：分割得到的非负整数不会大于100000000；输入数据不可能全由‘5’组成。
Output
对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。
Sample Input
0051231232050775
Sample Output
0 77 12312320
题解：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main() {
char str[1000 + 5];
char number[1000][1000];
long long num[1000 + 5];
while (scanf("%s", str) != EOF) {
int i = 0;
memset(number, '\0', sizeof(number));
memset(num, 0, sizeof(num));
char* p = strtok(str, "5");
while (p) {
strcpy(number[i++], p);
p = strtok(NULL, "5");
}
int j;
for (j = 0; j < i; j++) {
long long sum = 0;
for (int k = 0; k < strlen(number[j]); k++) {
sum = sum * 10 + number[j][k] - '0';
}
num[j] = sum;
}
sort(num, num + j);
printf("%d", num[0]);
for (int m = 1; m < j; m++) {
printf(" %d", num[m]);
}
printf("\n");
}
return 0;
}
这道题一次性AC的，不解释了，重点是应用了一个strtok函数
Test D
有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。
Input
输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。
Output
对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。
Sample Input
3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0
Sample Output
Yes
No
题解
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
char a[1005][50],b[1005][50];
int k[1005];
int main()
{
int n,i=0,sum,l;
char temp[50];
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
memset(a,NULL,sizeof(a));
memset(b,NULL,sizeof(b));
memset(k,0,sizeof(k));
memset(temp,NULL,sizeof(temp));
for(i=0;i<n;i++)
scanf("%s %s",a[i],b[i]);
for(i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(strcmp(a[i],b[j])!=0) //没有被打败过
{
k[i]++;
// printf("k=%d\n",k[i]);
}
}
}
sum=0,l=0;
for(i=0;i<n;i++)
{
if(k[i]==n) //第一个没有被打败过的人
{
l=1; //一个打败的人都没有l==0。
strcpy(temp,a[i]);
break;
}
}
if(l==0)
{
printf("No\n");
continue;
}
for(i=0;i<n;i++)
{
if(k[i]==n)
{
if(strcmp(temp,a[i])!=0) //有不同的人就说明有多个人没有被打败过
{
sum=1;
printf("No\n");
break;
}
}
}
if(sum==0)
printf("Yes\n");
}
return 0;
}
这道题因为一开始没有思路，没写出来，后来查阅可知：
题目要求产生冠军，其实，仔细看一下题目就可以知道，其实冠军的产生很简单，就是所给的数据中存在唯一没有被打败的人，而对于谁打败谁，根本没有关系。
换句话说，只要把所有名字列出来，并记录他们分别被打败的次数，再从头到尾查一下总共多少人没有被打败过，如果只有一个人 那就yes了。
另外网上还给出了特别简单的方法：利用Set容器
理解题意： 这个题很容易理解为最后的冠军为间接赢了所有人的选手，但其实冠军是所有选手中没有输过的那一个 解题思路： 利用集合set中的元素只出现一次的特性，把输入的所有选手都放到一个集合A中，失败的选手放到集合B中，如果A比B多一个，则说明产生了冠军
代码如下
#include <bits/stdc++.h>
using namespace std;
int main()
{
set<string>A,B;
string s1,s2;
int n;
while(cin>>n&&n){
for(int i =0 ;i < n; i++){
cin>>s1>>s2;
A.insert(s1);
A.insert(s2);
B.insert(s2);
}
if(A.size()-B.size()==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
A.clear();
B.clear();
}
return 0;
}
今后要加强复习Set容器，它和multiset的不同之处在于其元素不能重复
Test E
Football is one of the greatest games in the world. Lots of people like to play football. After one season of matches, the header has to calculate the last scores of every team. He is too lazy that he doesn’t want to calculate, so he asks you to write a program for him to solve the problem.
Here are the rules:
1 Every team has to match with all the other teams.
2 Every two teams have to match for two times,one at home and one away.
3 In one match, the winner will get 3 points, the loser will get 0 point. If it is draw, both of them will get 1 point.
Input
The input consists of many test cases. In each case, there will be a number N in the first line which means the number of teams. Followed by N * (N – 1)lines. Each line stands for a match between two teams. The format is: “Team1 VS Team2 p:q”, p stands for the balls that Team1 has kicked in and q stands for the balls that Team2 has kicked in. p and q are not greater than 9.
Process to the end of file.
Output
For each test case, output the teams and their scores in descending order. One line a team, the format is: “TeamX scores”. If two teams get the same score, the one with high net goals will be ahead, which net goal means the difference between the total balls that the team kicked in and the total balls that the team lost. IE: if one team kicked in 30 balls and lost 40 balls, then the net goal is 30 – 40 = -10. If two teams have the same score and the same net goal, the one whose kicked in balls is bigger will be ahead. If two teams have the same score and the same net goal and the same kicked in balls, they will be outputed in alphabetic order.
Output a blank line after each test case.
Sample Input
3
Manchester VS Portsmouth 3:0
Liverpool VS Manchester 1:1
Liverpool VS Portsmouth 0:0
Portsmouth VS Manchester 1:1
Manchester VS Liverpool 2:1
Liverpool VS Portsmouth 1:2
Sample Output
Manchester 8
Portsmouth 5
Liverpool 2
Huge input, scanf is recommended.
Hint
Hint
暂时没做此题，跳过
Test F
给你两个集合，要求{A} + {B}.
注:同一个集合中不会有两个相同的元素.
Input
每组输入数据分为三行,第一行有两个数字n,m(0<n,m<=10000),分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.每个元素为不超出int范围的整数,每个元素之间有一个空格隔开.
Output
针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,每个元素之间有一个空格隔开.
Sample Input
1 2
1
2 3
1 2
1
1 2
Sample Output
1 2 3
1 2
题解：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
int main() {
int n, m;
while (scanf("%d %d", &n, &m) != EOF) {
int k = n > m ? n : m;
int A[10000];
int B[10000];
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
int alen = 0;
int blen = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &A[i]);
alen++;
}
for (int i = 0; i < m; i++){
scanf("%d",&B[i]);
blen++;
}
int l,j;//l控制b数组,j控制a数组
for ( l = 0; l < blen; l++) {
for ( j = 0; j < alen; j++) {
if (B[l] == A[j]) {
goto As;
}
}
if (j == alen) {
A[alen++] = B[l];
}
As:;
}
sort(A, A + alen);
printf("%d", A[0]);
for (int i = 1; i < alen; i++) {
printf(" %d", A[i]);
}
printf("\n");
}
return 0;
}
一次性AC的，不多解释
Test G
Welcome to HDU to take part in the first CCPC girls’ competition!
As a pretty special competition, many volunteers are preparing for it with high enthusiasm.
One thing they need to do is blowing the balloons.
Before sitting down and starting the competition, you have just passed by the room where the boys are blowing the balloons. And you have found that the number of balloons of different colors are strictly different.
After thinking about the volunteer boys’ sincere facial expressions, you noticed that, the problem with more balloon numbers are sure to be easier to solve.
Now, you have recalled how many balloons are there of each color.
Please output the solving order you need to choose in order to finish the problems from easy to hard.
You should print the colors to represent the problems.
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
题解
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct bolloon {
char color[10];
int ID;
};
bool operator<(bolloon s1, bolloon s2) {
return s1.ID < s2.ID;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
bolloon bb;
priority_queue<bolloon> sq;
int n;
char color[10];
int ID;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s %d", color, &ID);
strcpy(bb.color, color);
bb.ID = ID;
sq.push(bb);
}
printf("%s", sq.top().color);
sq.pop();
while (!sq.empty()) {
printf(" %s", sq.top().color);
sq.pop();
}
printf("\n");
}
}
一开始PE，哈哈，又是因为空格的问题，好在我已经完美记住了它的解决方案
Test H
Jackson wants to know his rank in the class. The professor has posted a list of student numbers and marks. Compute Jackson’s rank in class; that is, if he has the top mark(or is tied for the top mark) his rank is 1; if he has the second best mark(or is tied) his rank is 2, and so on.
Input
The input consist of several test cases. Each case begins with the student number of Jackson, an integer between 10000000 and 99999999. Following the student number are several lines, each containing a student number between 10000000 and 99999999 and a mark between 0 and 100. A line with a student number and mark of 0 terminates each test case. There are no more than 1000 students in the class, and each has a unique student number.
Output
For each test case, output a line giving Jackson’s rank in the class.
Sample Input
20070101
20070102 100
20070101 33
20070103 22
20070106 33
0 0
Sample Output
2
代码暂不提供，这个题也是搞了好长时间，排序本身不难，但是输出名次搞的晕头转向的，不知道怎么用简洁的代码解决分数相同的问题
Test I
输入一个字符串，判断其是否是C的合法标识符。
Input
输入数据包含多个测试实例，数据的第一行是一个整数n,表示测试实例的个数，然后是n行输入数据，每行是一个长度不超过50的字符串。
Output
对于每组输入数据，输出一行。如果输入数据是C的合法标识符，则输出"yes"，否则，输出“no”。
Sample Input
3
12ajf
fi8x_a
ff ai_2
Sample Output
no
yes
no
题解：
#include<iostream>
#include<cstring>
using namespace std;
int main() {
int n;
char str[50 + 5];
scanf("%d", &n);
getchar();
while (n--) {
gets(str);
int ifok = 1;
int i;
for (i = 0; i < strlen(str); i++) {
if (str[0] >= '0' && str[0] <= '9') {
ifok = 0;
break;
}
else {
if (!((str[i] >= '0' && str[i] <= '9') || str[i] == '_' || (str[i] >= 'A' && str[i] <= 'Z') || (str[i] >= 'a' && str[i] <= 'z'))) {
ifok = 0;
break;
}
}
}
if (ifok == 1) {
printf("yes\n");
}
else {
printf("no\n");
}
}
return 0;
}
Test J
输入一个十进制数N，将它转换成R进制数输出。
Input
输入数据包含多个测试实例，每个测试实例包含两个整数N(32位整数)和R（2<=R<=16, R<>10）。
Output
为每个测试实例输出转换后的数，每个输出占一行。如果R大于10，则对应的数字规则参考16进制（比如，10用A表示，等等）。
Sample Input
7 2
23 12
-4 3
Sample Output
111
1B
-11
题解：
#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
char Switch(int a);
int main() {
int n, r;
while (scanf("%d %d", &n, &r) != EOF) {
stack<int> sq;
int iffu = 0;
if (n < 0) {
n = -n;
iffu = 1;
}
int temp = n;
do {
int d = temp % r;
sq.push(d);
temp /= r;
} while (sqrt(temp) != 0);
if (iffu == 1) {
printf("-");
}
while (!sq.empty()) {
int tt = sq.top();
if (tt >= 10) {
printf("%c", Switch(tt));
}
else {
printf("%d", tt);
}
sq.pop();
}
printf("\n");
}
}
char Switch(int a) {
char b;
switch (a) {
case 10:b='A'; break;
case 11:b='B'; break;
case 12:b='C'; break;
case 13:b='D'; break;
case 14:b='E'; break;
case 15:b='F'; break;
case 16:b='G'; break;
case 17:b='H'; break;
case 18:b='I'; break;
case 19:b='J'; break;
case 20:b='K'; break;
case 21:b='L'; break;
case 22:b='M'; break;
case 23:b='N'; break;
case 24:b='O'; break;
case 25:b='P'; break;
case 26:b='Q'; break;
case 27:b='R'; break;
case 28:b='S'; break;
case 29:b='T'; break;
case 30:b='U'; break;
case 31:b='V'; break;
case 32:b='W'; break;
case 33:b='X'; break;
case 34:b='Y'; break;
case 35:b='Z'; break;
}
return b;
}
代码一次性通过！
京公网安备 11010502036488号