首页 > 代码库 > 2014 ACM/ICPC 牡丹江赛区现场赛
2014 ACM/ICPC 牡丹江赛区现场赛
最近突然感觉状态不佳，可能是天冷的缘故？
赛后来做牡丹江赛区的题目
【A】3819 Average Score -- 签到题
【B】
【C】
【D】
【E】
【F】
【G】
【H】
【I】
【J】
【K】3829 Known Notation -- 贪心 + 模拟
【A】3819 Average Score -- 签到题
Bob is a freshman in Marjar University. He is clever and diligent. However, he is not good at math, especially in Mathematical Analysis.
After a mid-term exam, Bob was anxious about his grade. He went to the professor asking about the result of the exam. The professor said:
"Too bad! You made me so disappointed."
"Hummm... I am giving lessons to two classes. If you were in the other class, the average scores of both classes will increase."
Now, you are given the scores of all students in the two classes, except for the Bob‘s. Please calculate the possible range of Bob‘s score. All scores shall be integers within [0, 100].
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers N (2 <= N <= 50) and M (1 <= M <= 50) indicating the number of students in Bob‘s class and the number of students in the other class respectively.
The next line contains N - 1 integers A1, A2, .., AN-1 representing the scores of other students in Bob‘s class.
The last line contains M integers B1, B2, .., BM representing the scores of students in the other class.
Output
For each test case, output two integers representing the minimal possible score and the maximal possible score of Bob.
It is guaranteed that the solution always exists.
Sample Input
24 35 5 54 4 36 55 5 4 5 31 3 2 2 1
Sample Output
4 42 4
题意：
简单明了，求平均数，然后找上限和下限
分析：
没有分析
代码：
#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;int T, N, M, x;double av1, av2;int main(){ scanf( "%d", &T ); while( T-- ) { scanf( "%d %d", &N, &M ); av1 = 0.0, av2 = 0.0; for( int i = 0; i < N-1; ++i ) { scanf( "%d",&x ); av1 += x; } av1 /= (N-1); for( int i = 0; i < M; ++i ) { scanf( "%d",&x ); av2 += x; } av2 /= M; double minn = ceil(av2); if( minn == av2 ) minn++; double maxx = floor(av1); if( maxx == av1 ) maxx--; printf( "%.0f %.0f\n", minn, maxx ); } return 0; }
【K】3829 Known Notation -- 贪心 + 模拟
Do you know reverse Polish notation (RPN)? It is a known notation in the area of mathematics and computer science. It is also known as postfix notation since every operator in an expression follows all of its operands. Bob is a student in Marjar University. He is learning RPN recent days.
To clarify the syntax of RPN for those who haven‘t learnt it before, we will offer some examples here. For instance, to add 3 and 4, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand. The arithmetic expression written "3 - 4 + 5" in conventional notation would be written "3 4 - 5 +" in RPN: 4 is first subtracted from 3, and then 5 added to it. Another infix expression "5 + ((1 + 2) × 4) - 3" can be written down like this in RPN: "5 1 2 + 4 × + 3 -". An advantage of RPN is that it obviates the need for parentheses that are required by infix.
In this problem, we will use the asterisk "*" as the only operator and digits from "1" to "9" (without "0") as components of operands.
You are given an expression in reverse Polish notation. Unfortunately, all space characters are missing. That means the expression are concatenated into several long numeric sequence which are separated by asterisks. So you cannot distinguish the numbers from the given string.
You task is to check whether the given string can represent a valid RPN expression. If the given string cannot represent any valid RPN, please find out the minimal number of operations to make it valid. There are two types of operation to adjust the given string:
- Insert. You can insert a non-zero digit or an asterisk anywhere. For example, if you insert a "1" at the beginning of "2*3*4", the string becomes "12*3*4".
- Swap. You can swap any two characters in the string. For example, if you swap the last two characters of "12*3*4", the string becomes "12*34*".
The strings "2*3*4" and "12*3*4" cannot represent any valid RPN, but the string "12*34*" can represent a valid RPN which is "1 2 * 34 *".
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
There is a non-empty string consists of asterisks and non-zero digits. The length of the string will not exceed 1000.
Output
For each test case, output the minimal number of operations to make the given string able to represent a valid RPN.
Sample Input
31*111*234***
Sample Output
102
题意：
给出一个可能不完整的后缀表达式，问最少需要多少次操作能够将其变为合法的后缀表达式
操作有两个，一个是insert，一个是swap
分析：想不出如何进行构造或者说不知道如何去贪心。看了别人的题解后清楚了思路。
需要注意的几点是：
1. 操作符op 数量不能少于 数字num的数量，否则无法完成运算，后缀表达式不合法
2. 全为数字没有操作符，可以将其当作一个数字，不需要任何操作，输出0即可
3. 末尾不能是数字，否则也是非法的后缀表达式。
具体做法：
扫描整个字符串统计op和num的数量。
如果num数量小于等于op数量，那么直接在最前面插入op-num+1个数字
考虑最后一位不能是数字的情况
再扫描一遍字符串，遇到不合法的‘*‘，和最后的数字进行交换。
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int T;char str[1010];int main(){ scanf( "%d\n", &T ); while( T-- ) { gets(str); int len = strlen( str ); int op = 0, num = 0; for( int i = 0; i < len; ++i ) { if( str[i] == ‘*‘ ) op++; else num++; } if( op == 0 ) { puts( "0" ); continue; } int res = 0; int tot = 0; if( num <= op ) { res = op - num + 1; num += res; tot += res; } if( str[len - 1] != ‘*‘ ) { for( int i = 0; i < len; ++i ) { if( str[i] == ‘*‘ ) { swap( str[i], str[len - 1] ); res++; break; } } } for( int i = 0; i < len; ++i ) { if( str[i] == ‘*‘ ) { if( tot < 2 ) { for( int j = len - 1; j >= 0; --j ) { if( str[j] != ‘*‘ ) { swap( str[j], str[i] ); res++; tot++; break; } } } else tot--; } else tot++; } printf( "%d\n", res ); } return 0;}
2014 ACM/ICPC 牡丹江赛区现场赛