团体程序设计天梯赛练习集 PAT-L3 题解与程序（1~18题）

题目集链接：https://www.patest.cn/contests/gplt

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 
29 using namespace std;
30 
31 using LL = long long;
32 template <class Tp>
33 using MinHeap = priority_queue<Tp, vector<Tp>, greater<Tp>>;
34 template <class Tp>
35 using MaxHeap = priority_queue<Tp>;
36 
37 template <class RAIter>
38 inline void sortGt(RAIter first, RAIter last) { sort(first, last, greater<decltype(*first)>() ); }
39 
40 const double eps = 1e-8;
41 const int inf = 0x3f3f3f3f;
42 const 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数组。这样在倒推方案时，面值小的硬币尽可能先输出。

代码如下：（模板部分不再贴出，下同）

 1 const int maxN = 1e4 + 5;
 2 const int maxM = 100 + 5;
 3 
 4 bool dp[maxN][maxM];
 5 int val[maxN];
 6 int N, M;
 7 
 8 void input()
 9 {
10     scanf("%d%d", &N, &M);
11     for (int i = 1; i <= N; i++)
12         scanf("%d", val + i);
13 }
14 
15 void printAns()
16 {
17     if (!dp[N][M])
18     {
19         puts("No Solution");
20         return;
21     }
22     auto printVal = [] (int x) -> void {
23         static bool first = true;
24         if (!first)
25             putchar(' ');
26         else
27             first = false;
28         printf("%d", x);
29     };
30     for (int n = N, m = M; n > 0 && m > 0; n--)
31     {
32         if (dp[n][m] && dp[n - 1][m - val[n]])
33         {
34             printVal(val[n]);
35             m -= val[n];
36         }
37     }
38 }
39 
40 void solve()
41 {
42     sortGt(val + 1, val + N + 1);
43     dp[0][0] = true;
44     for (int i = 1; i <= N; i++)
45     {
46         for (int j = 0; j < val[i]; j++)
47             dp[i][j] = dp[i - 1][j];
48         for (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 
54 int main()
55 {
56     input();
57     solve();
58     return 0;
59 }

L3-001

L3-002 堆栈：二分，树状数组

每当Push x时，给树状数组中第x位加上1；反之每当Pop时，设出栈的值为x，给树状数组中第x位减去1。

执行PeekMedian时，设当前栈中有n个元素，则所求的值x就是：满足树状数组中前x项前缀和>=(n+1)/2的最小值。

代码如下：

 1 const int maxN = 1e5 + 10;
 2 
 3 stack<int> stk;
 4 int bit[maxN];
 5 int N;
 6 
 7 inline int lowbit(int x) { return x & -x; }
 8 
 9 void addToBit(int val, int pos)
10 {
11     for (; pos < maxN; pos += lowbit(pos))
12         bit[pos] += val;
13 }
14 
15 int getPrefix(int pos)
16 {
17     int ans = 0;
18     for (; pos; pos -= lowbit(pos))
19         ans += bit[pos];
20     return ans;
21 }
22 
23 void printMedian()
24 {
25     if (stk.empty())
26     {
27         puts("Invalid");
28         return;
29     }
30     int lessN = (stk.size() - 1) >> 1;
31     int left = 1, right = maxN - 1;
32     while (left < right)
33     {
34         int mid = (left + right) >> 1;
35         if (getPrefix(mid) <= lessN)
36             left = mid + 1;
37         else
38             right = mid;
39     }
40     printf("%d
", left);
41 }
42 
43 void pushToStack(int val)
44 {
45     stk.push(val);
46     addToBit(1, val);
47 }
48 
49 void popFromStack()
50 {
51     if (stk.empty())
52     {
53         puts("Invalid");
54         return;
55     }
56     addToBit(-1, stk.top());
57     printf("%d
", stk.top());
58     stk.pop();
59 }
60 
61 int main()
62 {
63     scanf("%d", &N);
64     char cmd[16];
65     int x;
66     while (N--)
67     {
68         scanf("%s", cmd);
69         if (cmd[1] == 'u') //Push
70         {
71             scanf("%d", &x);
72             pushToStack(x);
73         }
74         else if (cmd[1] == 'o') //pop
75         {
76             popFromStack();
77         }
78         else
79         {
80             printMedian();
81         }
82     }
83     return 0;
84 }

L3-002

L3-003 社交集群：并查集

不要求集群中任意两人都有共同爱好，所以直接并查集维护即可。另外不要把人的编号和兴趣的编号搞混。

代码如下：

 1 const int maxN = 1000 + 5;
 2 
 3 int N;
 4 int last[maxN];
 5 int ufs[maxN];
 6 
 7 void init()
 8 {
 9     FILL(last, -1);
10     for (int i = 1; i <= N; i++)
11         ufs[i] = i;
12 }
13 
14 int findUfs(int x) { return ufs[x] == x ? x : (ufs[x] = findUfs(ufs[x])); }
15 void unifyUfs(int x, int y) { ufs[findUfs(x)] = findUfs(y); }
16 
17 int main()
18 {
19     scanf("%d", &N);
20     init();
21     for (int i = 1; i <= N; i++)
22     {
23         int n, id;
24         scanf("%d:", &n);
25         while (n--)
26         {
27             scanf("%d", &id);
28             if (last[id] != -1)
29                 unifyUfs(i, last[id]);
30             last[id] = i;
31         }
32     }
33     vector<int> ans;
34     for (int i = 1; i <= N; i++)
35     {
36         if (findUfs(i) != i)
37             continue;
38         int cnt = 0;
39         for (int j = 1; j <= N; j++)
40             if (findUfs(j) == i)
41                 cnt += 1;
42         ans.push_back(cnt);
43     }
44     sortGt(ans.begin(), ans.end());
45     printf("%zu
", ans.size());
46     for (size_t i = 0; i < ans.size(); i++)
47     {
48         if (i != 0)
49             putchar(' ');
50         printf("%d", ans[i]);
51     }
52     return 0;
53 }

L3-003

L3-004 肿瘤诊断：BFS

BFS判断联通块个数即可。

代码如下：

 1 const int maxR = 1290;
 2 const int maxC = 130;
 3 const int maxL = 60;
 4 
 5 bool cover[maxR][maxC][maxL];
 6 bool vis[maxR][maxC][maxL];
 7 int R, C, L, T;
 8 
 9 void input()
10 {
11     scanf("%d%d%d%d", &R, &C, &L, &T);
12     int x;
13     for (int k = 0; k < L; k++)
14         for (int i = 0; i < R; i++)
15             for (int j = 0; j < C; j++)
16             {
17                 scanf("%d", &x);
18                 cover[i][j][k] = x;
19             }
20 }
21 
22 inline bool isValid(int r, int c, int l)
23 {
24     return r >= 0 && r < R && c >= 0 && c < C && l >= 0 && l < L;
25 }
26 //up, down, left, right, front, back
27 const int dr[6] = {0, 0, 0, 0, 1, -1};
28 const int dc[6] = {0, 0, -1, 1, 0, 0};
29 const int dl[6] = {-1, 1, 0, 0, 0, 0};
30 
31 int bfs(int r, int c, int l)
32 {
33     using Tuple = tuple<int, int, int>;
34     queue<Tuple> que;
35     vis[r][c][l] = true;
36     que.emplace(r, c, l);
37 
38     int res = 1;
39     while (!que.empty())
40     {
41         tie(r, c, l) = que.front();
42         que.pop();
43         for (int i = 0; i < 6; i++)
44         {
45             int nr = r + dr[i], nc = c + dc[i], nl = l + dl[i];
46             if (isValid(nr, nc, nl) && !vis[nr][nc][nl] && cover[nr][nc][nl])
47             {
48                 vis[nr][nc][nl] = true;
49                 que.emplace(nr, nc, nl);
50                 res += 1;
51             }
52         }
53     }
54     return res;
55 }
56 
57 int solve()
58 {
59     int ans = 0;
60     for (int i = 0; i < R; i++)
61         for (int j = 0; j < C; j++)
62             for (int k = 0; k < L; k++)
63                 if (!vis[i][j][k] && cover[i][j][k])
64                 {
65                     int temp = bfs(i, j, k);
66                     if (temp >= T)
67                         ans += temp;
68                 }
69     return ans;
70 }
71 
72 int main()
73 {
74     input();
75     printf("%d
", solve());
76     return 0;
77 }

L3-004

其中用来判断是否越界的isValid函数还可以进一步优化，优化后运行时间从165ms缩短为85ms，但由于编码量较大所以比赛中未必实用。

 1 inline bool isValid(int i, int r, int c, int l)
 2 {
 3     switch (i)
 4     {
 5         case 0: return l >= 0; break;
 6         case 1: return l < L; break;
 7         case 2: return c >= 0; break;
 8         case 3: return c < C; break;
 9         case 4: return r < R; break;
10         case 5: return r >= 0; break;
11     }
12 }

L3-004 Optimization

L3-005 垃圾箱分布：最短路

比较裸的最短路问题，不过要注意审题：

判断最优解的第一关键字：“垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，居民点与垃圾箱之间不能超过D_S”；

第二关键字：“如果解不唯一，则输出到所有居民点的平均距离最短的那个解”；

第三关键字：“如果这样的解还是不唯一，则输出编号最小的地点”。

代码如下：

  1 const int maxN = 1e3 + 15;
  2 const int maxK = 1e4 + 15;
  3 const int inf = 0x3f3f3f3f;
  4 
  5 struct Edge
  6 {
  7     int to, next, len;
  8     void assign(int t, int n, int l) { to = t; next = n; len = l; }
  9 };
 10 
 11 Edge elist[maxK * 2];
 12 int head[maxN];
 13 int ecnt;
 14 int N, M, K, DS;
 15 
 16 void initElist()
 17 {
 18     FILL(head, -1);
 19     ecnt = 0;
 20 }
 21 
 22 inline void addEdge(int u, int v, int len)
 23 {
 24     elist[ecnt].assign(v, head[u], len);
 25     head[u] = (ecnt++);
 26     elist[ecnt].assign(u, head[v], len);
 27     head[v] = (ecnt++);
 28 }
 29 
 30 inline int getId(const char* str) { return str[0] == 'G' ? N + atoi(str + 1) : atoi(str); }
 31 
 32 void input()
 33 {
 34     scanf("%d%d%d%d", &N, &M, &K, &DS);
 35     char s1[8], s2[8];
 36     int len;
 37 
 38     initElist();
 39     for (int i = 0; i < K; i++)
 40     {
 41         scanf("%s%s%d", s1, s2, &len);
 42         addEdge(getId(s1), getId(s2), len);
 43     }
 44 }
 45 
 46 int dist[maxN];
 47 bool inq[maxN];
 48 queue<int> que;
 49 
 50 inline void pushToQue(int v)
 51 {
 52     que.push(v);
 53     inq[v] = true;
 54 }
 55 
 56 inline int popFromQue()
 57 {
 58     int v = que.front();
 59     que.pop();
 60     inq[v] = false;
 61     return v;
 62 }
 63 
 64 void spfa(int s)
 65 {
 66     FILL(dist, 0x3f);
 67     dist[s] = 0;
 68     pushToQue(s);
 69 
 70     while (!que.empty())
 71     {
 72         int cur = popFromQue();
 73         for (int e = head[cur]; e != -1; e = elist[e].next)
 74         {
 75             int to = elist[e].to, len = elist[e].len;
 76             if (dist[cur] + len < dist[to])
 77             {
 78                 dist[to] = dist[cur] + len;
 79                 if (!inq[to])
 80                     pushToQue(to);
 81             }
 82         }
 83     }
 84 }
 85 
 86 void solve()
 87 {
 88     int ansM = 0;
 89     double minAve = 1e20;
 90     int maxMinD = 0;
 91 
 92     for (int i = 1; i <= M; i++)
 93     {
 94         spfa(N + i);
 95         if (count(dist + 1, dist + N + 1, inf) || any_of(dist + 1, dist + N + 1, [] (int d) -> bool { return d > DS; }) )
 96             continue;
 97             
 98         double curAve = accumulate(dist + 1, dist + N + 1, 0.0) / N;
 99         int curMinD = *min_element(dist + 1, dist + N + 1);
100         if (curMinD > maxMinD || (curMinD == maxMinD && curAve < minAve))
101         {
102             ansM = i;
103             minAve = curAve;
104             maxMinD = curMinD;
105         }
106     }
107 
108     if (ansM == 0)
109         puts("No Solution");
110     else
111         printf("G%d
%.1f %.1f", ansM, (double)maxMinD, minAve);
112 }
113 
114 int main()
115 {
116     input();
117     solve();
118     return 0;
119 }

L3-005

L3-006 迎风一刀斩：计算几何

“注意摆在你面前的两个多边形可不一定是端端正正摆好的，它们可能被平移、被旋转（逆时针90度、180度、或270度），或者被（镜像）翻面。”

由于旋转角一定是90°的倍数，因此可以得出：

结论1：如果一个多边形有两条及以上的斜边（横、纵坐标均不相等），那么它一定不是一刀切成的残片。

画图模拟一下，不难发现：

结论2：满足条件的残片一定不多于5条边；

结论3：如果两个残片可以拼成一个矩形，那么它们的边数之和不多于8。

结论4：满足条件的残片一定是凸多边形。

然后进一步分类讨论：

（1）如果两个残片都有3条边，检查这两个直角三角形是否全等即可。

（2）如果其中一个残片有3条边，另一个有4~5条，那么后者残缺的一块应该是一个与前一块残片全等的直角三角形。分析两块残片的斜边即可。

（3）如果两块残片都是矩形，检查它们是否有相等长度的边。

（4）如果两块残片都是有1条斜边的四边形，除了要检查两条斜边是否一致，还要检查两块残片内部的锐角是否相等，如下图。

代码如下（真·奇丑无比）：

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <tuple>
  4 #include <cmath>
  5 
  6 using namespace std;
  7 using LL = long long;
  8 
  9 LL multi(int x1, int y1, int x2, int y2)
 10 {
 11     return 1LL * x1 * y2 - 1LL * x2 * y1;
 12 }
 13 
 14 //isValid, isTriangle, N, longer, shorter, sinAngle
 15 using Tuple = tuple<bool, bool, int, int, int, double>;
 16 
 17 Tuple readFigure()
 18 {
 19     int N;
 20     scanf("%d", &N);
 21 
 22     int fx, fy, lx, ly, cx, cy;
 23     int vecX, vecY;
 24     int skewCnt = 0;
 25     int longer, shorter;
 26     int posCnt = 0, negCnt = 0;
 27     double sinAngle = 0.0;
 28     bool valid = true;
 29     scanf("%d%d", &fx, &fy);
 30     lx = fx;
 31     ly = fy;
 32 
 33     auto updateSkew = [&] (int x1, int y1, int x2, int y2) -> void { //c1, l2
 34         skewCnt += 1;
 35         longer = abs(x1 - x2);
 36         shorter = abs(y1 - y2);
 37         if (longer <= shorter)
 38             swap(longer, shorter);
 39 
 40         LL multiRes = multi(-(y1 - y2), -(x1 - x2), vecX, vecY);
 41         if (posCnt > 0 && multiRes < 0 || negCnt > 0 && multiRes > 0)
 42             sinAngle = 1.0 * fabs(multiRes) / hypot(x1 - x2, y1 - y2) / hypot(vecX, vecY);
 43     };
 44 
 45     for (int i = 2; i <= N; i++)
 46     {
 47         scanf("%d%d", &cx, &cy);
 48         if (i > 2)
 49         {
 50             if (multi(vecX, vecY, cx - lx, cy - ly) < 0)
 51                 negCnt += 1;
 52             else
 53                 posCnt += 1;
 54         }
 55         if (cx != lx && cy != ly)
 56             updateSkew(cx, cy, lx, ly);
 57         vecX = cx - lx;
 58         vecY = cy - ly;
 59         if (i < N)
 60         {
 61             lx = cx;
 62             ly = cy;
 63         }
 64     }
 65 
 66     if (cx != fx && cy != fy)
 67         updateSkew(cx, cy, fx, fy);
 68     if (multi(vecX, vecY, fx - cx, fy - cy) < 0)
 69         negCnt += 1;
 70     else
 71         posCnt += 1;
 72 
 73     if (posCnt > 0 && negCnt > 0)
 74         valid = false;
 75 
 76     if (!valid || skewCnt >= 2)
 77         return make_tuple(false, false, 0, 0, 0, 0.0);
 78     if (skewCnt == 1)
 79         return make_tuple(true, true, N, longer, shorter, sinAngle);
 80     else
 81     {
 82         longer = abs(fx - cx + fy - cy);
 83         shorter = abs(cx - lx + cy - ly);
 84         if (longer <= shorter)
 85             swap(longer, shorter);
 86         return make_tuple(true, false, N, longer, shorter, sinAngle);
 87     }
 88 }
 89 
 90 bool solve()
 91 {
 92     auto tp1 = readFigure();
 93     auto tp2 = readFigure();
 94 
 95     if (!get<0>(tp1) || !get<0>(tp2) || (get<1>(tp1) ^ get<1>(tp2)) || get<2>(tp1) + get<2>(tp2) >= 9)
 96         return false;
 97     if (get<1>(tp1))
 98     {
 99         bool res = get<3>(tp1) == get<3>(tp2) && get<4>(tp1) == get<4>(tp2);
100         if (get<2>(tp1) == 4 && get<2>(tp2) == 4)
101             res &= (fabs(get<5>(tp1) - get<5>(tp2)) < 1e-6);
102         return res;
103     }
104     else
105         return get<3>(tp1) == get<3>(tp2) || get<4>(tp1) == get<4>(tp2) ||
106                                              get<3>(tp1) == get<4>(tp2) ||
107                                              get<4>(tp1) == get<3>(tp2);
108 }
109 
110 int main()
111 {
112     int T;
113     for (scanf("%d", &T); T; T--)
114     {
115         printf("%s
", solve() ? "YES" : "NO");
116     }
117     return 0;
118 }

L3-006

L3-007 天梯地图：最短路，输出方案

依然是比较裸的最短路，但要比“垃圾箱分布”恶心得多。依然是注意审题：

判别最快到达路线的第二关键字：“如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的”。

判别最短距离路线的第二关键字：“而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的”。

为了避免代码重复，可以考虑将dist的递推式作为dijkstra函数的参数。C++11里借助Lambda表达式可以很方便地实现。

代码如下：

  1 using Pair = pair<int, int>;
  2 
  3 const int maxN = 500 + 5;
  4 int gTime[maxN][maxN];
  5 int gLen[maxN][maxN];
  6 int N, M, S, T;
  7 
  8 void input()
  9 {
 10     scanf("%d%d", &N, &M);
 11     FILL(gTime, 0x3f);
 12     FILL(gLen, 0x3f);
 13 
 14     for (int u, v, o, l, t, i = 0; i < M; i++)
 15     {
 16         scanf("%d%d%d%d%d", &u, &v, &o, &l, &t);
 17         gTime[u][v] = t;
 18         gLen[u][v] = l;
 19         if (o == 0)
 20         {
 21             gTime[v][u] = t;
 22             gLen[v][u] = l;
 23         }
 24     }
 25     scanf("%d%d", &S, &T);
 26 }
 27 
 28 Pair dist[maxN];
 29 int bef[maxN];
 30 bool vis[maxN];
 31 
 32 void initDijkstra()
 33 {
 34     FILL(dist, 0x3f);
 35     FILL(vis, 0);
 36     dist[S] = Pair(0, 0);
 37 }
 38 
 39 pair<int, vector<int>> dijkstra(function<Pair(int, int)> procFn)
 40 {
 41     initDijkstra();
 42 
 43     int cur = S;
 44     for (int _i = 1; _i < N; ++_i)
 45     {
 46         vis[cur] = true;
 47         for (int j = 0; j < N; j++)
 48             if (!vis[j] && procFn(cur, j) < dist[j])
 49             {
 50                 dist[j] = procFn(cur, j);
 51                 bef[j] = cur;
 52             }
 53         auto nextD = Pair(inf, inf);
 54         for (int j = 0; j < N; j++)
 55             if (!vis[j] && dist[j] < nextD)
 56             {
 57                 nextD = dist[j];
 58                 cur = j;
 59             }
 60     }
 61 
 62     vector<int> res;
 63     for (cur = T; ; cur = bef[cur])
 64     {
 65         res.push_back(cur);
 66         if (cur == S)
 67             break;
 68     }
 69     return { dist[T].first, move(res) };
 70 }
 71 
 72 void printPath(const vector<int> &vec)
 73 {
 74     for (auto it = vec.crbegin(); it != vec.crend(); ++it)
 75     {
 76         if (it != vec.crbegin())
 77             printf(" => ");
 78         printf("%d", *it);
 79     }
 80     putchar('
');
 81 }
 82 
 83 void solve()
 84 {
 85     auto resTime = dijkstra([] (int u, int v) {
 86         return Pair(dist[u].first + gTime[u][v], dist[u].second + gLen[u][v]);
 87     });
 88     auto resLen = dijkstra([] (int u, int v) {
 89         return Pair(dist[u].first + gLen[u][v], dist[u].second + 1);
 90     });
 91 
 92     if (resTime.second == resLen.second)
 93     {
 94         printf("Time = %d; Distance = %d: ", resTime.first, resLen.first);
 95         printPath(resTime.second);
 96     }
 97     else
 98     {
 99         printf("Time = %d: ", resTime.first);
100         printPath(resTime.second);
101         printf("Distance = %d: ", resLen.first);
102         printPath(resLen.second);
103     }
104 }
105 
106 int main()
107 {
108     input();
109     solve();
110     return 0;
111 }

L3-007

L3-008 喊山：BFS

直接BFS即可。代码如下：

 1 struct Edge
 2 {
 3     int to, next;
 4     void assign(int t, int n) { to = t; next = n; }
 5 };
 6 
 7 const int maxN = 1e4 + 5;
 8 const int maxM = 1e6 + 5;
 9 
10 Edge elist[maxM];
11 int head[maxN];
12 int qry[12];
13 int ecnt = 0;
14 int N, M, K;
15 
16 void initElist()
17 {
18     FILL(head, -1);
19     ecnt = 0;
20 }
21 
22 inline void addEdge(int u, int v)
23 {
24     elist[ecnt].assign(v, head[u]);
25     head[u] = (ecnt++);
26     elist[ecnt].assign(u, head[v]);
27     head[v] = (ecnt++);
28 }
29 
30 void input()
31 {
32     scanf("%d%d%d", &N, &M, &K);
33     initElist();
34     for (int u, v, i = 0; i < M; i++)
35     {
36         scanf("%d%d", &u, &v);
37         addEdge(u, v);
38     }
39     for (int i = 1; i <= K; i++)
40         scanf("%d", qry + i);
41 }
42 
43 int dist[maxN];
44 
45 int bfs(int s)
46 {
47     FILL(dist, -1);
48     dist[s] = 0;
49 
50     queue<int> que;
51     que.push(s);
52 
53     while (!que.empty())
54     {
55         int cur = que.front();
56         que.pop();
57         for (int e = head[cur]; e != -1; e = elist[e].next)
58         {
59             int to = elist[e].to;
60             if (dist[to] == -1)
61             {
62                 dist[to] = dist[cur] + 1;
63                 que.push(to);
64             }
65         }
66     }
67 
68     auto pos = max_element(dist + 1, dist + N + 1);
69     if (*pos <= 0)
70         return 0;
71     else
72         return (int)(pos - dist);
73 }
74 
75 void solve()
76 {
77     for (int i = 1; i <= K; i++)
78         printf("%d
", bfs(qry[i]));
79 }
80 
81 int main()
82 {
83     input();
84     solve();
85     return 0;
86 }

L3-008

L3-009 长城：凸包

链接：http://www.cnblogs.com/Onlynagesha/p/8672128.html

L3-010 是否完全二叉树：BFS，模拟

按题目要求建树然后BFS。判断它是否为完全二叉树，就看是否存在唯一的节点S满足：

（1）S要么只有左孩子，要么没有孩子；

（2）BFS过程中，它之前的节点都有2个孩子；

（3）BFS过程中，它后边的节点都没有孩子。

代码如下：

 1 struct Node
 2 {
 3     int val;
 4     Node *lch, *rch;
 5     Node(int v): val(v), lch(nullptr), rch(nullptr) {}
 6 };
 7 
 8 Node* insert(int val, Node* cur)
 9 {
10     if (cur == nullptr)
11         return new Node(val);
12     if (val > cur->val)
13         cur->lch = insert(val, cur->lch);
14     else
15         cur->rch = insert(val, cur->rch);
16     return cur;
17 }
18 
19 bool bfs(Node *root)
20 {
21     bool res = true;
22     bool fin = false;
23 
24     queue<Node*> que;
25     que.push(root);
26 
27     while (!que.empty())
28     {
29         Node *cur = que.front();
30         que.pop();
31         if (cur != root)
32             putchar(' ');
33         printf("%d", cur->val);
34 
35         if (cur->lch)
36             que.push(cur->lch);
37         if (cur->rch)
38             que.push(cur->rch);
39 
40         if (!cur->lch && cur->rch)
41             res = false;
42         else if (fin && (cur->lch || cur->rch))
43             res = false;
44         if (!cur->rch)
45             fin = true;
46     }
47 
48     putchar('
');
49     return res;
50 }
51 
52 int main()
53 {
54     int N;
55     Node *root = nullptr;
56 
57     scanf("%d", &N);
58     for (int x, i = 1; i <= N; i++)
59     {
60         scanf("%d", &x);
61         root = insert(x, root);
62     }
63 
64     if (bfs(root))
65         printf("YES");
66     else
67         printf("NO");
68 
69     return 0;
70 }

L3-010

L3-011 直捣黄龙：最短路，输出方案

我的妈呀这么多最短路……还一个比一个恶心（后边有个更恶心的）……

照着题意做即可。注意输出部分的要求是“第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数”，这个统计方案数放在最后真的很容易忽略啊，害得我最后还得补代码￣へ￣

代码如下：

  1 #include <iostream>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <tuple>
  5 #include <map>
  6 #include <string>
  7 #include <stack>
  8 
  9 #define FILL(arr, ch) memset(arr, ch, sizeof(arr))
 10 
 11 const int maxN = 200 + 10;
 12 const int inf = 0x3f3f3f3f;
 13 
 14 using Tuple = std::tuple<int, int, int>;
 15 
 16 std::map<std::string, int> idMap;
 17 std::map<int, std::string> nameMap;
 18 int enemyN[maxN];
 19 int graph[maxN][maxN];
 20 int N, K, S, T;
 21 
 22 int getId(const std::string& str)
 23 {
 24     auto iter = idMap.find(str);
 25     if (iter != idMap.end())
 26         return iter->second;
 27     idMap.emplace(str, (int)idMap.size() + 1);
 28     nameMap.emplace((int)idMap.size(), str);
 29     return (int)idMap.size();
 30 }
 31 
 32 inline const std::string& getName(int id)
 33 {
 34     return nameMap.find(id)->second;
 35 }
 36 
 37 void input()
 38 {
 39     std::string s1, s2;
 40     std::cin >> N >> K >> s1 >> s2;
 41     S = getId(s1);
 42     T = getId(s2);
 43 
 44     for (int i = 1; i < N; i++)
 45     {
 46         std::cin >> s1;
 47         int id = getId(s1);
 48         std::cin >> enemyN[id];
 49     }
 50     FILL(graph, 0x3f);
 51     int len;
 52     for (int i = 1; i <= K; i++)
 53     {
 54         std::cin >> s1 >> s2 >> len;
 55         int id1 = getId(s1);
 56         int id2 = getId(s2);
 57         graph[id1][id2] = graph[id2][id1] = len;
 58     }
 59 }
 60 
 61 struct Dist
 62 {
 63     int len;
 64     int nodeN;
 65     int totEnemyN;
 66 
 67     bool operator < (const Dist& rhs) const
 68     {
 69         if (len != rhs.len)
 70             return len < rhs.len;
 71         if (nodeN != rhs.nodeN)
 72             return nodeN > rhs.nodeN;
 73         return totEnemyN > rhs.totEnemyN;
 74     }
 75 
 76     Dist advance(int u, int v) const {
 77         return { len + graph[u][v], nodeN + 1, totEnemyN + enemyN[v] };
 78     }
 79 };
 80 
 81 Dist dist[maxN];
 82 bool vis[maxN];
 83 int prev[maxN];
 84 int cnt[maxN];
 85 
 86 void initDijkstra()
 87 {
 88     FILL(dist, 0x3f);
 89     dist[S] = { 0, 1, 0 };
 90     cnt[S] = 1;
 91 }
 92 
 93 void dijkstra()
 94 {
 95     initDijkstra();
 96     int cur = S;
 97     for (int i = 1; i < N; i++)
 98     {
 99         vis[cur] = true;
100         for (int j = 1; j <= N; j++)
101         {
102             auto nextDist = dist[cur].advance(cur, j);
103             if (nextDist.len < dist[j].len)
104                 cnt[j] = cnt[cur];
105             else if (nextDist.len == dist[j].len)
106                 cnt[j] += cnt[cur];
107 
108             if (!vis[j] && nextDist < dist[j])
109             {
110                 dist[j] = nextDist;
111                 prev[j] = cur;
112             }
113         }
114 
115         Dist minDist { inf, inf, inf };
116         for (int j = 1; j <= N; j++)
117             if (!vis[j] && dist[j] < minDist)
118             {
119                 minDist = dist[j];
120                 cur = j;
121             }
122     }
123 }
124 
125 void solve()
126 {
127     dijkstra();
128     std::stack<int> path;
129 
130     for (int cur = T; ; cur = prev[cur])
131     {
132         path.push(cur);
133         if (cur == S)
134             break;
135     }
136     bool first = true;
137     while (!path.empty())
138     {
139         int cur = path.top();
140         path.pop();
141         if (!first)
142             std::cout << "->";
143         first = false;
144         std::cout << getName(cur);
145     }
146     std::cout << '
' << cnt[T] << ' ' << dist[T].len << ' ' << dist[T].totEnemyN;
147 }
148 
149 int main()
150 {
151     input();
152     solve();
153     return 0;
154 }

L3-011

L3-012 水果忍者：计算几何，枚举

比较考验思路的一题。不过本题数据量比较小，N<=1e4的话可以用O(N^2)的算法挤进去，我加了一系列优化以后最后一个测试点只用了11ms。

题解：http://blog.csdn.net/foreyes_1001/article/details/52208749

代码如下：

  1 #include <cctype>
  2 #include <cmath>
  3 #include <cstdio>
  4 #include <stdexcept>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 using LL = long long;
 10 
 11 const int inf = 0x3f3f3f3f;
 12 
 13 template <class IntType>
 14 IntType gcd(IntType x, IntType y)
 15 {
 16     return y ? gcd(y, x % y) : x;
 17 }
 18 
 19 struct Fraction
 20 {
 21     int num, den; //numerator / denominator
 22     void assign(int _num, int _den = 1)
 23     {
 24         if (_den == 0)
 25             throw invalid_argument("Denominator should not be 0!");
 26         if (_den < 0)
 27         {
 28             _num = - _num;
 29             _den = - _den;
 30         }
 31         int g = gcd(abs(_num), _den);
 32         num = _num / g;
 33         den = _den / g;
 34     }
 35     bool operator < (const Fraction& rhs) const { return 1LL * num * rhs.den < 1LL * den * rhs.num; }
 36     bool operator == (const Fraction& rhs) const
 37     {
 38         if (num == 0)
 39             return rhs.num == 0;
 40         return num == rhs.num && den == rhs.den;
 41     }
 42 
 43     Fraction(): num(0), den(1) {}
 44     Fraction(int _num, int _den = 1) { assign(_num, _den); }
 45 };
 46 
 47 const int maxN = 10000 + 10;
 48 struct Line
 49 {
 50     int x, yUp, yDown, len;
 51     void assign(int x, int yu, int yd) { this->x = x; yUp = yu; yDown = yd; len = yUp - yDown; }
 52     bool operator < (const Line& rhs) const { return len < rhs.len; }
 53 };
 54 Line line[maxN];
 55 int N;
 56 
 57 inline Fraction scopeUp(int vUp, int vDown)
 58 {
 59     return {line[vUp].yUp - line[vDown].yDown, line[vUp].x - line[vDown].x};
 60 }
 61 inline Fraction scopeDown(int v1, int v2)
 62 {
 63     return {line[v1].yDown - line[v2].yDown, line[v1].x - line[v2].x};
 64 }
 65 
 66 void input()
 67 {
 68     scanf("%d", &N);
 69     int x, yu, yd;
 70     for (int i = 1; i <= N; i++)
 71     {
 72         scanf("%d%d%d", &x, &yu, &yd);
 73         line[i].assign(x, yu, yd);
 74     }
 75 }
 76 
 77 void solve()
 78 {
 79     sort(line + 1, line + N + 1);
 80     for (int ct = 1; ct <= N; ++ct)
 81     {
 82         Fraction minScope(-inf), maxScope(inf);
 83         bool ok = true;
 84         auto judgeSameX = [&ok, &ct] (int i) {
 85             bool res = (line[i].x == line[ct].x);
 86             if (res && (line[i].yUp < line[ct].yDown || line[i].yDown > line[ct].yDown))
 87                 ok = false;
 88             return res;
 89         };
 90         auto judgeScope = [&] () {
 91             if (maxScope < minScope)
 92                 ok = false;
 93         };
 94         for (int i = 1; ok && i <= N; i++)
 95             if (!judgeSameX(i))
 96             {
 97                 if (line[i].x < line[ct].x)
 98                 {
 99                     minScope = max(minScope, scopeUp(i, ct));
100                     maxScope = min(maxScope, scopeDown(ct, i));
101                 }
102                 else
103                 {
104                     minScope = max(minScope, scopeDown(i, ct));
105                     maxScope = min(maxScope, scopeUp(i, ct));
106                 }
107                 judgeScope();
108             }
109         if (ok)
110         {
111             printf("%d %d %d %d", line[ct].x, line[ct].yDown,
112                    line[ct].x + minScope.den, line[ct].yDown + minScope.num);
113             return;
114         }
115     }
116     throw logic_error("Answer not found!");
117 }
118 
119 int main()
120 {
121     input();
122     solve();
123     return 0;
124 }

L3-012

L3-013 非常弹的球：数学，物理

根据物理公式推导即可，答案是一个无穷级数。注意单位的转换。

代码如下：

 1 #include <iostream>
 2 #include <iomanip>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int w, p;
 8   cin >> w >> p;
 9   cout << fixed << setprecision(3) << 2000.0 / (9.8 * w / 100.0 * p / 100.0);
10   return 0;
11 }

L3-013

L3-014 周游世界：最短路，输出方案

整套题集最恶心的最短路没有之一。

代码里用了拆点的思想，将不同线路交错的换乘点拆成多个。状态转移时以经停站数量为第一关键字，以换乘次数为第二关键字。

代码如下：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <utility>
  7 #include <queue>
  8 #include <stack>
  9 
 10 #define FILL(arr, ch) memset(arr, ch, sizeof(arr))
 11 
 12 const int inf = 0x3f3f3f3f;
 13 
 14 struct OldNode
 15 {
 16     std::vector<int> newNodes;
 17 };
 18 OldNode oldNodes[10000];
 19 
 20 struct NewNode
 21 {
 22     int spotId;
 23     int routeId;
 24     NewNode(int s, int r): spotId(s), routeId(r) {}
 25 };
 26 std::vector<NewNode> newNodes;
 27 
 28 int createNewNode(int spotId, int routeId)
 29 {
 30     auto newId = static_cast<int>(newNodes.size());
 31     newNodes.emplace_back(spotId, routeId);
 32     oldNodes[spotId].newNodes.push_back(newId);
 33     return newId;
 34 }
 35 
 36 struct Edge
 37 {
 38     int to, next;
 39     void assign(int t, int n) { to = t; next = n; }
 40 };
 41 Edge elist[100005];
 42 int head[10005];
 43 int ecnt;
 44 int routeN;
 45 
 46 void initEList() { FILL(head, -1); ecnt = 0; }
 47 
 48 inline void addEdge(int u, int v) //bidirectional
 49 {
 50     elist[ecnt].assign(v, head[u]);
 51     head[u] = (ecnt++);
 52     elist[ecnt].assign(u, head[v]);
 53     head[v] = (ecnt++);
 54 }
 55 
 56 void inputGraph()
 57 {
 58     scanf("%d", &routeN);
 59     initEList();
 60     for (int routeId = 1; routeId <= routeN; ++routeId)
 61     {
 62         int spotN, spotId;
 63         scanf("%d%d", &spotN, &spotId);
 64         int lastNewId = createNewNode(spotId, routeId);
 65         int curNewId;
 66         for (int i = 2; i <= spotN; i++)
 67         {
 68             scanf("%d", &spotId);
 69             curNewId = createNewNode(spotId, routeId);
 70             addEdge(lastNewId, curNewId);
 71             lastNewId = curNewId;
 72         }
 73     }
 74 }
 75 
 76 using Pair = std::pair<int, int>;
 77 
 78 std::queue<int> que;
 79 Pair dist[10005];
 80 int prev[10005];
 81 bool inq[10005];
 82 
 83 void initSpfa(int startSpot)
 84 {
 85     FILL(dist, 0x3f);
 86     for (auto newId: oldNodes[startSpot].newNodes)
 87     {
 88         dist[newId] = {0, 0};
 89         que.push(newId);
 90     }
 91 }
 92 
 93 inline void pushToQueue(int v)
 94 {
 95     if (inq[v])
 96         return;
 97     inq[v] = true;
 98     que.push(v);
 99 }
100 
101 inline int popFromQueue()
102 {
103     int v = que.front();
104     que.pop();
105     inq[v] = false;
106     return v;
107 }
108 
109 inline void updateDist(int from, int to, const Pair& nextDist)
110 {
111     if (nextDist < dist[to])
112     {
113         dist[to] = nextDist;
114         prev[to] = from;
115         pushToQueue(to);
116     }
117 }
118 
119 void spfa(int startSpot)
120 {
121     initSpfa(startSpot);
122     while (!que.empty())
123     {
124         int cur = popFromQueue();
125 
126         int oldId = newNodes[cur].spotId;
127         for (auto to: oldNodes[oldId].newNodes)
128         {
129             if (to == cur)
130                 continue;
131             Pair nextDist { dist[cur].first, dist[cur].second + 1 };
132             updateDist(cur, to, nextDist);
133         }
134         for (int e = head[cur]; e != -1; e = elist[e].next)
135         {
136             int to = elist[e].to;
137             Pair nextDist { dist[cur].first + 1, dist[cur].second };
138             updateDist(cur, to, nextDist);
139         }
140     }
141 }
142 
143 void printPath(int startOldId, int endNewId)
144 {
145     std::stack<int> stk;
146     for (int cur = endNewId; ; cur = prev[cur])
147     {
148         stk.push(cur);
149         if (newNodes[cur].spotId == startOldId)
150             break;
151     }
152     auto popFromStack = [&stk] () {
153         int v = stk.top();
154         stk.pop();
155         return v;
156     };
157     int head = popFromStack();
158     int tail = popFromStack();
159     auto printLine = [&head, &tail] () {
160         printf("Go by the line of company #%d from %04d to %04d.
",
161                newNodes[head].routeId, newNodes[head].spotId, newNodes[tail].spotId);
162     };
163     while (!stk.empty())
164     {
165         if (newNodes[stk.top()].routeId != newNodes[head].routeId)
166         {
167             printLine();
168             head = popFromStack();
169         }
170         else
171             tail = popFromStack();
172     }
173     printLine();
174 }
175 
176 void solve(int startSpot, int endSpot)
177 {
178     spfa(startSpot);
179     Pair minDist {inf, inf};
180     int endNewId = -1;
181     for (int newId: oldNodes[endSpot].newNodes)
182         if (dist[newId] < minDist)
183         {
184             minDist = dist[newId];
185             endNewId = newId;
186         }
187     if (endNewId == -1)
188         printf("Sorry, no line is available.
");
189     else
190     {
191         printf("%d
", dist[endNewId].first);
192         printPath(startSpot, endNewId);
193     }
194 }
195 
196 int main()
197 {
198     inputGraph();
199     int Q, s, t;
200     scanf("%d", &Q);
201     for (int i = 0; i < Q; i++)
202     {
203         scanf("%d%d", &s, &t);
204         solve(s, t);
205     }
206     return 0;
207 }

L3-014

L3-015 球队“食物链”：TSP，状态压缩DP

类比旅行商问题的DP解法：设dp[v][S]表示从节点v出发，遍历点集S中所有节点，然后回到节点1的字典序最小的路径（也可能不存在）。

伪代码形式的状态转移方程：

dp[v][S] = noPath
for each u in S:
    if dp[u][S - v] != noPath
        update dp[v][S]

存储中间路径时只需保存下一个节点是谁，不需要保留整条路径。

代码如下：（代码中节点编号是0 ~ N - 1，另外这份代码写得确实很丑，毕竟我太弱又好久没写过状压DP(；′⌒`）

  1 const int maxN = 20;
  2 
  3 int N;
  4 bool graph[maxN][maxN];
  5 
  6 void input()
  7 {
  8     char str[maxN][maxN + 1];
  9     scanf("%d", &N);
 10     for (int i = 0; i < N; i++)
 11         scanf("%s", str[i]);
 12     for (int i = 0; i < N; i++)
 13         for (int j = 0; j < N; j++)
 14         {
 15             if (str[i][j] == 'W')
 16                 graph[i][j] = true;
 17             else if (str[i][j] == 'L')
 18                 graph[j][i] = true;
 19         }
 20 }
 21 
 22 struct BSet
 23 {
 24     int size;
 25     int val;
 26     void assign(int v)
 27     {
 28         val = v;
 29         size = 0;
 30         for (; v; v >>= 1)
 31             size += v & 1;
 32     }
 33     bool operator < (const BSet& rhs) const {
 34         return size < rhs.size || (size == rhs.size && val < rhs.val);
 35     }
 36     bool hasNode(int n) const {
 37         n -= 1;
 38         return (val >> n) & 1;
 39     }
 40     int remove(int n) const {
 41         n -= 1;
 42         return val & (-1 ^ (1 << n));
 43     }
 44 };
 45 
 46 BSet bset[1 << maxN];
 47 int to[maxN][1 << maxN];
 48 
 49 void initBSet()
 50 {
 51     int lim = (1 << (N - 1));
 52     for (int i = 0; i < lim; i++)
 53         bset[i].assign(i);
 54     sort(bset, bset + lim);
 55 }
 56 
 57 void solve()
 58 {
 59     FILL(to, -1);
 60     initBSet();
 61     for (int i = 1; i < N; i++)
 62         if (graph[i][0])
 63             to[i][0] = 0;
 64 
 65     int lim = (1 << (N - 1));
 66     for (int s = 1; s < lim; s++)
 67     {
 68         for (int i = 0; i < N; i++) //dp[i][bset[s].val]
 69         {
 70             if (i > 0 && bset[s].hasNode(i))
 71                 continue;
 72             for (int j = 1; j < N; j++)
 73             {
 74                 if (!bset[s].hasNode(j))
 75                     continue;
 76                 if (graph[i][j] && to[j][bset[s].remove(j)] != -1)
 77                 {
 78                     to[i][bset[s].val] = j;
 79                     break;
 80                 }
 81             }
 82         }
 83     }
 84 
 85     if (to[0][lim - 1] == -1)
 86     {
 87         printf("No Solution");
 88         return;
 89     }
 90     int S = lim - 1;
 91     int cur = 0;
 92     for (int i = 0; i < N; i++)
 93     {
 94         if (i != 0)
 95             putchar(' ');
 96         printf("%d", cur + 1);
 97         cur = to[cur][S];
 98         S ^= (1 << (cur - 1));
 99     }
100 }
101 
102 int main()
103 {
104     input();
105     solve();
106     return 0;
107 }

L3-015

L3-016 二叉搜索树的结构：模拟，字符串

按照题意模拟即可，就是多种询问处理起来有些麻烦。此外要注意询问的数值不在二叉树内的情况。

处理询问格式时我用了C++11的正则表达式库，这玩意儿编译起来真的好慢啊，第一次交居然编译超时……

注意捕获整数的格式应为-?d+（前面有0~1个负号）。代码里的写法是错误的，那样可能捕获多个负号，不过本题并不受影响。

还有用try - catch判断非法数值的方法可以说是粗陋至极了(￣▽￣)／

代码如下：

  1 struct Node
  2 {
  3     int val;
  4     size_t lch, rch, par;
  5     Node(int v, size_t p = -1): val(v), lch(-1), rch(-1), par(p) {}
  6 };
  7 vector<Node> node;
  8 int N, M;
  9 
 10 void insert(int x)
 11 {
 12     if (node.empty())
 13     {
 14         node.emplace_back(x);
 15         return;
 16     }
 17     size_t cur = 0;
 18     size_t nextV = (x < node[0].val) ? node[0].lch : node[0].rch;
 19     while (nextV != -1)
 20     {
 21         cur = nextV;
 22         nextV = (x < node[cur].val) ? node[cur].lch : node[cur].rch;
 23     }
 24 
 25     *(x < node[cur].val ? &node[cur].lch : &node[cur].rch) = node.size();
 26     node.emplace_back(x, cur);
 27 }
 28 
 29 pair<size_t, int> _findNode(int val)
 30 {
 31     size_t cur = 0;
 32     int layer = 0;
 33     while (cur != -1)
 34     {
 35         if (node[cur].val == val)
 36             return { cur, layer };
 37         layer += 1;
 38         if (val < node[cur].val)
 39             cur = node[cur].lch;
 40         else
 41             cur = node[cur].rch;
 42     }
 43     throw invalid_argument("val not found!");
 44 }
 45 
 46 inline size_t findNode(int val) { return _findNode(val).first; }
 47 inline size_t getLayer(int val) { return _findNode(val).second; }
 48 
 49 bool checkRoot(int a) { return node[0].val == a; }
 50 bool checkSiblings(int a, int b) { return node[findNode(a)].par == node[findNode(b)].par; }
 51 bool checkParent(int a, int b) { return node[findNode(b)].par == findNode(a); }
 52 bool checkLeftChild(int a, int b) { return node[findNode(b)].lch == findNode(a); }
 53 bool checkRightChild(int a, int b) { return node[findNode(b)].rch == findNode(a); }
 54 bool checkSameLevel(int a, int b) { return getLayer(a) == getLayer(b); }
 55 
 56 #define SOLVE_BRANCH(rgx, func) 
 57     if (regex_match(cmd, rgxResult, rgx)) { 
 58         try { return func(stoi(rgxResult[1].str()), stoi(rgxResult[2].str())); } 
 59         catch (invalid_argument) { return false; } 
 60     }
 61 
 62 bool solve(const char* cmd)
 63 {
 64     static regex rgxCheckRoot {R"((-*d+) is the root
*)"},
 65                  rgxCheckSiblings {R"((-*d+) and (-*d+) are siblings
*)"},
 66                  rgxCheckParent {R"((-*d+) is the parent of (-*d+)
*)"},
 67                  rgxCheckLeftChild {R"((-*d+) is the left child of (-*d+)
*)"},
 68                  rgxCheckRightChild {R"((-*d+) is the right child of (-*d+)
*)"},
 69                  rgxCheckSameLevel {R"((-*d+) and (-*d+) are on the same level
*)"};
 70 
 71     cmatch rgxResult;
 72     if (regex_match(cmd, rgxResult, rgxCheckRoot))
 73         return checkRoot(stoi(rgxResult[1].str()));
 74 
 75     SOLVE_BRANCH(rgxCheckSiblings, checkSiblings);
 76     SOLVE_BRANCH(rgxCheckParent, checkParent);
 77     SOLVE_BRANCH(rgxCheckLeftChild, checkLeftChild);
 78     SOLVE_BRANCH(rgxCheckRightChild, checkRightChild);
 79     SOLVE_BRANCH(rgxCheckSameLevel, checkSameLevel);
 80 
 81     throw invalid_argument("Error while matching command!");
 82 }
 83 
 84 int main()
 85 {
 86     scanf("%d", &N);
 87     for (int x, i = 0; i < N; i++)
 88     {
 89         scanf("%d", &x);
 90         insert(x);
 91     }
 92     char cmd[1234];
 93     scanf("%d", &M);
 94     while (getchar() != '
');
 95     for (int i = 0; i < M; i++)
 96     {
 97         fgets(cmd, 1234, stdin);
 98         printf("%s
", solve(cmd) ? "Yes" : "No");
 99     }
100     return 0;
101 }

L3-016

L3-017 森森快递：贪心，线段树

如果区间A包含了区间B，那么选择区间A显然是没有意义的。选择A的收益不会比选择B高，且会导致更多资源的浪费。

然后考虑其他不被包含的区间，将它们按左端点从小到大排序（此时右端点也是排好序的），此时我们的贪心策略是：尽可能利用左边的区间，从而给右边创造更多机会。

因为涉及区间修改，以及查询区间内最小值这两种操作，所以需要借助线段树维护。

代码如下：（线段树写得比较丑(*/ω＼*）

  1 const int maxN = 1e5 + 10;
  2 
  3 struct Node
  4 {
  5     int val;
  6     int tag;
  7     Node *lch, *rch;
  8 
  9     Node(int v, Node* l = nullptr, Node* r = nullptr):
 10             val(v), tag(0), lch(l), rch(r) {}
 11 
 12     void pushTag()
 13     {
 14         if (tag == 0)
 15             return;
 16 
 17         val += tag;
 18         if (lch)
 19         {
 20             lch->tag += this->tag;
 21             rch->tag += this->tag;
 22         }
 23         tag = 0;
 24     }
 25 };
 26 
 27 struct Range
 28 {
 29     int left, right;
 30     Range(int l, int r): left(l), right(r) {}
 31     bool operator < (const Range& rhs) const {
 32         return right < rhs.right || (right == rhs.right && left > rhs.left);
 33     }
 34 };
 35 
 36 vector<Node> segTree;
 37 vector<Range> range;
 38 Node *root;
 39 int lim[maxN];
 40 int N, Q;
 41 
 42 Node* _initSegTree(int left, int right)
 43 {
 44     if (right - left == 1)
 45     {
 46         segTree.emplace_back(lim[left]);
 47         return &segTree.back();
 48     }
 49     int mid = (left + right) >> 1;
 50     auto pl = _initSegTree(left, mid), pr = _initSegTree(mid, right);
 51     segTree.emplace_back(min(pl->val, pr->val), pl, pr);
 52     return &segTree.back();
 53 }
 54 
 55 void initSegTree()
 56 {
 57     segTree.reserve(N * 2 + 10);
 58     root = _initSegTree(1, N);
 59 }
 60 
 61 namespace _SegTree_Impl
 62 {
 63     int rl, rr, delta;
 64 }
 65 
 66 void _modify(int nl, int nr, Node* cur)
 67 {
 68     using namespace _SegTree_Impl;
 69     cur->pushTag();
 70     if (rl <= nl && rr >= nr)
 71     {
 72         cur->tag += delta;
 73         cur->pushTag();
 74         return;
 75     }
 76     else if (rl >= nr || rr <= nl)
 77         return;
 78 
 79     int mid = (nl + nr) >> 1;
 80     _modify(nl, mid, cur->lch);
 81     _modify(mid, nr, cur->rch);
 82     cur->val = min(cur->lch->val, cur->rch->val);
 83 }
 84 
 85 void modify(int left, int right, int v)
 86 {
 87     using namespace _SegTree_Impl;
 88     if (v == 0)
 89         return;
 90 
 91     rl = left;
 92     rr = right;
 93     delta = v;
 94     _modify(1, N, root);
 95 }
 96 
 97 int _query(int nl, int nr, Node* cur)
 98 {
 99     using namespace _SegTree_Impl;
100     cur->pushTag();
101     if (rl <= nl && rr >= nr)
102         return cur->val;
103     else if (rl >= nr || rr <= nl)
104         return 0x7fffffff;
105 
106     int mid = (nl + nr) >> 1;
107     return min(_query(nl, mid, cur->lch), _query(mid, nr, cur->rch));
108 }
109 
110 int query(int left, int right)
111 {
112     using namespace _SegTree_Impl;
113     rl = left;
114     rr = right;
115     return _query(1, N, root);
116 }
117 
118 void input()
119 {
120     scanf("%d%d", &N, &Q);
121     for (int i = 1; i < N; i++)
122         scanf("%d", lim + i);
123     for (int i = 1; i <= Q; i++)
124     {
125         int x, y;
126         scanf("%d%d", &x, &y);
127         if (x > y)
128             swap(x, y);
129         range.emplace_back(x + 1, y + 1);
130     }
131 }
132 
133 void solve()
134 {
135     initSegTree();
136     sort(range.begin(), range.end());
137 
138     LL ans = 0;
139     for (const auto& rng: range)
140     {
141         int left = rng.left;
142         int right = rng.right;
143         int qryRes = query(left, right);
144         ans += qryRes;
145         modify(left, right, -qryRes);
146     }
147 
148     printf("%lld", ans);
149 }
150 
151 int main()
152 {
153     input();
154     solve();
155     return 0;
156 }

L3-017

L3-018 森森美图：最短路

在最短路的基础上稍微涉及了些计算几何的知识。

求start→end的最短路时，要求途径的节点都在向量start→end的逆时针方向（配合向量叉积判断），对于两个端点只计算end的权值。

求end→start的最短路时，要求途径的节点都在向量end→start的逆时针方向，对于两个端点只计算start的权值。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <functional>
 7 
 8 using namespace std;
 9 
10 const double sqrt2 = sqrt(2.0);
11 const int maxN = 100 + 5;
12 const int dir[8][2] = {
13         {1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}
14 };
15 
16 int A[maxN][maxN];
17 double dist[maxN][maxN];
18 bool inq[maxN][maxN];
19 int R, C;
20 int CS, RS, CT, RT;
21 
22 void input()
23 {
24     scanf("%d%d", &R, &C);
25     for (int r = 0; r < R; r++)
26         for (int c = 0; c < C; c++)
27             scanf("%d", A[r] + c);
28     scanf("%d%d%d%d", &CS, &RS, &CT, &RT);
29 }
30 
31 inline int multi(int c1, int r1, int c2, int r2)
32 {
33     return c1 * r2 - c2 * r1;
34 }
35 
36 inline bool isValid(int r, int c)
37 {
38     return r >= 0 && r < R && c >= 0 && c < C;
39 }
40 
41 double spfa(int rs, int cs, int rt, int ct) //NOLINT
42 {
43     using Pair = pair<int, int>;
44     queue<Pair> que;
45     que.emplace(rs, cs);
46     memset(dist, 0x7f, sizeof(dist));
47     dist[rs][cs] = 0.0;
48 
49     int curR, curC;
50     while (!que.empty())
51     {
52         tie(curR, curC) = que.front();
53         que.pop();
54         inq[curR][curC] = false;
55         for (int i = 0; i < 8; i++)
56         {
57             int nextR = curR + dir[i][0];
58             int nextC = curC + dir[i][1];
59             if (!isValid(nextR, nextC) ||
60                     ((nextR != rt || nextC != ct) && multi(ct - cs, rt - rs, nextC - cs, nextR - rs) >= 0))
61                 continue;
62 
63             double len = A[nextR][nextC] +
64                     (i < 4 ? 0.0 : (sqrt2 - 1.0) * (A[nextR][nextC] + A[curR][curC]));
65             if (dist[curR][curC] + len < dist[nextR][nextC])
66             {
67                 dist[nextR][nextC] = dist[curR][curC] + len;
68                 if (!inq[nextR][nextC])
69                 {
70                     inq[nextR][nextC] = true;
71                     que.emplace(nextR, nextC);
72                 }
73             }
74         }
75     }
76     return dist[rt][ct];
77 }
78 
79 double solve()
80 {
81     return spfa(RS, CS, RT, CT) + spfa(RT, CT, RS, CS);
82 }
83 
84 int main()
85 {
86     input();
87     printf("%.2f", solve());
88     return 0;
89 }

L3-018