PAT 甲级 - 模板库 | 栖迟於一丘

C++ 中为使用者提供了标准的模板库也叫 STL，其中封装了大部分刷题所要用到的容器，而我在之前写过一篇《C++ STL》，所以这里就是单纯的记录一些类型题的解题思路，并不重复赘述具体的使用和含义
话说 C++ 中的容器在易用性和速度上做出的平衡要比其他语言强的不是一星半点，之前看过侯捷老师的手撕 STL 源码，后来转 Java 没能坚持看完，但仍感觉受益匪浅（虽说时间一长忘干净了），不知道什么原因 B 站上找不到了

vector

1039

题目：Course List for Student

Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤40, 000), the number of students who look for their course lists, and K (≤2, 500), the total number of courses. Then the student name lists are given for the courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students Ni (≤200) are given in a line. Then in the next line, Ni student names are given. A student name consists of 3 capital English letters plus a one-digit number. Finally the last line contains the N names of students who come for a query. All the names and numbers in a line are separated by a space.

Output Specification:

For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student’s name, then the total number of registered courses of that student, and finally the indices of the courses in increasing order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.

Sample Input:

11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9

Sample Output:

ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0

思路： 使用 map 搭配 vector 动态数组进行课程编号和姓名的映射存放，因数据规模过大，不要使用 cin 和 cout，姓名使用 char 数组存储，避免使用字符串，查询输出时，进行编号的排序

代码：

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std; 

int main()
{

    int n, k;
    scanf("%d %d", &n, &k);
    map<string, vector<int>> list;// 建立集合，用姓名映射课程的方式 
    char name[5];// 直接输入字符串会超时，使用字符数组的方式 
    for (int i = 0; i < k; i++)
    {
        int id, cnt;
        scanf("%d %d", &id, &cnt);
        for (int j = 0; j < cnt; j++)
        {
            scanf("%s", name);
            list[name].push_back(id);// 根据姓名将课程 ID 放入 
        }
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%s", name);
        vector<int> v = list[name];// 查询时放入临时数组 
        printf("%s %d", name, v.size());
        sort(v.begin(), v.end());// 排序后输出 
        for (int j = 0; j < v.size(); j++)
        {
            printf(" %d", v[j]);
        }
        printf("\n");
    }
    system("pause");
    return 0;

}

1047

题目：Student List for Course

Zhejiang University has 40,000 students and provides 2,500 courses. Now given the registered course list of each student, you are supposed to output the student name lists of all the courses.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤40,000), the total number of students, and K (≤2,500), the total number of courses. Then N lines follow, each contains a student’s name (3 capital English letters plus a one-digit number), a positive number C (≤20) which is the number of courses that this student has registered, and then followed by C course numbers. For the sake of simplicity, the courses are numbered from 1 to K.

Output Specification:

For each test case, print the student name lists of all the courses in increasing order of the course numbers. For each course, first print in one line the course number and the number of registered students, separated by a space. Then output the students’ names in alphabetical order. Each name occupies a line.

Sample Input:

10 5
ZOE1 2 4 5
ANN0 3 5 2 1
BOB5 5 3 4 2 1 5
JOE4 1 2
JAY9 4 1 2 5 4
FRA8 3 4 2 5
DON2 2 4 5
AMY7 1 5
KAT3 3 5 4 2
LOR6 4 2 4 1 5

Sample Output:

1 4
ANN0
BOB5
JAY9
LOR6
2 7
ANN0
BOB5
FRA8
JAY9
JOE4
KAT3
LOR6
3 1
BOB5
4 7
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1
5 9
AMY7
ANN0
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1

思路： 使用 map 映射 vector 字符串数组即可

代码：

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

/*
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    map<int, vector<string>> list;
    char name[5];
    for (int i = 0; i < n; i++)
    {
        int k;
        scanf("%s %d", name, &k);
        for (int j = 0; j < k; j++)
        {
            int temp;
            scanf("%d", &temp);
            list[temp].push_back(name);
        }
    }

    for (int i=1;i<=m;i++)
    {
        vector<string> str = list[i];
        printf("%d %d\n", i, str.size());
        sort(str.begin(), str.end());
        for (int j = 0; j < str.size(); j++)
        {
            printf("%s\n",str[j].c_str());
        }
    }
    system("pause");
    return 0;
}
*/

int n, k, c, idx;
vector<vector<string>> course;

int main()
{
    scanf("%d%d", &n, &k);
    course.resize(k + 1);
    for (int i = 0; i < n; ++i)
    {
        string name;
        cin >> name >> c;
        for (int j = 0; j < c; ++j)
        {
            scanf("%d", &idx);
            course[idx].push_back(name);
        }
    }
    for (int i = 1; i <= k; ++i)
    {
        printf("%d %d\n", i, course[i].size());
        sort(course[i].begin(), course[i].end());
        for (int j = 0; j < course[i].size(); ++j)
            printf("%s\n", course[i][j].c_str());
    }
    return 0;
}

set

1063

题目：Set Similarity

Given two sets of integers, the similarity of the sets is defined to be Nc/Nt×100%, where Nc is the number of distinct common numbers shared by the two sets, and Nt is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.

Input Specification:

Each input file contains one test case. Each case first gives a positive integer N (≤50) which is the total number of sets. Then N lines follow, each gives a set with a positive $M (≤10^4)$ and followed by M integers in the range [0, 109]. After the input of sets, a positive integer K (≤2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.

Output Specification:

For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.

Sample Input:

3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

Sample Output:

50.0%
33.3%

思路： 相似性的计算就是在集合 B 中出现过的集合 A 的元素除以所有不重复的元素和；注意：集合变量的名称不能时模板类的名称

代码：

#include <iostream>
#include <set>
using namespace std; 

int n, m; 
set<int> st[51]; 

void compare(int a, int b) // 将比较方法独立出来 
{

    int samenum = 0, totalnum = st[b].size();
    for (auto it = st[a].begin(); it != st[a].end(); it++)
    {
        if (st[b].find(*it) != st[b].end())
        {
            samenum++;
        }
        else
        {
            totalnum++;
        }
    }
    printf("%.1f%\n", samenum * 100.00 / totalnum); // 输出保留一位小数 

}

int main()
{

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int size, temp;
        cin >> size;
        for (int j = 0; j < size; j++)
        {
            cin >> temp;
            st[i].insert(temp); // 存储到 set 数组中 
        }
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        compare(a, b); // 通过查找编号调用方法 
    }
    return 0;

}

string

1060

题目：Are They Equal

If a machine can save only 3 significant digits, the float numbers 12300 and 12358.9 are considered equal since they are both saved as 0.123×105 with simple chopping. Now given the number of significant digits on a machine and two float numbers, you are supposed to tell if they are treated equal in that machine.

Input Specification:

Each input file contains one test case which gives three numbers N, A and B, where N (<100) is the number of significant digits, and A and B are the two float numbers to be compared. Each float number is non-negative, no greater than 10100, and that its total digit number is less than 100.

Output Specification:

For each test case, print in a line YES if the two numbers are treated equal, and then the number in the standard form 0.d[1]...d[N]*10^k (d[1]>0 unless the number is 0); or NO if they are not treated equal, and then the two numbers in their standard form. All the terms must be separated by a space, with no extra space at the end of a line.

Note: Simple chopping is assumed without rounding.

Sample Input 1:

3 12300 12358.9

Sample Output 1:

YES 0.123*10^5

Sample Input 2:

3 120 128

Sample Output 2:

NO 0.12010^3 0.12810^3

思路： 只需判断保存有效数字的字符串和指数位数是否相同即可保证一对数字的相同，根据不同情况的处理封装在方法中

指数在 main 方法中定义，使用 int& e 的方式处理同一变量，否则无法返回两个变量
在方法中首先去掉前导零，去掉后有三种情况，首字符为小数点为小数，否则为正数，若字符串长度为 0，为 0
当为小数时，去掉小数点，小数点后面 0 的个数即为指数 e 的值
为正数时，向后寻找小数点或末尾，非 0 或末尾，指数 e++
最后根据输入 N 的值每次放入一个有效字符，不足补 0，返回判断即可

代码：

#include <iostream>
#include <string>
using namespace std;

int n;
string deal(string str, int &e) // 字符串处理方法，指数 e 为恒定地址变量 
{
    int k = 0;
    while (str.length() > 0 && str[0] == '0') // 将前导 0 去除 
    {
        str.erase(str.begin());
    }
    if (str[0] == '.') // 去掉 0 为小数点说明为小数 
    {
        str.erase(str.begin());
        while (str.length() > 0 && str[0] == '0') // 通过小数点后边 0 的个数获得指数的负数值 
        {
            str.erase(str.begin());
            e--;
        }
    }
    else // 不是小数点即为整数 
    {
        while (k < str.length() && str[k] != '.') // 小数点之前的位数为指数值 
        {
            k++;
            e++;
        }
        if (k < str.length()) // 最后 k 的值小于字符串长度说明有小数点，将其去掉 
        {
            str.erase(str.begin() + k);
        }
    }
    if (str.length() == 0) // 如果去掉 0，字符串长度为 0，说明指数也为 0
    {
        e = 0;
    }
    int num = 0;
    k = 0;
    string dealed;
    while (num < n) // 保存 n 个有效数字 
    {
        if (k < str.length())
        {
            dealed += str[k++];
        }
        else
        {
            dealed += '0';
        }
        num++;
    }
    return dealed;
}

int main()
{
    string s1, s2, s3, s4;
    cin >> n >> s1 >> s2;
    int e1 = 0, e2 = 0;
    s3 = deal(s1, e1);
    s4 = deal(s2, e2);
    if (s3 == s4 && e1 == e2) // 通过有效数字和指数判断科学计数法是否相同 
    {
        cout << "YES 0." << s3 << "*10^" << e1;
    }
    else
    {
        cout << "NO 0." << s3 << "*10^" << e1 << " 0." << s4 << "*10^" << e2;
    }
    system("pause");
    return 0;
}

map

1100

题目：Mars Numbers

People on Mars count their numbers with base 13:

Zero on Earth is called “tret” on Mars.
The numbers 1 to 12 on Earth is called “jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec” on Mars, respectively.
For the next higher digit, Mars people name the 12 numbers as “tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou”, respectively.

For examples, the number 29 on Earth is called “hel mar” on Mars; and “elo nov” on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.

Output Specification:

For each number, print in a line the corresponding number in the other language.

Sample Input:

4
29
5
elo nov
tam

Sample Output:

hel mar
may
115
13

思路： 因为数据不会超过 169，直接采用打表的方式将每个数字与其“火星文”形式对应起来

字符串数组对应数字转“火星文”，map<string, int> 对应“火星文”转数字
打表将个位和整十位分为一种情况，其他分为一种情况，进行运算赋值即可

代码：

#include <iostream>
#include <map>
#include <cstring>
using namespace std; 

string unitDigit[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"}; 
string tenDigit[13] = {"tret", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"}; 
// 将个位十位保存 
string numToStr[170]; // 通过数字作为下标输出字符串 
map<string, int> strToNum; // 通过字符串映射到数字 
void init()
{

    for (int i = 0; i < 13; i++)
    {
        numToStr[i] = unitDigit[i];
        strToNum[unitDigit[i]] = i; // 存储个位的互相对应 
        numToStr[i * 13] = tenDigit[i];
        strToNum[tenDigit[i]] = i * 13; // 存储整十位的互相对应 
    }
    for (int i = 1; i < 13; i++)
    { // 每位的对应 
        for (int j = 1; j < 13; j++)
        {
            string str = tenDigit[i] + " " + unitDigit[j];
            numToStr[i * 13 + j] = str;
            strToNum[str] = i * 13 + j;
        }
    }

}
int main()
{

    init(); // 调用打表 
    int n;
    cin >> n;
    string query;
    getchar();
    for (int i = 0; i < n; i++)
    {
        getline(cin, query);
        if (query[0] >= '0' && query[0] <= '9')
        {
            int num = stoi(query); // 将属于数字的转换为 int 型 
            cout << numToStr[num] << endl;
        }
        else
        {
            cout << strToNum[query] << endl;
        }
    }
    return 0;

}

1054

题目：The Dominant Color

Behind the scenes in the computer’s memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color. A strictly dominant color takes more than half of the total area. Now given an image of resolution M by N (for example, 800×600), you are supposed to point out the strictly dominant color.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (≤800) and N (≤600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range [0,224). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.

Output Specification:

For each test case, simply print the dominant color in a line.

Sample Input:

5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24

Sample Output:

24

思路： map<int,int> 集合映射颜色与出现次数，当次数超过 $M*N/2$ 时输出

代码：

#include <iostream>
#include <map>
using namespace std;

int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    map<int, int> arr;
    int half = m * n / 2;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int temp;
            scanf("%d", &temp);
            arr[temp]++;
            if (arr[temp] > half)
            {
                printf("%d", temp);
                return 0;
            }
        }
    }
    return 0;
}

1071

题目：Speech Patterns

People often have a preference among synonyms of the same word. For example, some may prefer “the police”, while others may prefer “the cops”. Analyzing such patterns can help to narrow down a speaker’s identity, which is useful when validating, for example, whether it’s still the same person behind an online avatar.

Now given a paragraph of text sampled from someone’s speech, can you find the person’s most commonly used word?

Input Specification:

Each input file contains one test case. For each case, there is one line of text no more than 1048576 characters in length, terminated by a carriage return \n . The input contains at least one alphanumerical character, i.e., one character from the set [0-9 A-Z a-z ].

Output Specification:

For each test case, print in one line the most commonly occurring word in the input text, followed by a space and the number of times it has occurred in the input. If there are more than one such words, print the lexicographically smallest one. The word should be printed in all lower case. Here a “word” is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.

Note that words are case insensitive.

Sample Input:

Can1: “Can a can can a can? It can!”

Sample Output:

can 5

思路： 判断是否属于有效字符，遇到非法字符便截取之前有效的字符放到 map 集合中，注意：最后一位时，即便属于非法字符也要放入

代码：

#include <iostream>
#include <map>
#include <cctype>
using namespace std; 

int main()
{

    string str, temp;
    map<string, int> mcount;
    getline(cin, str);
    for (int i = 0; i < str.length(); i++)
    {
        if (isalnum(str[i])) // 属于数字和字母 
        {
            if (isupper(str[i]))
            { // 大写转换为小写 
                str[i] = tolower(str[i]);
            }
            temp += str[i];
        }
        if (!isalnum(str[i]) || i == str.length() - 1) // 非法字符或最后一位 
        {
            if (temp.length() != 0)
            {
                mcount[temp]++; // 不为空便自增 
            }
            temp.clear();
        }
    }
    int max = 0;
    string ans;
    for (auto it = mcount.begin(); it != mcount.end(); it++)
    {
        if (it->second > max)
        {
            max = it->second;
            ans = it->first; // 遍历求次数最大，记录输出 
        }
    }
    cout << ans << " " << max << endl;
    return 0;

}

1022

题目：Digital Library

A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID’s.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤104) which is the total number of books. Then N blocks follow, each contains the information of a book in 6 lines:

Line #1: the 7-digit ID number;
Line #2: the book title – a string of no more than 80 characters;
Line #3: the author – a string of no more than 80 characters;
Line #4: the key words – each word is a string of no more than 10 characters without any white space, and the keywords are separated by exactly one space;
Line #5: the publisher – a string of no more than 80 characters;
Line #6: the published year – a 4-digit number which is in the range [1000, 3000].

It is assumed that each book belongs to one author only, and contains no more than 5 key words; there are no more than 1000 distinct key words in total; and there are no more than 1000 distinct publishers.

After the book information, there is a line containing a positive integer M (≤1000) which is the number of user’s search queries. Then M lines follow, each in one of the formats shown below:

1: a book title
2: name of an author
3: a key word
4: name of a publisher
5: a 4-digit number representing the year

Output Specification:

For each query, first print the original query in a line, then output the resulting book ID’s in increasing order, each occupying a line. If no book is found, print Not Found instead.

Sample Input:

3
1111111
The Testing Book
Yue Chen
test code debug sort keywords
ZUCS Print
2011
3333333
Another Testing Book
Yue Chen
test code sort keywords
ZUCS Print2
2012
2222222
The Testing Book
CYLL
keywords debug book
ZUCS Print2
2011
6
1: The Testing Book
2: Yue Chen
3: keywords
4: ZUCS Print
5: 2011
3: blablabla

Sample Output:

1: The Testing Book
1111111
2222222
2: Yue Chen
1111111
3333333
3: keywords
1111111
2222222
3333333
4: ZUCS Print
1111111
5: 2011
1111111
2222222
3: blablabla
Not Found

思路：

对除了 id 之外的其他信息都建立一个 map<string, set>，把相应的 id 插入对应搜索词的 map 的集合里面，形成一个信息对应一个集合，集合里面是复合条件的书的 id
因为对于输入的关键词（可以重复，算是书本对应的 tag 标签）没有给定关键词的个数，可以使用 while(cin >> s) 并且判断 c = getchar()，c 是否等于、n，如果是再退出循环
建立 query，通过传参的形式可以将不同的 map 名称统一化，先要判断 map.find() 和 m.end() 是否相等，如果不等再去遍历整个 map，输出所有满足条件的 id，如果相等就说明不存在这个搜索词对应的 id，那么就要输出 Not Found
传参一定要用引用，否则最后一组数据可能会超时

代码：

#include <iostream>
#include <map>
#include <set>
using namespace std;

map<string, set<int>> title, author, key, pub, year; // 每类信息建立一个 map 集合映射 ID

void query(map<string, set<int>> &m, string &str) // 查询方法使用引用的形式，防止大数据超市 
{
    if (m.find(str) != m.end())
    {
        for (auto it = m[str].begin(); it != m[str].end(); it++)
            printf("%07d\n", *it);
    }
    else
        cout << "Not Found\n";
}

int main()
{
    int n, m, id, num;
    scanf("%d", &n);
    string ttitle, tauthor, tkey, tpub, tyear;
    for (int i = 0; i < n; i++)
    {
        scanf("%d\n", &id);
        getline(cin, ttitle);
        title[ttitle].insert(id);
        getline(cin, tauthor);
        author[tauthor].insert(id);
        while (cin >> tkey) // 关键字使用分隔输入的形式 
        {
            key[tkey].insert(id);
            char c = getchar();
            if (c == '\n')
                break;
        }
        getline(cin, tpub);
        pub[tpub].insert(id);
        getline(cin, tyear);
        year[tyear].insert(id);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d: ", &num);
        string temp;
        getline(cin, temp);
        cout << num << ": " << temp << "\n";
        if (num == 1) // 根据查询类型判断方法引用的集合 
            query(title, temp);
        else if (num == 2)
            query(author, temp);
        else if (num == 3)
            query(key, temp);
        else if (num == 4)
            query(pub, temp);
        else if (num == 5)
            query(year, temp);
    }
    return 0;
}

stack

1051

题目：Pop Sequence

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
YES
NO

思路： 使用 stack 模板模拟入栈，每放入一个元素后判断其与输出序列要输出的元素是否相同，相同后出栈，位数后移；
有两种情况表示出栈顺序不对：1、当前入栈的元素超过栈的容量；2、模拟完成后栈不为空

代码：

#include <iostream>
#include <vector>
#include <stack>
using namespace std; 

stack<int> st; 
int main()
{

    int m, n, k, arr[1001]; // 保存序列 
    cin >> m >> n >> k;
    while (k--)
    {
        while (!st.empty()) // 将栈清空 
        {
            st.pop();
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> arr[i]; // 保存序列 
        }
        int current = 1;
        bool flag = true;
        for (int i = 1; i <= n; i++)
        {
            st.push(i);
            if (st.size() > m) // 当前个数超过容量 
            {
                flag = false;
                break;
            }
            while (!st.empty() && st.top() == arr[current]) // 每放入一个元素判断出栈 
            {
                st.pop();
                current++;
            }
        }
        if (st.empty() && flag) // 模拟完成后栈空和容量未超表示正确 
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;

}

queue

1056

题目：Mice and Rice

Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.

First the playing order is randomly decided for NP programmers. Then every NG programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every NG winners are then grouped in the next match until a final winner is determined.

For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: NP and NG (≤1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than NG mice at the end of the player’s list, then all the mice left will be put into the last group. The second line contains NP distinct non-negative numbers Wi (i=0,⋯,NP−1) where each Wi is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,⋯,NP−1 (assume that the programmers are numbered from 0 to NP−1). All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:

11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3

Sample Output:

5 5 5 2 5 5 5 3 1 3 5

思路： 根据输入重量时的顺序作为编号，保存到结构体的 weight 中，并将排列规则放入队列中，分组进行比较之后将每组的获胜者放入队列最后，判断一个便出队一个，当进行一轮的比较之后，队列后的就是下一轮的排列顺序，继续分组重复操作；每轮中个人的排名就是当前轮的组数 +1，进入下一轮的人员继续更新排名直到只剩一人时退出循环

代码：

#include <iostream>
#include <queue>
using namespace std;

struct Mouse // 建立老鼠结构体 
{
    int weight, rank;
};

int main()
{
    Mouse mouse[1001];
    int Np, Ng;
    cin >> Np >> Ng;
    for (int i = 0; i < Np; i++) // 按输入顺序为其编号 
    {
        cin >> mouse[i].weight;
    }
    queue<int> qu;
    int order;
    for (int i = 0; i < Np; i++)
    {
        cin >> order;
        qu.push(order); // 将排列顺序放入队列中 
    }
    int temp = Np, group;  //temp 表示此轮的人员，group 表示分成几组 
    while (qu.size() != 1) // 角逐到只剩一个 
    {
        if (temp % Ng == 0)
        {
            group = temp / Ng;
        }
        else
        {
            group = temp / Ng + 1;
        }
        for (int i = 0; i < group; i++)
        {
            int k = qu.front(); //k 表示小组的胜出者 
            for (int j = 0; j < Ng; j++)
            {
                if (i * Ng + j >= temp) // 存在最后一组数量不够的情况 
                {
                    break;
                }
                int front = qu.front();
                if (mouse[front].weight > mouse[k].weight)
                {
                    k = front;
                }
                mouse[front].rank = group + 1; // 每次都更新排名 
                qu.pop();
            }
            qu.push(k); // 每组最大的放到队列中进入下一轮 
        }
        temp = group; // 新一轮的成员数就是上一轮的组数 
    }
    mouse[qu.front()].rank = 1;
    for (int i = 0; i < Np; i++)
    {
        cout << mouse[i].rank;
        if (i < Np - 1)
        {
            cout << " ";
        }
    }
    system("pause");
    return 0;
}

linklist

1074

题目：Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

思路： 建立链表的节点结构体，根据 next 的数据为其排序规则从小到大赋值，根据规则排序，就可以模拟链表的连接；处理完链表后根据分组的单组容量构建输出规则进行输出

**tips：** 整数型不管前导零有多少，始终存储有效数组，如：输入 00100，存储为 100

代码：

#include <iostream>
#include <algorithm>
using namespace std; 

const int edge = 100010; 
struct Node // 定义链表的结点结构体 
{

    int address, data, next;
    int order; // 定义位置，后续排序 

}; 

bool cmp(Node a, Node b) // 排序规则 
{

    return a.order < b.order;

}

int main()
{

    Node node[edge];
    for (int i = 0; i < edge; i++)
    {
        node[i].order = edge; // 将所有的规则定义为一个较大值 
    }

    int begin, n, k;
    cin >> begin >> n >> k;
    int address;
    for (int i = 0; i < n; i++) // 读入数据 
    {
        cin >> address;
        cin >> node[address].data >> node[address].next;
        node[address].address = address;
    }
    int count = 0;
    while (begin != -1)
    {
        node[begin].order = count++; // 将规则的先后顺序定义 
        begin = node[begin].next;
    }
    sort(node, node + edge, cmp);       // 排序连接起来 
    for (int i = 0; i < count / k; i++) // 分块进行输出 
    {
        for (int j = (i + 1) * k - 1; j > i * k; j--)
        {
            printf("%05d %d %05d\n", node[j].address, node[j].data, node[j - 1].address);
        }
        // 每一组的最后一个数据进行判断输出 
        printf("%05d %d ", node[i * k].address, node[i * k].data); // 输出数据 
        if (i < count / k - 1)                                     // 如果不是最后一组 
        {
            printf("%05d\n", node[(i + 2) * k - 1].address); // 输出越组后的最后一个（倒序的第一个）
        }
        else
        {
            if (count % k == 0) // 如果能整分组，输出 -1
            {
                printf("-1\n");
            }
            else // 不能整分 
            {
                printf("%05d\n", node[(i + 1) * k].address); // 不能分组的第一个的地址 
                for (int l = count / k * k; l < count; l++)  // 将其照常输出即可 
                {
                    printf("%05d %d ", node[l].address, node[l].data);
                    if (l < count - 1)
                    {
                        printf("%05d\n", node[l + 1].address);
                    }
                    else
                    {
                        printf("-1\n");
                    }
                }
            }
        }
    }
    system("pause");
    return 0;

}

1032

** 题目：Sharing **

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.

You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).

Input Specification:

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive $N (≤10^5)$ , where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next

whereAddress is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.

Output Specification:

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.

Sample Input 1:

11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010

Sample Output 1:

67890

思路： 建立一个范围足够的静态链表，遍历第一条链表，将出现过的节点标记，在遍历第二条时出现标记过的节点则输出下标

代码：

#include <iostream>
using namespace std;

const int edge = 100001;
struct Node // 定义结构体 
{
    char data;
    int next;
    bool flag; // 对第一条链表的出现的节点赋予正值 
};

int main()
{
    Node node[edge];
    for (int i = 0; i < edge; i++)
    {
        node[i].flag = false; // 将每一个节点初始设置为未出现 
    }
    int begin1, begin2, total;
    cin >> begin1 >> begin2 >> total;
    int address, next;
    char data;
    for (int i = 0; i < total; i++)
    {
        cin >> address >> data >> next;
        node[address].data = data;
        node[address].next = next;
    }
    while (begin1 != -1) // 遍历第一条，对每一个节点做标记 
    {
        node[begin1].flag = true;
        begin1 = node[begin1].next;
    }
    while (begin2 != -1)
    {
        if (node[begin2].flag)
        {
            break; // 在第二条中出现被标记的节点跳出 
        }
        begin2 = node[begin2].next;
    }
    if (begin2 != -1)
    {
        printf("%05d", begin2);
    }
    else
    {
        printf("-1");
    }
    return 0;
}

1052

题目：Linked List Sorting

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive N (<105) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Key Next

where Address is the address of the node in memory, Key is an integer in [−105, 105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.

Sample Input:

5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345

Sample Output:

5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1

思路： 题目要求只输出能够连接的节点，所以对节点结构体定义同一个标记变量，将有效的节点根据 data 的大小进行升序排序

代码：

#include <iostream>
#include <algorithm>
using namespace std; 

const int edge = 100001; 
struct Node
{

    int address, data, next;
    bool flag; // 存在无法连接的节点，创建标记属性 

}; 
bool cmp(Node a, Node b) // 根据数据大小进行排序 
{

    if (a.flag == false || b.flag == false) // 只要 a 或 b 有一个不符合条件，就将其放置到最后 
    {
        return a.flag > b.flag;
    }
    else
    {
        return a.data < b.data; // 其他根据数据大小进行排序 
    }

}

int main()
{

    Node node[edge];
    for (int i = 0; i < edge; i++)
    {
        node[i].flag = false; // 先将所有节点的标记置为 false
    }
    int N, begin;
    cin >> N >> begin;
    int address;
    for (int i = 0; i < N; i++)
    {
        cin >> address;
        cin >> node[address].data >> node[address].next;
        node[address].address = address;
    }
    int count = 0;
    while (begin != -1)
    {
        node[begin].flag = true; // 将能够连接的节点标记为 true
        count++;                 // 记录有效节点的个数 
        begin = node[begin].next;
    }
    if (count == 0) // 没有有效节点直接进行输出 
    {
        cout << "0 -1";
    }
    else
    {
        sort(node, node + edge, cmp);                // 进行排序 
        printf("%d %05d\n", count, node[0].address); // 输出有效节点的个数和起始位置 
        for (int i = 0; i < count; i++)
        {
            if (i < count - 1)
            {
                printf("%05d %d %05d\n", node[i].address, node[i].data, node[i + 1].address);
            }
            else
            {
                printf("%05d %d -1\n", node[i].address, node[i].data);
            }
        }
    }
    return 0;

}

1097

题目：Deduplication on a Linked List

Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N (≤105) which is the total number of nodes. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Key Next

where Address is the position of the node, Key is an integer of which absolute value is no more than 104, and Next is the position of the next node.

Output Specification:

For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

Sample Output:

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

思路： 将数据绝对值相同的节点按照输入顺序放置到最后分别控制有效位和无效位单独输出，排序的标记变量初始置为数据规模的两倍放置中间存放无效位时溢出，输出时注意两类的最后一个节点的 next 为 -1

代码：

#include <cstdio>
#include <stdlib.h>
#include <algorithm>
using namespace std;

const int maxn = 100000;
struct NODE
{
    int address, key, next, num = 2 * maxn; //num 让其数时数据规模的两倍，中间留出充足的空间进行分类放置 
} node[maxn];
bool exist[maxn] = {false};
int cmp(NODE a, NODE b)
{
    return a.num < b.num;
}
int main()
{
    int begin, n, cnt1 = 0, cnt2 = 0, a; //cnt1 表示有效的，cnt2 表示被删除的 
    scanf("%d%d", &begin, &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a);
        scanf("%d%d", &node[a].key, &node[a].next);
        node[a].address = a;
    }
    for (int i = begin; i != -1; i = node[i].next) // 遍历 
    {
        if (exist[abs(node[i].key)] == false) // 如果这个数的绝对值没有出现过 
        {
            exist[abs(node[i].key)] = true; // 表示出现 
            node[i].num = cnt1++;           // 为其赋予第几个有效位 
        }
        else
        {
            node[i].num = maxn + cnt2++; // 为其赋予第几个无效位 
        }
    }
    sort(node, node + maxn, cmp);
    int cnt = cnt1 + cnt2;
    for (int i = 0; i < cnt; i++)
    {
        if (i != cnt1 - 1 && i != cnt - 1) // 不是两类的最后一个节点 
        {
            printf("%05d %d %05d\n", node[i].address, node[i].key, node[i + 1].address);
        }
        else
        {
            printf("%05d %d -1\n", node[i].address, node[i].key);
        }
    }
    return 0;
}