A - {A} + {B}
给你两个集合，要求{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
使用set进行去重排序，直接输出就行（代码输出的地方我用for(auto x : s)复杂了，可以简化)
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<set>
using namespace std;
int main() {
int a, b;
int c;
set<int> s;
while (scanf("%d %d", &a, &b) != EOF) {
s.clear();
for (int i = 0; i < a + b; i++) {
cin >> c;
s.insert(c);
}
int k = 0;
for (auto x : s) {
k++;
}
int p = 0;
for (auto x : s) {
cout << x;
if (p != k - 1)
cout << ' ';
p++;
}
cout << '\n';
}
return 0;
}B - Train Problem I
As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.
Input
The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.
Output
The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.
Sample Input
3 123 321
3 123 312
Sample Output
Yes.
in
in
in
out
out
out
FINISH
No.
FINISH
For the first Sample Input, we let train 1 get in, then train 2 and train 3.
So now train 3 is at the top of the railway, so train 3 can leave first, then train 2 and train 1.
In the second Sample input, we should let train 3 leave first, so we have to let train 1 get in, then train 2 and train 3.
Now we can let train 3 leave.
But after that we can't let train 1 leave before train 2, because train 2 is at the top of the railway at the moment.
So we output "No.".
使用栈stack
for (i = 0; i < n; i++){
st.push(r[i]);
a[sic++] = 0;
while (st.empty() == 0 && st.top() == c[ans]) {
a[sic++] = 1;
ans++;
st.pop();
}
}进行记录。
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<stack>
using namespace std;
int main() {
stack<char> st;
string r, c;
int n, sic/*记录进入*/, i, ans/*出*/;
int a[10010];
while (scanf("%d", &n) != EOF) {
cin >> r >> c;
st = stack<char>();
sic = 0; ans = 0;
for (i = 0; i < n; i++){
st.push(r[i]);
a[sic++] = 0;
while (st.empty() == 0 && st.top() == c[ans]) {
a[sic++] = 1;
ans++;
st.pop();
}
}
if (ans != n)
cout << "No.\n";
else {
cout << "Yes.\n";
for (i = 0; i < sic; i++) {
if (a[i] != 0)
cout << "out\n";
else
cout << "in\n";
}
}
cout << "FINISH\n";
}
return 0;
}C - Alice, Bob and Candies
There are n candies in a row, they are numbered from left to right from 1 to n. The size of the i-th candy is ai.
Alice and Bob play an interesting and tasty game: they eat candy. Alice will eat candy from left to right, and Bob — from right to left. The game ends if all the candies are eaten.
The process consists of moves. During a move, the player eats one or more sweets from her/his side (Alice eats from the left, Bob — from the right).
Alice makes the first move. During the first move, she will eat 1 candy (its size is a1). Then, each successive move the players alternate — that is, Bob makes the second move, then Alice, then again Bob and so on.
On each move, a player counts the total size of candies eaten during the current move. Once this number becomes strictly greater than the total size of candies eaten by the other player on their previous move, the current player stops eating and the move ends. In other words, on a move, a player eats the smallest possible number of candies such that the sum of the sizes of candies eaten on this move is strictly greater than the sum of the sizes of candies that the other player ate on the previous move. If there are not enough candies to make a move this way, then the player eats up all the remaining candies and the game ends.
For example, if n=11 and a=[3,1,4,1,5,9,2,6,5,3,5], then:
move 1: Alice eats one candy of size 3 and the sequence of candies becomes [1,4,1,5,9,2,6,5,3,5].
move 2: Alice ate 3 on the previous move, which means Bob must eat 4 or more. Bob eats one candy of size 5 and the sequence of candies becomes [1,4,1,5,9,2,6,5,3].
move 3: Bob ate 5 on the previous move, which means Alice must eat 6 or more. Alice eats three candies with the total size of 1+4+1=6 and the sequence of candies becomes [5,9,2,6,5,3].
move 4: Alice ate 6 on the previous move, which means Bob must eat 7 or more. Bob eats two candies with the total size of 3+5=8 and the sequence of candies becomes [5,9,2,6].
move 5: Bob ate 8 on the previous move, which means Alice must eat 9 or more. Alice eats two candies with the total size of 5+9=14 and the sequence of candies becomes [2,6].
move 6 (the last): Alice ate 14 on the previous move, which means Bob must eat 15 or more. It is impossible, so Bob eats the two remaining candies and the game ends.
Print the number of moves in the game and two numbers:
a — the total size of all sweets eaten by Alice during the game;
b — the total size of all sweets eaten by Bob during the game.
Input
The first line contains an integer t (1≤t≤5000) — the number of test cases in the input. The following are descriptions of the t test cases.
Each test case consists of two lines. The first line contains an integer n (1≤n≤1000) — the number of candies. The second line contains a sequence of integers a1,a2,…,an (1≤ai≤1000) — the sizes of candies in the order they are arranged from left to right.
It is guaranteed that the sum of the values of n for all sets of input data in a test does not exceed 2⋅105.
Output
For each set of input data print three integers — the number of moves in the game and the required values a and b.
Example
Input
7
11
3 1 4 1 5 9 2 6 5 3 5
1
1000
3
1 1 1
13
1 2 3 4 5 6 7 8 9 10 11 12 13
2
2 1
6
1 1 1 1 1 1
7
1 1 1 1 1 1 1
Output
6 23 21
1 1000 0
2 1 2
6 45 46
2 2 1
3 4 2
4 4 3
这道题没有用STL，直接暴力了，稍微有点麻烦。
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<vector>
using namespace std;
int main() {
//vector<int> v;
int n;//测试次数
int num;//糖果数目
int q, h;//前一个人的糖果大小与后一个人的糖果大小
int alla, allb;
int sic;//移动次数
int i, a, peo;//左/右
int ans,kac;//是否吃完
cin >> n;
while (n--) {
int v[200010];
cin >> num;
for (i = 0; i < num; i++){
cin >> v[i];
}
q = v[0]; sic = 1; alla = v[0]; v[0] = 0; kac = 0;
allb = 0; a = num
1; peo = 1; i = 1; ans = num - 1;
h = 0;
for (; a >= i;) {
h = 0;
if (peo == 1) {
for (; i <= a; a--) {
h = h + v[a];
kac++;
v[a] = 0;
if (h > q) {
allb += h;
q = h;
peo = 0;
sic++;
ans -= kac;
kac = 0;
a--;
break;
}
}
}
else {
for (; i <= a; i++) {
h = h + v[i];
v[i] = 0;
kac++;
if (h > q) {
alla += h;
q = h;
peo = 1;
sic++;
ans -= kac;
kac = 0;
i++;
break;
}
}
}
}
if (ans != 0)
sic++;
else
h = 0;
if (peo == 1)
allb += h;
else
alla += h;
printf("%d %d %d\n", sic, alla, allb);
}
return 0;
}D - Let the Balloon Rise
Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.
This year, they decide to leave this lovely job to you.
Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.
A test case with N = 0 terminates the input and this test case is not to be processed.
Output
For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.
Sample Input
5
green
red
blue
red
red
3
pink
orange
pink
0
Sample Output
red
pink
使用map，然后筛选即可。
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<map>
using namespace std;
int main() {
map<string, int> mp;
string x;
int n, all, c;
while (scanf("%d",&n)!=EOF) {
if (n == 0)
break;
mp.clear();
while (n--) {
cin >> x;
mp[x] = mp[x] + 1;
}c = 0;
string b;
for (auto x : mp)
if (x.second > c) {
b = x.first;
c = x.second;
}
cout << b << '\n';
}
return 0;
}E - 全排列
给出一个字符串S（可能有重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = "1312"，
输出为：
1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211
Input
输入一个字符串S（S的长度 <= 9，且只包括0 - 9的阿拉伯数字）
Output
输出S所包含的字符组成的所有排列
Sample Input
1312
Sample Output
1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211
直接使用全排列即可。
do {
printf("%s\n", a);
} while (next_permutation(a, a + n));#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<set>
using namespace std;
int main() {
//set<string> st;
char a[15];
int n;
cin >> a;
n = strlen(a);
sort(a, a + n);
do {
printf("%s\n", a);
} while (next_permutation(a, a + n));
return 0;
}F - 水果
夏天来了
好开心啊,呵呵,好多好多水果
Joe经营着一个不大的水果店.他认为生存之道就是经营最受顾客欢迎的水果.现在他想要一份水果销售情况的明细表,这样Joe就可以很容易掌握所有水果的销售情况了.
Input
第一行正整数N(0<N<=10)表示有N组测试数据.
每组测试数据的第一行是一个整数M(0<M<=100),表示工有M次成功的交易.其后有M行数据,每行表示一次交易,由水果名称(小写字母组成,长度不超过80),水果产地(小写字母组成,长度不超过80)和交易的水果数目(正整数,不超过100)组成.
Output
对于每一组测试数据,请你输出一份排版格式正确(请分析样本输出)的水果销售情况明细表.这份明细表包括所有水果的产地,名称和销售数目的信息.水果先按产地分类,产地按字母顺序排列;同一产地的水果按照名称排序,名称按字母顺序排序.
两组测试数据之间有一个空行.最后一组测试数据之后没有空行.
Sample Input
1
5
apple shandong 3
pineapple guangdong 1
sugarcane guangdong 1
pineapple guangdong 3
pineapple guangdong 1
Sample Output
guangdong
|----pineapple(5)
|----sugarcane(1)
shandong
|----apple(3)
使用两个map嵌套，进行排序输出。
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<map>
using namespace std;
//bool cmp1(string a, string b) {
// return a[0] < b[0];
//}
//bool cmp(pair<string, string> a, pair < string, string > b) {
// if (a.second != b.second)
// cmp1(a.second, b.second);
// else
// cmp1(a.first, b.first);
//}
int main() {
//map <string, string> ma;
/*map<map<string, string>, int> mp;
map<map<string,string>,int>::iterator it;*/
int n;
string a, b;
int k, num;
cin >> n;
while (n--)
{
map<string, map<string, int> >mp;
map<string, map<string, int> >::iterator it;
cin >> num;
while (num--) {
cin >> a >> b >> k;
mp[b][a] += k;
}
for (it = mp.begin(); it != mp.end(); it++)
{
cout << it->first << endl;
map<string, int>::iterator it2;
for (it2 = it->second.begin(); it2 != it->second.end(); it2++)
cout << " |----" << it2->first << "(" << it2->second << ")" << endl;
}
if (n != 0)
cout << endl;
}
return 0;
}H - 稳定排序
大家都知道，快速排序是不稳定的排序方法。
如果对于数组中出现的任意a[i],aj,其中a[i]==a[j]，在进行排序以后a[i]一定出现在a[j]之前，则认为该排序是稳定的。某高校招生办得到一份成绩列表，上面记录了考生名字和考生成绩。并且对其使用了某排序算法按成绩进行递减排序。现在请你判断一下该排序算法是否正确，如果正确的话，则判断该排序算法是否为稳定的。
Input
本题目包含多组输入，请处理到文件结束。
对于每组数据，第一行有一个正整数N(0<N<300)，代表成绩列表中的考生数目。
接下来有N行，每一行有一个字符串代表考生名字(长度不超过50，仅包含'a'~'z'),和一个整数代表考生分数(小于500)。其中名字和成绩用一个空格隔开。
再接下来又有N行，是上述列表经过某排序算法以后生成的一个序列。格式同上。
Output
对于每组数据，如果算法是正确并且稳定的，就在一行里面输出"Right"。如果算法是正确的但不是稳定的，就在一行里面输出"Not Stable"，并且在下面输出正确稳定排序的列表，格式同输入。如果该算法是错误的，就在一行里面输出"Error",并且在下面输出正确稳定排序的列表，格式同输入。
请在这里输入引用内容
注意，本题目不考虑该排序算法是错误的，但结果是正确的这样的意外情况。
Sample Input
3
aa 10
bb 10
cc 20
cc 20
bb 10
aa 10
3
aa 10
bb 10
cc 20
cc 20
aa 10
bb 10
3
aa 10
bb 10
cc 20
aa 10
bb 10
cc 20
Sample Output
Not Stable
cc 20
aa 10
bb 10
Right
Error
cc 20
aa 10
bb 10
这道题开始使用map，发现排序有问题，使用unordered_map的时候还是有问题，不知道是哪里逻辑出了错。
错误代码如下
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<map>
#include<unordered_map>
using namespace std;
bool cmp(pair<string, int> a, pair<string, int> b) {
//if (a.second != b.second)
return a.second > b.second;
//else
// return a.first < b.first;
}
int main() {
int n, i;
int sic;
int a; string b;
while (scanf("%d", &n) != EOF) {
unordered_map<string, int> mp;
//unordered_map<int, string> it;
sic = 0;//Right
for (i = 0; i < n; i++){
cin >> b >> a;
mp[b] = a;
}
vector<pair<string, int>> v(mp.begin(), mp.end());
sort(v.begin(), v.end(), cmp);
for (auto x:v){
cin >> b >> a;
if (x.first != b && sic != 2) {
sic = 1;//Not Stable
}
if (x.second != a) {
sic = 2;//Error
}
}
if (sic == 0)
cout << "Right\n";
else {
if (sic == 1)
cout << "Not Stable\n";
else
cout << "Error\n";
for (auto x : v)
cout << x.first << ' ' << x.second << '\n';
}
}
return 0;
}最后结构体真相，老老实实用结构体去了。
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<map>
#include<unordered_map>
using namespace std;
struct P {
string name;
int v;
};
P s[303], s1[303];
int main()
{
int n;
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> s[i].name >> s[i].v;
}
for (int i = 0; i < n; i++) {
cin >> s1[i].name >> s1[i].v;
}
for (int j = 1; j < n; j++) {
P key = s[j];
int i = j - 1;
while (i >= 0 && s[i].v < key.v) {
s[i + 1] = s[i];
i--;
}
s[i + 1] = key;
}
int sic = 1;
for (int i = 0; i < n; i++) {
if (s1[i].v != s[i].v) {
sic = 0; break;
}
if (s1[i].name != s[i].name && s1[i].v == s[i].v) {
sic = 2;
}
}
if (sic == 1)
cout << "Right" << endl;
else if (sic == 2)
cout << "Not Stable" << endl;
else if (sic == 0)
cout << "Error" << endl;
if (sic != 1)
for (int i = 0; i < n; i++)
cout << s[i].name << " " << s[i].v << endl;
}
return 0;
}
京公网安备 11010502036488号