HPU 暑期集训 Day 3
今天主要讲了点基本的STL的用法。题写的有点吃力了，以后可能就写不完了，然后攒着写不完的题一天比一天多。
Nothing can change my love for you,even you.
Today's problem I spent too much wrong on the format,I should be more careful.
Windows Message Queue
Description:
Message queue is the basic fundamental of windows system. For each process, the system maintains a message queue. If something happens to this process, such as mouse click, text change, the system will add a message to the queue. Meanwhile, the process will do a loop for getting message from the queue according to the priority value if it is not empty. Note that the less priority value means the higher priority. In this problem, you are asked to simulate the message queue for putting messages to and getting message from the message queue.
Input
There's only one test case in the input. Each line is a command, "GET" or "PUT", which means getting message or putting message. If the command is "PUT", there're one string means the message name and two integer means the parameter and priority followed by. There will be at most 60000 command. Note that one message can appear twice or more and if two messages have the same priority, the one comes first will be processed first.(i.e., FIFO for the same priority.) Process to the end-of-file.
Output
For each "GET" command, output the command getting from the message queue with the name and parameter in one line. If there's no message in the queue, output "EMPTY QUEUE!". There's no output for "PUT" command.
Sample Input
GET
PUT msg1 10 5
PUT msg2 10 4
GET
GET
GET
Sample Output
EMPTY QUEUE!
msg2 10
msg1 10
EMPTY QUEUE!
Problem solving:
Through a special queue with a struct and Operator overloading.The main question is understand this,oh my poor English.
Code:
#include
using namespace std;
struct node
{
string s;
int p, q, id;
} n[6005];
bool operator <(const node &x, const node &y)//Operator overloading.
{
if (x.q == y.q)
return x.id > y.id;
return x.q > y.q;
}
priority_queue que;
int main()
{
string s;
int k = 0;
while (cin >> s)
{
if (s[0] == 'G')
{
if (que.empty())
puts("EMPTY QUEUE!");
else
{
cout << que.top().s << " " << que.top().p << endl;
que.pop();
}
}
if (s[0] == 'P')
{
cin >> n[0].s >> n[0].p >> n[0].q;
n[0].id = k;
k++;
que.push(n[0]);
}
}
}Train Problem I
Description:
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.".
Problem solving:
An easy problem.Use a stack to simulate this process and a queue to record 'in' or 'out'.Judge if we can pop or push.
Code:
#include
using namespace std;
int main()
{
int n;
while (~scanf("%d", &n))
{
int flag = 0;
string a, b;
cin >> a >> b;
stack s;
queue q;
for (int i = 0, j = 0; i < n && j <= n;)
{
if (s.empty() || s.top() != b[i])
{
if (j == n)
{
cout << "No.\nFINISH\n";
flag = 1;
break;
}
s.push(a[j]);
j++;
q.push("in");
}
else
{
s.pop();
q.push("out");
i++;
}
}
if (flag)
continue;
else
{
cout << "Yes.\n";
while (!q.empty())
{
cout << q.front() << endl;
q.pop();
}
}
cout << "FINISH\n";
}
}Rails
Description:
There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.
The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.
Input
The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0.
The last block consists of just one line containing 0.
Output
The output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last null' block of the input.
Sample Input
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0
Sample Output
Yes No Yes
Problem solving:
An easy stack question.
Code:
#include
#include
#include
#include
using namespace std;
int a[1005];
int main()
{
int n;
while (scanf("%d", &n) && n)
{
while (1)
{
int flag = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] == 0)
{
flag = 1; break;
}
}
if (flag)
break;
stack sta;
int pos = 0;
for (int i = 1; i <= n; i++)
{
sta.push(i);
while (!sta.empty() && sta.top() == a[pos])
{
sta.pop();
pos++;
}
}
if (sta.empty())
puts("Yes");
else
puts("No");
}
puts("");
}
}D - {A} + {B}
Description:
给你两个集合，要求{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
Problem solving:
An easy set question.
Code:
#include
using namespace std;
int main()
{
int n, m, a;
while (~scanf("%d %d", &n, &m))
{
set s;
for (int i = 0; i < n + m; i++)
{
cin >> a;
s.insert(a);
}
for (set::iterator it = s.begin(); it != s.end(); it++)
{
if (it == s.begin())
cout << *it;
else
cout << " " << *it;
}
cout << endl;
}
}水果
Description:
夏天来了好开心啊,呵呵,好多好多水果
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)
Problem solving:
An unusual problem.We can ues a map in map.And then the iterator is a little different now.Just see the Code.Luckily,map can automatic sorting makes this problem is not so hard.
Code:
#include
using namespace std;
int main()
{
int n, m, p;
string x, y;
cin >> n;
int xxxx=0;
while (n--)
{
if(xxxx!=0) puts("");
xxxx=1;
int i = 0;
map > ma;
cin >> m;
while (m--)
{
cin >> x >> y >> p;
ma[y][x] += p;
}
map::iterator iit;
for (map >::iterator it = ma.begin(); it != ma.end(); it++)
{
cout first << endl;
for (iit = it->second.begin(); iit != it->second.end(); iit++)
{
cout first second << ")" << endl;
}
}
}
}Let the Balloon Rise
Description:
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
Problem solving:
An easy map problem.
Code:
#include
using namespace std;
int main()
{
int n;
string s;
while (cin >> n)
{
map ma;
if (n == 0)
break;
while (n--)
{
cin >> s;
ma[s]++;
}
int mid = 0;
string ans;
for (map::iterator it = ma.begin(); it != ma.end(); it++)
{
if (it->second > mid)
{
ans = it->first;
mid = it->second;
}
}
cout << ans << endl;
}
}不重复数字
Description:
给出N个数，要求把其中重复的去掉，只保留第一次出现的数。
例如，给出的数为1 2 18 3 3 19 2 3 6 5 4，其中2和3有重复，去除后的结果为1 2 18 3 19 6 5 4。
Input
输入第一行为正整数T，表示有T组数据。
接下来每组数据包括两行，第一行为正整数N，表示有N个数。第二行为要去重的N个正整数。
Output
对于每组数据，输出一行，为去重后剩下的数字，数字之间用一个空格隔开。
Sample Input
2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6
Sample Output
1 2 18 3 19 6 5 4
1 2 3 4 5 6
Hint
对于30%的数据，1 <= N <= 100，给出的数不大于100，均为非负整数；
对于50%的数据，1 <= N <= 10000，给出的数不大于10000，均为非负整数；
对于100%的数据，1 <= N <= 50000，给出的数在32位有符号整数范围内。
提示:
由于数据量很大，使用C++的同学请使用scanf和printf来进行输入输出操作，以免浪费不必要的时间。
Problem solving:
We can't use set here because set will automatic sort.I wanted to ues a flag array to know the number has appread or not.But always RE.So I choose a set to know if the number has already appeared.
Code:
#include
using namespace std;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, a;
scanf("%d", &n);
set s;
int mid = s.size();
queue q;
while (n--)
{
scanf("%d", &a);
s.insert(a);
if (s.size() != mid)
{
q.push(a);
mid = s.size();
}
}
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
puts("");
}
}Andy's First Dictionary
Description:
Andy, 8, has a dream - he wants to produce his very own dictionary. This is not an easy task for him, as the number of words that he knows is, well, not quite enough. Instead of thinking up all the words himself, he has a briliant idea. From his bookshelf he would pick one of his favourite story books, from which he would copy out all the distinct words. By arranging the words in
alphabetical order, he is done! Of course, it is a really time-consuming job, and this is where a computer program is helpful.You are asked to write a program that lists all the different words in the input text. In this problem, a word is defined as a consecutive sequence of alphabets, in upper and/or lower case. Words with only one letter are also to be considered. Furthermore, your program must be CaSe InSeNsItIvE. For example, words like “Apple”, “apple” or “APPLE” must be considered the same.
Input
The input file is a text with no more than 5000 lines. An input line has at most 200 characters. Input
is terminated by EOF.
Output
Your output should give a list of different words that appears in the input text, one in a line. The
words should all be in lower case, sorted in alphabetical order. You can be sure that he number of
distinct words in the text does not exceed 5000.
Sample Input
Adventures in Disneyland
Two blondes were going to Disneyland when they came to a fork in the
road. The sign read: "Disneyland Left."
So they went home.
Sample Output
a
adventures
blondes
came
disneyland
fork
going
home
in
left
read
road
sign
so
the
they
to
two
went
were
when
Problem solving:
I know a new useful function through this problem--Stringstream.I will write a new artical about this these days.It's amazing,suitable for us who is lazy.About this problem,you just know what you should do:
1. Turn uppercase letter to lower case letters.
2. Delete the char which is not a letter.
Code:
#include
using namespace std;
int main()
{
string s;
set se;
while (cin >> s)
{
for (int i = 0; i < s.size(); i++)
{
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] += 32;
else if (s[i] >= 'a' && s[i] <= 'z')
s[i] = s[i];
else
s[i] = ' ';
}
string mi;
stringstream mid(s);
while (mid >> mi)
{
se.insert(mi);
}
}
for (set::iterator it = se.begin(); it != se.end(); it++)
{
cout << *it << endl;
}
}A and B and Compilation Errors
Description:
A and B are preparing themselves for programming contests.
B loves to debug his code. But before he runs the solution and starts debugging, he has to first compile the code.
Initially, the compiler displayed n compilation errors, each of them is represented as a positive integer. After some effort, B managed to fix some mistake and then another one mistake.
However, despite the fact that B is sure that he corrected the two errors, he can not understand exactly what compilation errors disappeared — the compiler of the language which B uses shows errors in the new order every time! B is sure that unlike many other programming languages, compilation errors for his programming language do not depend on each other, that is, if you correct one error, the set of other error does not change.
Can you help B find out exactly what two errors he corrected?
Input
The first line of the input contains integer n (3 ≤ n ≤ 105) — the initial number of compilation errors.
The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the errors the compiler displayed for the first time.
The third line contains n - 1 space-separated integers b1, b2, ..., bn - 1 — the errors displayed at the second compilation. It is guaranteed that the sequence in the third line contains all numbers of the second string except for exactly one.
The fourth line contains n - 2 space-separated integers с1, с2, ..., сn - 2 — the errors displayed at the third compilation. It is guaranteed that the sequence in the fourth line contains all numbers of the third line except for exactly one.
Output
Print two numbers on a single line: the numbers of the compilation errors that disappeared after B made the first and the second correction, respectively.
Examples
Input
5
1 5 8 123 7
123 7 5 1
5 1 7
Output
8
123
Input
6
1 4 3 3 5 7
3 7 5 4 3
4 3 7 5
Output
1
3
Note
In the first test sample B first corrects the error number 8, then the error number 123.
In the second test sample B first corrects the error number 1, then the error number 3. Note that if there are multiple errors with the same number, B can correct only one of them in one step.
Problem solving:
Through reding,you will kown the first line we output is the different number between the second line and the third line we input,and the second line we output is the different number between the third line and the fourth line we input.I choose a force way but easy to understand.
Code:
#include
using namespace std;
int main()
{
int n, a;
cin >> n;
map ma;
map ma1;
map ma2;
for (int i = 0; i < n; i++)
{
cin >> a;
ma[a]++;
}
for (int i = 0; i < n - 1; i++)
{
cin >> a;
ma1[a]++;
}
for (int i = 0; i < n - 2; i++)
{
cin >> a;
ma2[a]++;
}
int x = 0, y = 0;
for (map::iterator it = ma.begin(); it != ma.end(); it++)
{
int mid = it->first;
if (ma[mid] != ma1[mid])
cout << mid << endl;
}
for (map::iterator it = ma1.begin(); it != ma1.end(); it++)
{
int mid = it->first;
if (ma2[mid] != ma1[mid])
cout << mid << endl;
}
return 0;
}
排列2
Description:
Ray又对数字的列产生了兴趣：
现有四张卡片，用这四张卡片能排列出很多不同的4位数，要求按从小到大的顺序输出这些4位数。
Input
每组数据占一行，代表四张卡片上的数字（0<=数字<=9），如果四张卡片都是0，则输入结束。
Output
对每组卡片按从小到大的顺序输出所有能由这四张卡片组成的4位数，千位数字相同的在同一行，同一行中每个四位数间用空格分隔。
每组输出数据间空一行，最后一组数据后面没有空行。
Sample Input
1 2 3 4
1 1 2 3
0 1 2 3
0 0 0 0
Sample Output
1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 1123 1132 1213 1231 1312 1321 2113 2131 2311 3112 3121 3211 1023 1032 1203 1230 1302 1320 2013 2031 2103 2130 2301 2310 3012 3021 3102 3120 3201 3210
Problem solving:
An easy problem through 'next_permutation()'.The most disgusting place is the format.
Code:
#include
using namespace std;
int a[5];
int main()
{
int mid, x = 0;
while (scanf("%d %d %d %d", &a[0], &a[1], &a[2], &a[3]) != EOF)
{
sort(a, a + 4);
if (a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0)
break;
if (x)
cout << endl;
x = 1;
int flag = 1;
do
{
if (a[0] == 0)
continue;
if (flag)
{
cout << a[0] << a[1] << a[2] << a[3];
flag = 0;
}
else if (mid == a[0])
cout << " " << a[0] << a[1] << a[2] << a[3];
else
{
cout << endl;
cout << a[0] << a[1] << a[2] << a[3];
}
mid = a[0];
} while (next_permutation(a, a + 4));
puts("");
}
}I have too much PE before I passed this problem.
Ignatius and the Princess II
Description:
Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, "I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too." Ignatius says confidently, "OK, at last, I will save the Princess."
"Now I will show you the first problem." feng5166 says, "Given a sequence of number 1 to N, we define that 1,2,3...N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it's easy to see the second smallest sequence is 1,2,3...N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It's easy, isn't is? Hahahahaha......"
Can you help Ignatius to solve this problem?
Input
The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub's demand. The input is terminated by the end of file.
Output
For each test case, you only have to output the sequence satisfied the BEelzebub's demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.
Sample Input
6 4
11 8
Sample Output
1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10
Problem solving:
An easy problem through 'next_permutation()'.
Code:
#include
using namespace std;
int a[1005];
int main()
{
int n, m;
while (~scanf("%d %d", &n, &m))
{
for (int i = 1; i <= n; i++)
{
a[i] = i;
}
int flag = 0;
do
{
flag++;
if (flag == m)
break;
} while (next_permutation(a + 1, a + n + 1));
for (int i = 1; i < n; i++)
cout << a[i] << " ";
cout << a[n] << endl;
}
}
交通银行工作强度 39人发布