团体程序设计天梯赛练习集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;
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数组。这样在倒推⽅案时，⾯值⼩的硬币尽可能先输出。
代码如下：（模板部分不再贴出，下同）
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();
cstring转为int57 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
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 社交集：并查集
不要求集中任意两⼈都有共同爱好，所以直接并查集维护即可。另外不要把⼈的编号和兴趣的编号搞混。代码如下：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论