柳婼の blog – 我不管，反正我最萌～

PAT | 蓝桥 | LeetCode学习路径 & 刷题经验

你们要不要考虑也节省一下时间～

这份PDF题目叫做《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验 by 柳婼》，希望可以帮助学习算法路上的小可爱们节约时间、少踩一些坑、多走一些捷径～

一年前看过我blog的人应该知道，我曾经开通过知乎的值乎付费咨询，大概开通了大半年时间，期间也收到了很多咨询，绝大多数提问的话题都是“PAT、蓝桥、LeetCode怎么学如何刷题”，我也一一认真做了回答（绝大多数回答都在半小时以上），但是值乎的回答只能够发布语音，而且有回答时效，提问也有字数限制，后来问的人越来越多，我一天要花数小时在知乎回答上，而且回答的都是几乎相同的问题…对于分享算法经验来说，短短半小时确实不够，很多观点无法详细解释缘由，值乎一对一咨询确实不是一个很好的分享算法经验的平台，听者也很难短时间形成对问题答案的清晰理解，所以后来半年前我就关闭了知乎咨询的功能～不过还是有很多小可爱通过各种渠道向我咨询经验等问题，所以我花了好多天时间将这些问题的回答、刷题笔记、经验全都整理在了一份PDF中～这些问题包括：

里面不仅有关于这些竞赛的介绍、应该看哪些书、如何刷题，还有我自己刷算法过程中整理的笔记，目录如下：

这份经验一共3万7千字（想当年800字的高考作文都写那么辛苦…）在算法路上，我能帮的只有这么多了…希望能帮助你们少走很多弯路，少踩很多坑～剩下的就是靠你们自己刷题啦～还和离线版订阅获取的方式一样…打赏29元并备注邮箱号即可…打赏二维码在最下面…24小时内发送到邮箱…（一般一两个小时就收到了～）时间仓促，后期还会对这份文档的内容进行扩充完善…到时候有版本更新还会继续发送到邮箱中～感谢支持与信任～

1179 Chemical Equation – PAT甲级真题

A chemical equation is the symbolic representation of a chemical reaction in the form of symbols and formulae, wherein the reactant entities are given on the left-hand side and the product entities on the right-hand side. For example, CH4+2O2=CO2+2H2O means that the reactants in this chemical reaction are methane and oxygen: CH4 and O2, and the products of this reaction are carbon dioxide and water: CO2 and H2O.

Given a set of reactants and products, you are supposed to tell that in which way we can obtain these products, provided that each reactant can be used only once. For the sake of simplicity, we will consider all the entities on the right-hand side of the equation as one single product.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤20), followed by N distinct indices of reactants. The second line gives an integer M (1≤M≤10), followed by M distinct indices of products. The index of an entity is a 2-digit number.

Then a positive integer K (≤50) is given, followed by K lines of equations, in the format:

reactant_1 + reactant_2 + … + reactant_n -> product

where all the reactants are distinct and are in increasing order of their indices.

Note: It is guaranteed that

one set of reactants will not produce two or more different products, i.e. situation like 01 + 02 -> 03 and 01 + 02 -> 04 is impossible;
a reactant cannot be its product unless it is the only one on the left-hand side, i.e. 01 -> 01 is always true (no matter the equation is given or not), but 01 + 02 -> 01 is impossible; and
there are never more than 5 different ways of obtaining a product given in the equations list.

Output Specification:

For each case, print the equations that use the given reactants to obtain all the given products. Note that each reactant can be used only once.

Each equation occupies a line, in the same format as we see in the inputs. The equations must be print in the same order as the products given in the input. For each product in order, if the solution is not unique, always print the one with the smallest sequence of reactants — A sequence { a1,⋯,am } is said to be smaller than another sequence { b1,⋯,bn } if there exists 1≤i≤min(m,n) so that aj=bj for all j<i, and ai<bi.

It is guaranteed that at least one solution exists.

Sample Input:

8 09 05 03 04 02 01 16 10
3 08 03 04
6
03 + 09 -> 08
02 + 08 -> 04
02 + 04 -> 03
01 + 05 -> 03
01 + 09 + 16 -> 03
02 + 03 + 05 -> 08

Sample Output:

02 + 03 + 05 -> 08
01 + 09 + 16 -> 03
04 -> 04

题目大意：给定一组反应物和产物，你需要告诉我们如何获得这些产物，假设每种反应物只能使用一次。为了简单起见，我们将方程式右侧的所有实体视为一个单一的产物。打印使用给定的反应物来获得所有给定的产物的方程式。注意，每个反应物只能使用一次。

分析：used用来标记每个反应物是否可用，ans[i]表示第i个产物需要用到它的第i条合成公式（排序后），pro中存储产物的编号，equa中存储每个产物的所有合成公式。
如果某个产物自己本身就是反应物，这一条合成公式需要加到配方里。在匹配方案之前，先把每个配方按照题目要求从小到大排序。
本文搜索采用的序列是按照产物编号进行顺序搜索，确保每一个产物都在满足要求的情况下才继续下一次的搜索。
搜索过程中，尝试某产物的所有合成公式，如果当前公式中所有反应物都还可用，则进入下一层搜索（注意回来时要把这些反应物还给我们）。当达到M层时，表示已经完全匹配，并且是按照题目要求的最优序，输出每一条合成配方即可。

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
int N, M, K, num, used[101], ans[101];
vector<int> pro, temp;
vector<vector<int>> equa[101];
string s;
bool cmp(const vector<int> &a, const vector<int> &b) {
    for (int i = 0; ; i++) 
        if (a[i] != b[i]) return a[i] < b[i];
}
void dfs(int x) {
    if (x == M) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < equa[pro[i]][ans[i]].size(); j++) {
                if (j != 0) cout << " + ";
                cout << setw(2) << setfill('0') << equa[pro[i]][ans[i]][j];
            }
            cout << " -> " << setw(2) << setfill('0') << pro[i] << "\n";
        }
        exit(0);
    }
    for (int i = 0; i < equa[pro[x]].size(); i++) {
        int flag = 1;
        vector<int> A = equa[pro[x]][i];
        for (auto it : A) 
            if (used[it] != 1) {
                flag = 0;
                break;
            }
        if (flag == 0) continue;
        for (auto it : A) used[it] = 2;
        ans[x] = i;
        dfs(x + 1);
        for (auto it : A) used[it] = 1;
    }
}
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> num;
        used[num] = 1;
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> num;
        if(used[num] == 1) equa[num].push_back({num});
        pro.push_back(num);
    }
    cin >> K;
    for (int i = 0; i < K; i++) {
        temp.clear();
        while (cin >> num >> s) {
            temp.push_back(num);
            if (s == "->") {
                cin >> num;
                equa[num].push_back(temp);
                break;
            }
        }
    }
    for (int i = 0; i < M; i++) sort(equa[pro[i]].begin(), equa[pro[i]].end(), cmp);
    dfs(0);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <iomanip>

#include <vector>

using namespace std;

int N, M, K, num, used[101], ans[101];

vector<int> pro, temp;

vector<vector<int>> equa[101];

string s;

bool cmp(const vector<int> &a, const vector<int> &b) {

for (int i = 0; ; i++)

if (a[i] != b[i]) return a[i] < b[i];

}

void dfs(int x) {

if (x == M) {

for (int i = 0; i < M; i++) {

for (int j = 0; j < equa[pro[i]][ans[i]].size(); j++) {

if (j != 0) cout << " + ";

cout << setw(2) << setfill('0') << equa[pro[i]][ans[i]][j];

}

cout << " -> " << setw(2) << setfill('0') << pro[i] << "\n";

}

exit(0);

}

for (int i = 0; i < equa[pro[x]].size(); i++) {

int flag = 1;

vector<int> A = equa[pro[x]][i];

for (auto it : A)

if (used[it] != 1) {

flag = 0;

break;

}

if (flag == 0) continue;

for (auto it : A) used[it] = 2;

ans[x] = i;

dfs(x + 1);

for (auto it : A) used[it] = 1;

}

int main() {

cin >> N;

for (int i = 0; i < N; i++) {

cin >> num;

used[num] = 1;

}

cin >> M;

for (int i = 0; i < M; i++) {

cin >> num;

if(used[num] == 1) equa[num].push_back({num});

pro.push_back(num);

}

cin >> K;

for (int i = 0; i < K; i++) {

temp.clear();

while (cin >> num >> s) {

temp.push_back(num);

if (s == "->") {

cin >> num;

equa[num].push_back(temp);

break;

}

for (int i = 0; i < M; i++) sort(equa[pro[i]].begin(), equa[pro[i]].end(), cmp);

dfs(0);

return 0;

}

1178 File Path – PAT甲级真题

The figure shows the tree view of directories in Windows File Explorer. When a file is selected, there is a file path shown in the above navigation bar. Now given a tree view of directories, your job is to print the file path for any selected file.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10^3), which is the total number of directories and files. Then N lines follow, each gives the unique 4-digit ID of a file or a directory, starting from the unique root ID 0000. The format is that the files of depth d will have their IDs indented by d spaces. It is guaranteed that there is no conflict in this tree structure.

Then a positive integer K (≤100) is given, followed by K queries of IDs.

Output Specification:

For each queried ID, print in a line the corresponding path from the root to the file in the format: 0000->ID1->ID2->...->ID. If the ID is not in the tree, print Error: ID is not found. instead.

Sample Input:

14
0000
1234
2234
3234
4234
4235
2333
5234
6234
7234
9999
0001
8234
0002
4 9999 8234 0002 6666

Sample Output:

0000->1234->2234->6234->7234->9999
0000->1234->0001->8234
0000->0002
Error: 6666 is not found.

题目大意：该图显示了Windows文件资源管理器中目录的树状视图。当选择文件时，上方导航栏会显示文件路径。现在给定一个目录的树状视图，任务是打印任何选定文件的文件路径。第一行给出一个正整数N，表示目录和文件的总数。然后是N行，每行给出一个文件或目录的唯一的4位数ID，从唯一的根ID 0000 开始。格式是深度为d的文件将其ID缩进d个空格。然后给出一个正整数K，随后是K个查询的ID。对于每个查询的ID，在一行中按格式打印从根到文件的相应路径：0000->ID1->ID2->…->ID。如果ID不在树中，则打印错误：ID is not found.

分析：superior记录每一个编号的上级编号，last记录每层文件的上级文件夹，root记录根文件夹，ans中存储最后输出的文件访问路径。用map记录信息，注意带空格的整行字符串的输入需要用到getline，并且在普通cin输入和整行getline输入的时候会需要一个getchar帮忙一下。
每次输入一个文件目录，先找到它有几个(I个)空格，然后记录一下它的上级信息，并且把它作为最新的下一层的文件夹的上级目录。最后输入查找的目标，不在map里就表示没有，有的话就整理成题目所需输出的顺序输出即可～

#include <iostream>
#include <string>
#include <map>
using namespace std;
int N, K;
string s, root, ans;
map<string, string> superior;
map<int, string> last;
int main() {
    cin >> N >> root;
    last[1] = root;
    superior[root] = root;
    getchar();
    for (int i = 1, I; i < N; i++) {
        getline(cin, s);
        I = 0;
        while (s[I] == ' ') ++I;
        superior[s.substr(I)] = last[I];
        last[I + 1] = s.substr(I);
    }
    cin >> K;
    while (K--) {
        cin >> s;
        if (!superior.count(s)) cout << "Error: " << s << " is not found.\n";
        else {
            ans = "\n";
            while (s != root) {
                ans = "->" + s + ans;
                s = superior[s];
            }
            cout << root << ans;
        }
    }
    return 0;
}

#include <iostream>

#include <string>

#include <map>

using namespace std;

int N, K;

string s, root, ans;

map<string, string> superior;

map<int, string> last;

int main() {

cin >> N >> root;

last[1] = root;

superior[root] = root;

getchar();

for (int i = 1, I; i < N; i++) {

getline(cin, s);

I = 0;

while (s[I] == ' ') ++I;

superior[s.substr(I)] = last[I];

last[I + 1] = s.substr(I);

}

cin >> K;

while (K--) {

cin >> s;

if (!superior.count(s)) cout << "Error: " << s << " is not found.\n";

else {

ans = "\n";

while (s != root) {

ans = "->" + s + ans;

s = superior[s];

}

cout << root << ans;

}

return 0;

}

1177 Subsequence in Substring – PAT甲级真题

A substring is a continuous part of a string. A subsequence is the part of a string that might be continuous or not but the order of the elements is maintained. For example, given the string atpaaabpabtt, pabt is a substring, while pat is a subsequence.

Now given a string S and a subsequence P, you are supposed to find the shortest substring of S that contains P. If such a solution is not unique, output the left most one.

Input Specification:

Each input file contains one test case which consists of two lines. The first line contains S and the second line P. S is non-empty and consists of no more than 104 lower English letters. P is guaranteed to be a non-empty subsequence of S.

Output Specification:

For each case, print the shortest substring of S that contains P. If such a solution is not unique, output the left most one.

Sample Input:

atpaaabpabttpcat
pat

Sample Output:

pabt

题目大意：子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串atpaaabpabtt，pabt是一个子串，而pat就是一个子列。现给定一个字符串S和一个子列P，本题就请你找到S中包含P的最短子串。若解不唯一，则输出起点最靠左边的解。

分析：使用point表示当前待匹配的P串中下标，MIN表示目前获得的最短的答案长度（其实应该是j-i+1，但是只需要大小比较的话统一减1也不影响，可以少一次+1的计算）。ansl和ansr分别表示最终答案的最左和最右端点。
遍历整个S字符串，当前字符为P的首字符的时候，开始第二重循环，查看以当前位置作为起点是否存在一个子串满足条件。如果j-i等于MIN了，可以直接跳出循环，因为我就算当前情况满足题意，也不如用之前的那个子串（因为之前的那个子串起点更靠左）。如果point已经到了P的长度，表示所有内容匹配成功，并且当前最优，将现在的i和j更新成为新的答案～

#include <iostream>
using namespace std;
int main() {
    int point, MIN = 10000, ansl = 0, ansr = 0;
    string S, P;
    cin >> S >> P;
    for (int i = 0; i <= S.size() - P.size(); i++) {
        if (S[i] == P[0]) {
            point = 1;
            for (int j = i + 1; j < S.size(); j++) {
                if (j - i== MIN) break;
                if (S[j] == P[point]) point++;
                if (point == P.size()) {
                    ansl = i, ansr = j;
                    MIN = j - i ;
                    break;
                }
            }
        }
    }
    for (int i = ansl; i <= ansr; i++) cout << S[i];
    return 0; 
}

#include <iostream>

using namespace std;

int main() {

int point, MIN = 10000, ansl = 0, ansr = 0;

string S, P;

cin >> S >> P;

for (int i = 0; i <= S.size() - P.size(); i++) {

if (S[i] == P[0]) {

point = 1;

for (int j = i + 1; j < S.size(); j++) {

if (j - i== MIN) break;

if (S[j] == P[point]) point++;

if (point == P.size()) {

ansl = i, ansr = j;

MIN = j - i ;

break;

}

for (int i = ansl; i <= ansr; i++) cout << S[i];

return 0;

}

1176 The Closest Fibonacci Number – PAT甲级真题

The Fibonacci sequence Fn is defined by Fn+2=Fn+1+Fn for n≥0, with F0=0 and F1=1. The closest Fibonacci number is defined as the Fibonacci number with the smallest absolute difference with the given integer N.

Your job is to find the closest Fibonacci number for any given N.

Input Specification:

Each input file contains one test case, which gives a positive integer N (≤10^8).

Output Specification:

For each case, print the closest Fibonacci number. If the solution is not unique, output the smallest one.

Sample Input:

305

Sample Output:

233

Hint:

Since part of the sequence is { 0, 1, 1, 2, 3, 5, 8, 12, 21, 34, 55, 89, 144, 233, 377, 610, … }, there are two solutions: 233 and 377, both have the smallest distance 72 to 305. The smaller one must be printed out.

题目大意：为任意给定的整数N找出与之最近的斐波那契数。如果解不唯一，输出最小的那个数

分析：使用Fn、Fn_1、Fn_2分别表示当前的斐波那契数以及前两项。当Fn与N的绝对值大于等于Fn_1到N的绝对值时，就输出Fn_1的值并结束程序。数是越来越大的，再往后的数字与N的绝对值会越来越大

#include <iostream>
using namespace std;
int main() {
    int N, Fn, Fn_1 = 1, Fn_2 = 1;
    cin >> N;
    for (int i = 2; ; i++) {
        Fn = Fn_1 + Fn_2;
        if (abs(Fn - N) >= abs(Fn_1 - N)) {
            cout << Fn_1;
            return 0;
        }
        Fn_2 = Fn_1;
        Fn_1 = Fn;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int N, Fn, Fn_1 = 1, Fn_2 = 1;

cin >> N;

for (int i = 2; ; i++) {

Fn = Fn_1 + Fn_2;

if (abs(Fn - N) >= abs(Fn_1 - N)) {

cout << Fn_1;

return 0;

}

Fn_2 = Fn_1;

Fn_1 = Fn;

}

return 0;

}

1125 子串与子列 – PAT乙级真题

子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt是一个子串，而 pat 就是一个子列。

现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。

输入格式：

输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的一个非空子列。

输出格式：

在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。

输入样例：

atpaaabpabttpcat
pat

输出样例：

pabt

分析：使用point表示当前待匹配的P串中下标，MIN表示目前获得的最短的答案长度（其实应该是j-i+1，但是只需要大小比较的话统一减1也不影响，可以少一次+1的计算）。ansl和ansr分别表示最终答案的最左和最右端点。
遍历整个S字符串，当前字符为P的首字符的时候，开始第二重循环，查看以当前位置作为起点是否存在一个子串满足条件。如果j-i等于MIN了，可以直接跳出循环，因为我就算当前情况满足题意，也不如用之前的那个子串（因为之前的那个子串起点更靠左）。如果point已经到了P的长度，表示所有内容匹配成功，并且当前最优，将现在的i和j更新成为新的答案～

#include <iostream>
using namespace std;
int main() {
    int point, MIN = 10000, ansl = 0, ansr = 0;
    string S, P;
    cin >> S >> P;
    for (int i = 0; i <= S.size() - P.size(); i++) {
        if (S[i] == P[0]) {
            point = 1;
            for (int j = i + 1; j < S.size(); j++) {
                if (j - i== MIN) break;
                if (S[j] == P[point]) point++;
                if (point == P.size()) {
                    ansl = i, ansr = j;
                    MIN = j - i ;
                    break;
                }
            }
        }
    }
    for (int i = ansl; i <= ansr; i++) cout << S[i];
    return 0; 
}

#include <iostream>

using namespace std;

int main() {

int point, MIN = 10000, ansl = 0, ansr = 0;

string S, P;

cin >> S >> P;

for (int i = 0; i <= S.size() - P.size(); i++) {

if (S[i] == P[0]) {

point = 1;

for (int j = i + 1; j < S.size(); j++) {

if (j - i== MIN) break;

if (S[j] == P[point]) point++;

if (point == P.size()) {

ansl = i, ansr = j;

MIN = j - i ;

break;

}

for (int i = ansl; i <= ansr; i++) cout << S[i];

return 0;

}

1124 最近的斐波那契数 – PAT乙级真题

斐波那契数列 Fn 的定义为：对 n≥0 有 Fn+2=Fn+1+Fn，初始值为 F0=0 和 F1=1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。

本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。

输入格式：

输入在一行中给出一个正整数 N（≤10^8）。

输出格式：

在一行输出与 N 最近的斐波那契数。如果解不唯一，输出最小的那个数。

输入样例：

305

输出样例：

233

样例解释

部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 12, 21, 34, 55, 89, 144, 233, 377, 610, … }。可见 233 和 377 到 305 的距离都是最小值 72，则应输出较小的那个解。

#include <iostream>
using namespace std;
int main() {
    int N, Fn, Fn_1 = 1, Fn_2 = 1;
    cin >> N;
    for (int i = 2; ; i++) {
        Fn = Fn_1 + Fn_2;
        if (abs(Fn - N) >= abs(Fn_1 - N)) {
            cout << Fn_1;
            return 0;
        }
        Fn_2 = Fn_1;
        Fn_1 = Fn;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int N, Fn, Fn_1 = 1, Fn_2 = 1;

cin >> N;

for (int i = 2; ; i++) {

Fn = Fn_1 + Fn_2;

if (abs(Fn - N) >= abs(Fn_1 - N)) {

cout << Fn_1;

return 0;

}

Fn_2 = Fn_1;

Fn_1 = Fn;

}

return 0;

}