[第11届华南农业大学ACM程序设计竞赛 网络同步赛]题目及现场作答代码

A. Local Minimum

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 220 Accepted Submission(s) : 100

Description
There is an array contains n integers, no any 2 integers are same. Local minimum means an integer is less than its previous one and next one (ie. M[i-1] >M[i] < M[i + 1], 1 < i < n). The array is special, it is guarantee M[1] > M[2] and M[n - 1] < M[n]. Now, give you the array, please find out is there a local minimum exist in the array.

Input
The 1st line of input contains only 1 integer T (T <= 10), indicate the number of test cases.
The 1st line of each test case contains only 1 integer n (3 <= n <= 100), indicate the size of the array.
The 2nd line of each test case contains n integers, indicate the element of the array, the maximum of the integers will not exceed 100.

Output
For each test, if there is local minimum exist, please print "Yes", and otherwise print "No".

Sample Input
2
5
5 4 3 1 2
6
100 99 1 2 98 101

Sample Output
Yes
Yes

Accepted：

#include<stdio.h>
int main(){
	int T;
	scanf("%d", &T);
	int M[1001];
	while(T--){
		int n, i, flag = 0;
		scanf("%d", &n);
		for(i = 1; i <= n; ++i){
			scanf("%d", &M[i]);
		}
		for(i = 2; i < n; ++i){
			if(M[i-1] > M[i] && M[i] < M[i + 1]){
				flag = 1;
				break;
			}
		}
		if(flag == 1)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

B. Fibonacci Formula

Time Limit : 5000/2000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 187 Accepted Submission(s) : 76

Description
It is all known that the Fibonacci sequence is calculated by adding the previous two members.
So the sequence, with the first 2 members is both 1, is:
F(1)=1; F(2)=1;
F(n) = F(n-1) + F(n-2) (n>2).
Thus the sequence is 1, 1, 2, 3, 5, 8, etc.

As a matter of fact, the sequence can be calculated as a formula following.

F(n) = (α ^ n + β ^ n) / sqrt(5)

Where α = 1.618033988749895, β = -0.6180339887498949.

Actually, if a sequence is F(n) = F(n-1) + F(n-2), it does not matter what F(1) and F(2) are, the sequence can be calculated by F(n) = x * α^n + y * β^n. Now give you F(1) and F(2), please output x and y for the sequence F(n).

Input
The 1st line of the test case is an integer T (T <= 50000), which indicates the number of test cases.
And then T lines follow, for each case, there are two integer, which is F(1) and F(2) (-100 <= F(1), F(2) <= 100).

Output

Output two number x and y for the sequence F(n) for each case. In order to make the problem easier, you only need to output the absolute value of the result and round it to 1 digit after the decimal point.

Sample Input
2
1 1
0 0

Sample Output
0.4 0.4
0.0 0.0

Accepted：

#include<stdio.h>
#include<cmath>
double absd(double n){
	if(n < 0)
		return -n;
	return n;
}
int main(){
	int T;
	double F[5], x, y;
	double a = 1.618033988749895;
	double b = -0.6180339887498949;
	double a3 = pow(a, 3);
	double a4 = pow(a, 4);
	double b3 = pow(b, 3);
	double b4 = pow(b, 4);
	scanf("%d", &T);
	while(T--){
		scanf("%lf%lf", &F[1], &F[2]);
		F[3] = F[1] + F[2];
		F[4] = F[2] + F[3];
		y = (F[4] * a3 / a4 - F[3]) / (a3 * b4 / a4 - b3);
		x = (F[3] - b3 * y) / a3;
		printf("%.1lf %.1lf\n", absd(x), absd(y));
	}
	return 0;
}

C. StoneLand

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 139 Accepted Submission(s) : 15

Description
Zayhero likes traveling very much. His current step is StoneLand.

Everything in StoneLand is copied from the same stone, so Zayhero get confuse and cannot find his way out. Finally, he found a stone gate which lead to the exit. However, the stone gate needs a password to open it. After several attempts, Zayhero found that the password is n continuous 'A's (ie. AAA or AAAAAAAA, and etc.).

There is a special keyboard in front of the stone gate, which has several keys Zayhero can press to enter the password:
1) Press 'A', to input a single 'A';
2) Press 'C1', to select all content Zayhero has input;
3) Press 'C2', to copy all selected content into memory;
4) Press 'C3', to append all copied content into the end of the input

Please help Zayhero to find out what is the minimum press to enter n continuous 'A's.

Explanation of sample:

To press 11 continuous 'A's, Zayhero can:
1) Press 5 continuous 'A's;
2) Press 'C1', 'C2', 'C3', which copy and append 5 continuous 'A's into the back of the origin content, thus 10 'A's are inputted;
3) Press 1 more 'A's, and there are 11 'A's inputted.
Zayhero needs 9 presses totally.

To press 12 continuous 'A's, Zayhero can:
1) Press 3 continuous 'A's;
2) Press 'C1', 'C2', 'C3', which copy and append 3 continuous 'A's into the back of the origin content, thus 6 'A's are inputted;
3) Press 'C3' again, append 3 more 'A's to the input, thus there are 9 'A's;
4) Press 'C3' 1 more time, and there are 12 'A's.
Zayhero needs 8 presses totally.

Input
The 1st line of input contains only 1 integer T (T <= 20000), indicate the number of test cases.
Each test case contains only 1 integer n (n <= 10 ^ 6), indicate the password is n continuous 'A's.

Output
For each test case, print only 1 integer for each test case, indicate the minimum press Zayhero can press to enter the password. Please refer to sample output for more details.

Sample Input
3
5
11
12

Sample Output
Case 1: 5
Case 2: 9
Case 3: 8

Wrong Answer：

#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
int f[1000001];
int main(){
	int T, i;
	f[1] = 1;
	f[2] = 2;
	f[3] = 3;
	for(i = 4; i < 1000001; ++i){
		int sqr = sqrt((float)i);
		f[i] = min(f[i - 1] + 1, sqr + i / sqr + 1 + i % sqr);
		f[i] = min(f[i], i);
	}
	i = 0;
	scanf("%d", &T);
	while(T--){
		int n;
		scanf("%d", &n);
		printf("Case %d: %d\n", ++i, f[n]);
	}
	return 0;
}

D. WaterLand

Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 140 Accepted Submission(s) : 92

Description
Zayhero likes traveling very much. His current step is WaterLand. WaterLand is consisted by many rivers (numbered from 1 to n), all these rivers are origin from the source – the sea. The water from the sea will fill up the rivers through some water supply tunnels, each tunnel lead to exactly one river, and no two tunnels are lead to same river. Each tunnel is controlled by a single switch, if the switch in on, the river will be filled with water, otherwise the river will dry up.

Now, Zayhero found that some of these rivers are dry up since the switches are set off. Zayhero love to challenge himself, so he decide to set these switches on in order to fill ALL rivers from the 1st one to the n-th one.

However, the switches is special, if Zayhero change the status of the i-th switch, the switches from the (i+1)-th to n-th will change their status.
For example, there are 5 rivers in WaterLand, thus there are 5 tunnels and 5 switches, their current status are: on, off, on, on, on.
The 1st switch will not be changed since it is already on;
The 2nd switch will be changed since it is off, after that, the 2nd to the 5th switches will be changed at the same time, and thus the status will be: on, on, off, off, off;
After change the 3rd switch, the status will be: on, on, on, on, on, and all the rivers are filled with water now, Zayhero change 2 switches totally.

Now, please calculate how many switches are needed to be changed?

Input
The 1st line of input contains only 1 integer T (T <= 30), indicate the number of test cases.
There are 2 lines of each test case.
The 1st line of each test case contains only 1 integer n (n <= 10 ^ 4), indicate the number of rivers in WaterLand.
The 2nd line of each test case contains n integers Si, if Si = 0, indicate the status of the i-th switch is off, if Si = 1, indicate the status is on. It is guarantee that Si will always be 0 or 1.

Output
For each test case, print only 1 integer for each test case, indicate how many switches are needed to be changed by Zayhero. Please refer to sample output for more details.

Sample Input
3
5
1 0 1 1 1
5
1 0 0 1 1
5
0 1 0 1 0

Sample Output
Case 1: 2
Case 2: 2
Case 3: 5

Accepted：

#include<stdio.h>
int main(){
	int T, k = 1;
	scanf("%d", &T);
	while(T--){
		int n, i, ans = 0;
		int a[10000] = {0};
		scanf("%d", &n);
		for(i = 0; i <n; ++i){
			scanf("%d", &a[i]);
		}
		for(i = 0; i <n; ++i){
			if(a[i] == 0){
				for(int j = i; j < n; ++j){
					a[j] = (a[j] + 1) % 2;
				}
				++ans;
			}
		}
		printf("Case %d: %d\n", k, ans);
		++k;
	}
	return 0;
}

E. Prefix Sum

Time Limit : 6000/3000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 53 Accepted Submission(s) : 6

Description
A string v is a suffix string of a string w if string v can read from a position of string w and to the end of w.
For example, string bc is a suffix string of abc. but ab is not.
A string v is a prefix string of a string w if string v can read from the beginning of string w.
For example, string ab is prefix string of string abc, but bc and abcd are not.

For 2 strings s1 and s2, if there is a string s3 is both the prefix of s1 and s2, we call s3 is a common prefix of s1 and s2.
The longest common prefix of 2 strings is the longest common prefix string of all the common prefix strings among these 2 strings.

Your task is:
Give you the string, count the sum of the length of each of the longest common prefix string of each 2 suffix of the string.

Input
There are multi strings. One string per line. Each string is no longer than 10^5. The strings only contain A-Z and a-z.

Output
For each string, output the sum.

Sample Input
ABC
ABABA
AABB

Sample Output
0
7
2

[cce_cpp]//这道题没做[/cce_cpp]

F. Exam Statistics

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 187 Accepted Submission(s) : 81

Description
After the exam, statistics is a painful job for teachers. As there are so many students and subjects, the teacher will store the exam result into computers, and calculate it by input some commands.
There are 6 subjects in the exam: Chinese, Math, English, Politics, Physics and Chemistry. And there are 4 types of commands:

sum subject_ID: calculate the sum of the exam result of the target subject.
avg subject_ID: calculate the average of the exam result of the target subject.
max subject_ID: calculate the maximum of the exam result of the target subject.
min subject_ID: calculate the minimum of the exam result of the target subject.

You are asked to write a program that will help the teacher to finish the Simple Statistics.

Input
Input consists of multiple test cases, the 1st line of test data is an integer T (T <= 20), indicate the number of test cases.

Each test case starts with a line containing a positive integer n (n <= 1000), indicated the number of students.
Then n lines follow, each line contains 6 integers Ri (0 <= Ri <= 100) indicated the exam result of 6 subjects.
On the next line there is an integer m (m <= 20), indicated the number of commands.
Then m lines follow, each line contains 1 string and 1 integer, indicate the commands and subject_ID mention above, it is guarantee that the string will be one of "sum", "avg", "max", "min", and subject_ID will between 1 and 6.

Output
For each command, display the result. If the result is not an integer, round it into the nearest integer.

Sample Input
1
2
90 90 90 90 90 90
90 91 92 93 94 95
2
sum 1
avg 2

Sample Output
180
91

Accpeted：

#include<iostream>
#include<string>
using namespace std;
int a[1000][6];
int main(){
	cout.setf(ios::fixed);
	cout.precision(0);
	int T;
	cin >> T;
	int M[1001];
	while(T--){
		int n, m, i, j;
		cin >> n;
		for(i = 0; i < n; ++i){
			for(j = 0; j < 6; ++j){
				cin >> a[i][j];
			}
		}
		cin >> m;
		for(i = 0; i < m; ++i){
			int id;
			float ans = 0;
			string cmd;
			cin >> cmd >> id;
			--id;
			if(cmd == "sum"){
				for(j = 0; j < n; ++j){
					ans += a[j][id];
				}
			}else if(cmd == "avg"){
				for(j = 0; j < n; ++j){
					ans += a[j][id];
				}
				ans /= n;
			}else if(cmd == "max"){
				for(j = 0; j < n; ++j)
					if(ans < a[j][id])
						ans = a[j][id];
			}else if(cmd == "min"){
				ans = a[0][id];
				for(j = 0; j < n; ++j)
					if(ans > a[j][id])
						ans = a[j][id];
			}
			cout << ans << endl;
		}
	}
	return 0;
}

G. Poor Cell Phone Signals

Time Limit : 12000/6000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 62 Accepted Submission(s) : 9

Description
As a student in SCAU, you must have been suffering the poor cell phone signals, which often get you crazy. Getting no answer from your friends when using mobile-qq is nothing but a piece of cake. What else? Missing SMS is no longer a dream under the poor cell phone signals! You wanna surf the Internet with your mobile-phone in dormitory? I think it's a good idea to put down your phone and open your computer……Ok, stop~ Complaint is useless!
One day, SCAU and CMCC decide to solve the problem above by building some cell towers on dormitories. But here comes a problem. Due to the different physical features of a place, towers on different buildings have different coverage areas.
Let's simplify the problem:
The coverage area is a circle with certain radius. To save the cost, can you tell me how many towers at least to be build to cover the entire dormitories.

Input
There are multiple cases. End with EOF.
The first line of a case is a integer n (1 <= n <= 100), the number of dormitories (towers).
Then following n lines with three float number x, y, r. (-1000 <= x, y <= 1000, 0 < r <= 1000), (x, y) is the location of a dormitory and r is coverage radius of the cell tower on it.

Output

The least number of towers to be build to cover the entire dormitories.

Sample Input
2
-406.457734 -950.008225 128.310075
637.421699 -333.279118 80.669571
6
403.236760 416.225834 240.894500
255.312986 213.771553 116.424544
-590.686992 -575.514308 180.384586
-462.051247 -503.253768 164.271604
695.933857 -519.698202 177.853029
547.595746 430.545072 378.34457

Sample Output
2
3

Wrong Answer

#include<iostream>
#include<vector>
#include<iterator>
using namespace std;
struct d{
	double x, y, r;
	d(double x, double y, double r):x(x), y(y), r(r){}
};
int main(){
	int n, i, num;
	while(cin >> n){
		vector<d> v;
		for(i = 0; i < n; ++i){
			double x, y, r;
			cin >> x >> y >> r;
			v.push_back(d(x, y, r));
		}
		for(i = 0; i < v.size(); ++i){
			for(int j = 0; j < v.size(); ++j){
				if(i != j && v[i].x - v[i].r <= v[j].x && v[i].x + v[i].r >= v[j].x && v[i].y - v[i].r <= v[j].y && v[i].y + v[i].r >= v[j].y){
					v.erase(v.begin() + j);
					if(j < i)
						--i;
					--j;
				}
			}
		}
		cout << v.size() << endl;
	}
	return 0;
}

H. TreeLand

Time Limit : 9000/3000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 75 Accepted Submission(s) : 26

Description
Zayhero likes traveling very much. His current step is TreeLand, there is only 1 huge tree in it.

The tree has infinity nodes. The root of this tree is located at node with number 1. Each node has exactly 2 child-nodes, if the node is numbered I, the child-nodes are numbered I * 2 and I * 2 + 1.

Some edges of this tree grow some delicious fruits, Zayhero wants to eat these fruits. He will start climbing from the root of the tree, when he passes an edge, he will collect all fruits on that edge. But due to his power’s limited, he can’t go back from any node to its parent nodes.

Zayhero can choose to jump off the tree at any node, but he won't climb again. Please help him to calculate how many fruits he can collect at most.

The demo of Sample 1:

Node Number Fruit can be collect
1 0
2 0
3 10
4 0
5 13
6 19
7 10
8 0
9 9
10 13
11 13
12 19
13 19
14 10
15 16

So Zayhero could collect the most fruits by climbing to node 6 or 12 or 13. Since all other edge has not any fruit, so it is not necessary to process further after node 15.

Input
The 1st line of input contains only 1 integer T (T <= 20), indicate the number of test cases.
The 1st line of each test case contains only 1 integer n (n <= 10 ^ 4), indicate the number of edges contain fruits.
Then n lines follow, each line contains 2 integers Ni, Fi (1 < Ni <= 2 ^ 31 - 1, 1 <= Fi <= 10 ^ 5), indicate the edge (Ni / 2, Ni) contains Fi fruits on it.

Please notice that some edges may occur many times, Zayhero will collect ALL of them. Please refer to sample 3 for more details.

Output
For each test case, print only 1 integer for each test case, indicate the most fruits Zayhero can collect. Please refer to sample output for more details.

Sample Input
3
5
3 10
5 13
6 9
15 6
9 9
5
999999999 1
999999998 3
999999997 5
999999996 7
999999995 9
2
2 1
2 1

Sample Output
Case 1: 19
Case 2: 9
Case 3: 2

Accepted：

#include<stdio.h>
#include<map>
#include<iterator>
using namespace std;
int main(){
	int T, t = 0;
	scanf("%d", &T);
	while(T--){
		int n, i;
		scanf("%d", &n);
		map<int, int> m;
		for(i = 0; i <n; ++i){
			int a, b;
			scanf("%d%d", &a, &b);
			m[a] += b;
		}
		int max = 0, sum;
		for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it){
			sum = (*it).second;
			int k = (*it).first;
			while(k /= 2){
				sum += m[k];
			}
			if(max < sum)
				max = sum;
		}
		printf("Case %d: %d\n", ++t, max);
	}
	return 0;
}

I. MountainLand

Time Limit : 5000/2000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 336 Accepted Submission(s) : 23

Description
Zayhero likes traveling very much. His current step is MountainLand, which composed by a sequence of mountains, and these mountains may have different height.

Zayhero wants to challenge himself, so he wants to climb some mountains in MoutainLand. In order to make the challenge more difficult, he will choose the mountains by follow conditions:
1) He will choose at least 1 mountain to climb;
2) If he chooses more than 1 mountain, these mountains must locate in a continuous sequence;
3) If he chooses more than 1 mountain, the height of the most left mountain must LOWER than the most right one.

Please help to calculate how many mountains he can climb at most.

Input
The 1st line of input contains only 1 integer T (T <= 20), indicate the number of test cases.
Each test case contains 2 line.
The 1st line of each test case contains only 1 integer n (n <= 10 ^ 5), indicate the number of mountains in MountainLand.
The 2nd line of each test case contains n integers Hi (1 <= Hi <= 10 ^ 9), indicate the height of each mountain.

Output
For each test case, print only 1 integer for each test case, indicate the most mountains Zayhero can climb. Please refer to sample output for more details.

Sample Input
3
3
1 2 3
5
6 3 2 7 5
5
5 4 3 2 1

Sample Output
Case 1: 3
Case 2: 4
Case 3: 1

Time Limit Exceeded：

#include<stdio.h>
#include<map>
#include<iterator>
using namespace std;
int main(){
	int T, t = 0;
	scanf("%d", &T);
	while(T--){
		int n, i, ans = 0;
		int a[100000];
		scanf("%d", &n);
		for(i = 0; i < n; ++i){
			scanf("%d", &a[i]);
		}
		for(i = 0; i < n; ++i){
			int sum = 1;
			for(int j = n - 1; j > i; --j){
				if(a[i] < a[j]){
					sum = j - i + 1;
					break;
				}
			}
			//printf("d%d\n", sum);
			if(sum > ans)
				ans = sum;
		}
		printf("Case %d: %d\n", ++t, ans);
	}
	return 0;
}

区区不才。。。只做出5道题，这些是还没经过整理的现场作答代码，还请各位高手多多指教！

=======================签 名 档=======================
原文地址（我的博客）：http://www.clanfei.com/2012/04/574.html
欢迎访问交流，至于我为什么要多弄一个博客，因为我热爱前端，热爱网页，我更希望有一个更加自由、真正属于我自己的小站，或许并不是那么有名气，但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================