团体程序设计天梯赛练习集PAT-L3题解与程序（1~18题）2018年的天梯赛，鄙⼈很不幸成为了我们队的拖油瓶（⼿动笑哭
2018年的真题（19~21题）以后会更新……吧……
天梯赛的⼀点个⼈经（jiao）验（xun）：
该⽐赛没有罚时，⽽且测试点分值的分布极其诡异（经常是第⼀个⼩数据就⼗多分），所以尽最⼤可能骗分！
今年L3的三道题，3-1是⼀道极其恶⼼的模拟（⼿动AStyle），我x他xx的xxx这xx是什么xx玩意⼉……
3-2和3-3都可以直接写暴⼒骗分。3-2我写了个O(n^4)的模拟骗了22分，3-3本可以骗些分的，结果我沙茶了没写……
前⾯的部分1-1和2-4都挺坑的。2-4要考虑-0的情形，恶⼼程度瞬间提升了⼏个档次（
个⼈感觉这套题的特点：思路不算很难，但是有些细节繁杂得要死。尤其是某些图论题（感觉基本上都是最短路）的输⼊和输出，不多说了⾃⾏体会。
考察的知识点不算多，不过⽐较考验实现能⼒，所以拿来练练⼿还是不错的。
贴⼀下本⽂部分代码⽤的板⼦。像#define pb(v, x) v.push_back(x)这样激进的缩写法我是完全习惯不了（⼿动笑哭）
1 #include <cctype>
2 #include <cmath>
3 #include <cstdio>
4 #include <cstdlib>
5 #include <cstring>
6
7 #include <forward_list>
8 #include <list>
9 #include <map>
10 #include <queue>
11 #include <set>
12 #include <stack>
13 #include <unordered_map>
14 #include <unordered_set>
15 #include <vector>
16
17 #include <algorithm>
18 #include <functional>
19 #include <iostream>
20 #include <iterator>
21 #include <numeric>
22 #include <stdexcept>
23 #include <string>
24 #include <tuple>
25 #include <utility>
26
27#define FILL(arr, ch) memset(arr, ch, sizeof(arr))
28
29using namespace std;
2013款奥德赛30
31using LL = long long;
32 template <class Tp>
33using MinHeap = priority_queue<Tp, vector<Tp>, greater<Tp>>;
34 template <class Tp>
35using MaxHeap = priority_queue<Tp>;
36
37 template <class RAIter>
38 inline void sortGt(RAIter first, RAIter last) { sort(first, last, greater<decltype(*first)>() ); }
39
40const double eps = 1e-8;
41const int inf = 0x3f3f3f3f;
42const long long inf64 = 0x3f3f3f3f3f3f3f3fLL;
43
44 inline bool isEq(double x, double y) { return fabs(x - y) <= eps; }
45 inline bool isLt(double x, double y) { return y - x > eps; }
46 inline bool isGt(double x, double y) { return x - y > eps; }
Template
L3-001 凑零钱：01背包，输出⽅案
壳牌红喜力
重点在于如何输出字典序最⼩的解。我们可以将所有硬币按⾯值从⼤到⼩排序，然后递推求dp数组。这样在倒推⽅案时，⾯值⼩的硬币尽可能先输出。
代码如下：（模板部分不再贴出，下同）马自达mx5二手车
1const int maxN = 1e4 + 5;
2const int maxM = 100 + 5;
3
4bool dp[maxN][maxM];
5int val[maxN];
6int N, M;
7
8void input()
9 {
10    scanf("%d%d", &N, &M);
11for (int i = 1; i <= N; i++)
12        scanf("%d", val + i);
13 }
14
15void printAns()
16 {
17if (!dp[N][M])
18    {
19        puts("No Solution");
20return;
21    }
22    auto printVal = [] (int x) -> void {
23static bool first = true;
24if (!first)
25            putchar('');
26else
27            first = false;
28        printf("%d", x);
29    };
30for (int n = N, m = M; n > 0 && m > 0; n--) 31    {
32if (dp[n][m] && dp[n - 1][m - val[n]])
33        {
34            printVal(val[n]);
35            m -= val[n];
36        }
37    }
38 }
39
40void solve()
41 {
42    sortGt(val + 1, val + N + 1);
43    dp[0][0] = true;
44for (int i = 1; i <= N; i++)
45    {
46for (int j = 0; j < val[i]; j++)
47            dp[i][j] = dp[i - 1][j];
48for (int j = val[i]; j <= M; j++)
玩车震是什么意思
49            dp[i][j] = dp[i - 1][j] | dp[i - 1][j - val[i]];
50    }
51    printAns();
52 }
53
54int main()
55 {
56    input();
57    solve();
58return0;
59 }
L3-001
L3-002 堆栈：⼆分，树状数组
每当Push x时，给树状数组中第x位加上1；反之每当Pop时，设出栈的值为x，给树状数组中第x位减去1。
执⾏PeekMedian时，设当前栈中有n个元素，则所求的值x就是：满⾜树状数组中前x项前缀和>=(n+1)/2的最⼩值。代码如下：
1const int maxN = 1e5 + 10;
2
3 stack<int> stk;
4int bit[maxN];
5int N;
6
7 inline int lowbit(int x) { return x & -x; }
8
9void addToBit(int val, int pos)
10 {
11for (; pos < maxN; pos += lowbit(pos))
12        bit[pos] += val;
13 }
14
15int getPrefix(int pos)
16 {
17int ans = 0;
18for (; pos; pos -= lowbit(pos))
19        ans += bit[pos];
20return ans;
21 }
22
23void printMedian()
24 {
25if (pty())
26    {
27        puts("Invalid");
28return;
29    }
30int lessN = (stk.size() - 1) >> 1;
31int left = 1, right = maxN - 1;
32while (left < right)
33    {
34int mid = (left + right) >> 1;
35if (getPrefix(mid) <= lessN)
36            left = mid + 1;
37else
38            right = mid;
39    }
40    printf("%d\n", left);
41 }
42
43void pushToStack(int val)
44 {
45    stk.push(val);
46    addToBit(1, val);
47 }
48
仰融49void popFromStack()
50 {
51if (pty())
52    {
53        puts("Invalid");
54return;
55    }
56    addToBit(-1, p());
57    printf("%d\n", p());
58    stk.pop();
58    stk.pop();
59 }
60
61int main()
62 {
63    scanf("%d", &N);
64char cmd[16];
65int x;
66while (N--)
67    {
68        scanf("%s", cmd);
69if (cmd[1] == 'u') //Push雅马哈yzfr6
70        {
71            scanf("%d", &x);
72            pushToStack(x);
73        }
74else if (cmd[1] == 'o') //pop
75        {
76            popFromStack();
77        }
78else
79        {
80            printMedian();
81        }
82    }
83return0;
84 }
L3-002
L3-003 社交集：并查集
不要求集中任意两⼈都有共同爱好，所以直接并查集维护即可。另外不要把⼈的编号和兴趣的编号搞混。代码如下：