ACM: STL标准库容器的应用（vector、queue、list、map）
有碰到STL类型的题，就看了下关于STL的视频，粗略学习了下C++以及STL的用法...
以前从没用过C++也没看过和C++相关的知识，所以很多地方还是保持的C代码的风格..很多时候scanf和printf都改不过来...
但是用STL真的好方便啊...而且完全不会出错..用过以后再也不想写C了...
顺便再推荐一个网站http://www.cplusplus.com/reference/
查询各种函数超级超级方便。
四道原题，分别是vector、queue、list、map的应用。
https://vjudge.net/contest/208769#problem/B
第一题用的vector。
https://vjudge.net/contest/208769#problem/E
第二题用的vector和queue，本来想用list，后来感觉用queue更方便...
https://vjudge.net/contest/208769#problem/I
第三题用的list，但是我觉得更好的方法不是用STL做...
https://vjudge.net/contest/208769#problem/G
第四题用的map，完全不用处理...只需要输入、构造好、再输出就行了...
- 第一题
The Blocks Problem
Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks.
In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a speci ed state, you will “program” a robotic arm to respond to a limited set of commands.
The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks that lie on a at table. Initially there are n blocks on the table (numbered from 0 to n − 1) with block bi adjacent to block bi+1 for all 0 ≤ i < n − 1 as shown in the diagram below:
Initial Blocks World
The valid commands for the robot arm that manipulates blocks are:
• move a onto b
where a and b are block numbers, puts block a onto block b after returning any blocks that are
stacked on top of blocks a and b to their initial positions.
• move a over b
where a and b are block numbers, puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.
• pile a onto b
where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.
• pile a over b
where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.
• quit
terminates manipulations in the block world.
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no a ect on the con guration of blocks.
Input
The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25.
The number of blocks is followed by a sequence of block commands, one command per line. Your program should process all commands until the quit command is encountered.
You may assume that all commands will be of the form speci ed above. There will be no syntactically incorrect commands.
Output
The output should consist of the nal state of the blocks world. Each original block position numbered i (0 ≤ i < n where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don’t put any trailing spaces on a line.
There should be one line of output for each block position (i.e., n lines of output where n is the integer on the rst line of input).
Sample Input
10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
Sample Output
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:
题目超级超级超级难读懂...看了好几遍没看懂就有道翻译了...有道看了几遍还是看不懂就百度了...主要读懂四个模拟操作就行。
- move onto 将a、b上的积木还原、a放到b上
- move over 将a上的积木还原，a放到b顶端
- pile onto 将b上积木还原，a及a上积木放到b上
- pile over a及a上积木放到b顶端
简单讲下思路，主要是用数组，数组里面是vector（可动态增长）；
主要函数有：
1.查看行和高度；
2.将某个块.求出高度后,上面的数还原；
3.移动：移动的函数可以只有一个，若a移动到b，发现，可以统一概括为移动b的顶部；
然后其他的思路什么的就很简单了...不说了不说了..
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
vector<int> pile[25];
void search(int &row, int &height, int a) // 查看第几行和高度
{
for (int i = 0; i < 25; i++) {
for (int j = 0; j < pile[i].size(); j++) {
if (pile[i][j] == a) {
row = i;
height = j;
return;
}
}
}
}
void reset(int a, int row, int height) // 还原某一个块上的积木
{
for (unsigned long i = pile[row].size() - 1; i > height; i--) {
int k = pile[row][i];
pile[row].pop_back();
pile[k].push_back(k);
}
}
void block_move(int row1, int row2, int height_a) //移动a到b上，或b顶端
{
for (int i = height_a; i < pile[row1].size(); i++) {
pile[row2].push_back(pile[row1][i]);
}
pile[row1].resize( height_a );
}
int main(int argc, const char * argv[]) {
int n;
scanf("%d",&n);
for ( int i = 0; i < n; i++) {
pile[i].push_back(i);
}
vector<int> ::iterator it;
string command1;
string command2;
while (cin >> command1 && command1 != "quit" ) {
int a;
cin >> a;
cin >> command2;
int b;
cin >> b;
int row1 = 0, row2 = 0, height1 = 0, height2 = 0;
search(row1, height1, a);
search(row2, height2, b);
if (row1 == row2) {
continue;
}
if ( command1 == "move" ) {
if ( command2 == "onto" ) {
// move onto
// 将a、b上的积木还原、a放到b上
reset(a, row1, height1);
reset(b, row2, height2);
}
else {
// move over
// 将a上的积木还原，a放到b顶端
reset(a, row1, height1);
}
}
else {
if ( command2 == "onto" ) {
// pile onto
// 将b上积木还原，a及a上积木放到b上
reset(b, row2, height2);
}
// pile over
// a及a上积木放到b顶端
}
block_move(row1, row2, height1);
}
// 啊下面的忽略。。改不掉C
for (int i = 0; i < n; i++) {
printf("%d:",i);
for (int j = 0; j < pile[i].size(); j++) {
printf(" %d",pile[i][j]);
}
printf("\n");
}
return 0;
}
- 第二题
Team Queue
Queues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa is a team queue, for example.
In a team queue each element belongs to a team. If an element enters the queue, it rst searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue.
Your task is to write a program that simulates such a team queue.
Input
The input le will contain one or more test cases. Each test case begins with the number of teams t (1 ≤ t ≤ 1000). Then t team descriptions follow, each one consisting of the number of elements belonging to the team and the elements themselves. Elements are integers in the range 0..999999. A team may consist of up to 1000 elements.
Finally, a list of commands follows. There are three di erent kinds of commands: • ENQUEUE x — enter element x into the team queue
• DEQUEUE — process the rst element and remove it from the queue • STOP — end of test case
The input will be terminated by a value of 0 for t.
Warning: A test case may contain up to 200000 (two hundred thousand) commands, so the imple- mentation of the team queue should be e cient: both enqueing and dequeuing of an element should only take constant time.
Output
For each test case, rst print a line saying ‘Scenario #k’, where k is the number of the test case. Then, for each ‘DEQUEUE’ command, print the element which is dequeued on a single line. Print a blank line after each test case, even after the last one.
Sample Input
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0
Sample Output
Scenario #1
101
102
103
201 202 203
Scenario #2
259001
259002
259003
259004
259005
260001
这题英文还算好懂..啊现在每次读ACM的题..简直难度max的阅读理解...
大概意思就是，先输入几个team，告诉你每个team的成员有谁，再输入一个入队顺序，根据前面的队员关系，判断新入队的排哪去。只要有一个队员在前面，这个队伍的其他成员就可以无限插队。
所以先将每个队的队员记录下来（1.内容是vector的数组），再将每个队员（2.内容是queue的数组）的顺序记录下来，在将每个队伍的顺序记录下来（3.vector）。第一组记录完不用动，只需要不断地查找即可，第二组不断地改变，因为需要入队出队，用queue最合适（但是想了下list应该也可以），因为只要有队员在最开头，这组成员可以一直插队，但是当这组成员没有在开头了，那就不能插队，用第三组的vector来记录这一队有没有人在开头。
啊啊啊啊讲不清....总之不需要建立一个很长很长的队列，来看入队出队的顺序，要移动的太多了，单独每组team一个queue就可以了。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
void find_row(vector<int> relat[], int num, int t, int &row) // 查找在哪个队
{
for (int i = 0; i < t; i++) {
for (int j = 0; j < relat[i].size(); j++) {
if (relat[i][j] == num) {
row = i;
return;
}
}
}
}
int judge(vector<int> order, int n) // 判断
{
for (int i = 0; i < order.size(); i++) {
if (order[i] == n) {
return 1;
}
}
return 0;
}
int main()
{
int t = 0;
int Scenario = 0;
while (~scanf("%d", &t) && t != 0) {
vector<int> relat[1000]; // 存储关系
queue<int> Queue[1000]; // 存储入队出队顺序
vector<int> order; // 存储组别是否出队完
int d = 0;
for (int i = 0; i < t; i++) {
cin >> d;
for (int j = 0; j < d; j++) {
int num;
cin >> num;
relat[i].push_back(num);
}
}
string command;
cin >> command;
printf("Scenario #%d\n",++Scenario);
while ( command[0] != 'S' ) {
if (command[0] == 'E') {
// 入队
int num;
cin >> num;
int row = 0;
find_row(relat, num, t, row);
Queue[row].push(num);
if (judge(order, row) == 0) {
order.push_back(row);
}
}
else {
// 出队
int row1 = order[0];
printf("%d\n",Queue[row1].front());
Queue[row1].pop();
if (Queue[row1].size() == 0) {
order.erase(order.begin());
}
}
cin >> command;
}
printf("\n");
}
return 0;
}
- 第三题
士兵队列训练问题
某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。
Input
本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。
Output
共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。
Sample Input
2
20
40
Sample Output
1 7 19
1 19 37
这道题....坑...一开始没理解题的意思，一直以为是小于等于3个人就停止，但是实际上就算小于3个人了这一轮报数也要继续下去。
如果用STL做的话，最好的方法应该是双向链表list（啊不包括map啊什么的...那些我还没看过..）。对链表的访问必须要用迭代器。但是删除元素的时候要注意迭代器会指向被删除元素的下一个元素（一开始不知道，总是运行运行就访问越界了）。
还有list的迭代器是双向迭代器，不是随机访问迭代器，很多操作不能做，比如说给迭代器直接+n或迭代器之间比较大小，所以有些地方的判定要注意。迭代器的每次后移，都要判定到end了没。
话说end()函数，是返回一个指向头结点的迭代器（也就是最后一个结点，list是循环迭代器），所以可以用来判定。
第一次的时候超时间了，因为每次判定人数都是直接用size函数，但是size需要循环，时间复杂度为O(n)，直接自己用一个计数器就不会超时了。
#include <iostream>
#include <list>
using namespace std;
int main()
{
int N;
while (~scanf("%d", &N)) {
while (N--) {
list<int> soldier;
int num;
cin >> num;
for (int i = 0; i < num; i++) {
soldier.push_back(i+1);
}
list<int>::iterator it;
while (num > 3) {
it = soldier.begin();
while ( it != soldier.end() ) {
it++;
if ( it == soldier.end() ) {
break;
}
list<int>::iterator it2;
it2 = it;
it2++;
if (it2 == soldier.end()) {
it = soldier.erase(it);
num--;
break;
} // 话说这里...好像删除最后一个结点的时候..不知道迭代器发生了什么...指不到end去了...？？？
it = soldier.erase(it);
num--;
}
it = soldier.begin();
if (num <= 3) {
break;
}
while (it != soldier.end() ) {
it++;
if ( it == soldier.end()) {
break;
}
it++;
if ( it == soldier.end()) {
break;
}
list<int>::iterator it2;
it2 = it;
it2++;
if (it2 == soldier.end()) {
it = soldier.erase(it);
num--;
break;
}
it = soldier.erase(it);
num--;
}
}
it = soldier.begin();
cout << *it;
it++;
for ( ; it != soldier.end(); it++) {
cout << ' ' << *it ;
}
cout << endl;
}
}
return 0;
}
- 第四题
水果
夏天来了~~好开心啊,呵呵,好多好多水果
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算是很合适了吧...
先说下map，也是容器的一种.....
好了..本来这里写了一大段，传上去以后发现，消失了！！！消失了！！难受...已经不想写了..图再发一遍吧..
就简单讲下吧..这是个map < string, int > 容器的图，但是这道题有两个关键字，第一关键字为地区，第二关键字为水果名，所以需要两个map容器。如下图：
类似于二维数组的构造（数组里面有数组），这是个map当中有map的构造，看图应该就能看懂了。一开始我一直在想，如果两个水果地区都是guangdong，那不是关键字重复了么，还查了好久关键字重复怎么办...后来画了个图就懂了，如果都是广东，在左边一列算是一个关键字，然后在右边再细分。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
int N;
string fruit, place;
int num;
scanf("%d", &N);
while (N--) {
map<string, map<string, int>> myfruit;
int M;
cin >> M;
for ( int i = 0; i < M; i++) {
cin >> fruit >> place >> num;
myfruit[place][fruit] += num;
}
map<string, map<string, int>>::iterator it;
map<string, int> :: iterator it2;
for (it = myfruit.begin(); it != myfruit.end(); it++) {
cout << it->first << endl;
for ( it2 = it->second.begin(); it2 != it->second.end(); it2++) {
cout << " |----" << it2->first << '(' << it2->second << ')' << endl;
}
}
if (N > 0)
cout << endl;
}
return 0;
}
