题目及满分代码下载戳这里
A The Closest Fibonacci Number
热身题，预先把所有斐波那契数求出来。
#include<iostream>#include<vector>using namespace std;vector<int> nums;void get() {int tmp;for (int i = 2;; i++) {tmp = nums[i - 2] + nums[i - 1];if (tmp > 1e9)break;nums.push_back(tmp);}}int main() {int n;nums.push_back(0);nums.push_back(1);get();cin >> n;int i = 0;//直到大于等于该数字while (nums[i] < n)i++;if (nums[i] == n)cout << n;else {if (n - nums[i - 1] <= nums[i] - n)cout << nums[i - 1];elsecout << nums[i];}return 0;}
B Subsequence in Substring
字符串题，这题暴力竟然也过了（认为要dp）。
#include<iostream>#include<string>using namespace std;int main() {int len = 100000;string s, sub, ans;cin >> s >> sub;//枚举左端点for (int i = 0; i + sub.length() <= s.length(); i++) {int pos = 0, j = i;for (; j < s.length() && pos < sub.length(); j++) {if (s[j] == sub[pos])++pos;}//确定右端点if (pos == sub.length()) {if (j - i < len) {len = j - i;ans = s.substr(i, j - i);}}}cout << ans;return 0;}
C File Path
非 常规题，需要记录pre前驱指针，如果该文件和前一个文件平级，那么该文件的pre就是前一个文件的pre，如果该文件比前一个文件还深，则该文件pre就是前一个文件，如果该文件比前一个文件浅，则根据空格数迭代pre，找到规律后AC。
#include<cstdio>#include<string>#include<iostream>using namespace std;const int MAXN = 10010;int pre[MAXN];int n, m;void dfs(int tt) {if (pre[tt] != -2)dfs(pre[tt]);if (tt == 0)printf("0000");elseprintf("->%04d", tt);}int main() {string s;int tt;scanf("%d", &n);getchar();for (int i = 0; i < MAXN; i++)pre[i] = -1;//pre为-1代表没有这个文件，-2代表是根节点pre[0] = -2;int post = 0, bef = 0;for (int i = 0; i < n; i++) {getline(cin, s);int cur = stoi(s);if (i == 0)continue;//记录空格数int j = 0;while (s[j] == ' ')++j;//多一个空格，是上一个文件的子文件if (j == post + 1)pre[cur] = bef;else {int tmp = bef;//根据空格数迭代prefor (int k = 0; k <= post - j; k++)tmp = pre[tmp];pre[cur] = tmp;}bef = cur;post = j;}scanf("%d", &m);while (m--) {scanf("%d", &tt);if (pre[tt] == -1)printf("Error: %d is not found.", tt);elsedfs(tt);if (m)cout << endl;}return 0;}
D Chemical Equation
复杂的一道题，DFS回溯+映射，G[n]存储每个产物可选的方案，需要记录方案的字符串便于输出并且记录方案用到的原料，其中需要映射。满分代码如下：（应该有简单解法，不然给的三个提示也不会没用到）。
#include<iostream>#include<cstdio>#include<vector>#include<string>#include<algorithm>using namespace std;const int MAXN = 110;//是否使用过了bool vis[MAXN], ori[MAXN];vector<int> G[MAXN];//每个方案int pos;vector<int> fangan[MAXN];int n, m, k;//产物 原料int pro[MAXN];string fs[MAXN];//按照顺序排序bool cmp(int a, int b) {for (int i = 0;; i++)if (fangan[a][i] != fangan[b][i])return fangan[a] < fangan[b];}bool dfs(int lev, vector<string> &path) {if (lev == m) {for (int i = 0; i < path.size(); i++) {if (i)cout << endl;cout << path[i];}return true;}for (int i = 0; i < G[pro[lev]].size(); i++) {bool op = true;for (int j = 0; j < fangan[G[pro[lev]][i]].size(); j++)if (vis[fangan[G[pro[lev]][i]][j]]) {op = false;break;}//方案不合法if (!op)continue;for (int j = 0; j < fangan[G[pro[lev]][i]].size(); j++)vis[fangan[G[pro[lev]][i]][j]] = true;//回溯path.push_back(fs[G[pro[lev]][i]]);if (dfs(lev + 1, path))return true;for (int j = 0; j < fangan[G[pro[lev]][i]].size(); j++)vis[fangan[G[pro[lev]][i]][j]] = false;path.pop_back();}return false;}int main() {string s;int a;cin >> n;for (int i = 0; i < n; i++) {cin >> a;ori[a] = true;}cin >> m;for (int i = 0; i < m; i++) {cin >> pro[i];//自身可以成为方案if (ori[pro[i]]) {string ss;if (pro[i] < 10)ss = "0" + to_string(pro[i]) + " -> " + "0" + to_string(pro[i]);elsess = to_string(pro[i]) + " -> " + to_string(pro[i]);fs[pos] = ss;G[pro[i]].push_back(pos);fangan[pos++] = vector<int>({pro[i]});}}cin >> k;getchar();while (k--) {vector<int> tmp;getline(cin, s);for (int i = 0; i < s.length(); i = i + 5) {//空格代表这是化学式右边的产物，自己看看规律if (s[i] == ' ') {//产物a = stoi(s.substr(i + 1, 2));//映射字符串fs[pos] = s;G[a].push_back(pos);//映射数字fangan[pos++] = tmp;break;}int cur = stoi(s.substr(i, 2));//原料没有这个元素if (!ori[cur])break;tmp.push_back(cur);}}//根据要求的顺序排序for (int i = 0; i < m; i++)sort(G[pro[i]].begin(), G[pro[i]].end(), cmp);vector<string> path;//dfs求解dfs(0, path);return 0;}
PS.冬季果然简单一点，满分好开心，冲冲冲。
如果觉得《PAT甲级冬季满分题解》对你有帮助，请点赞、收藏，并留下你的观点哦！
