The 18th Zhejiang University Programming Contest Sponsored by TuSimple

A. Pretty Matrix

题意：模拟

方法：

code：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iomanip>
 5 
 6 #include <vector>
 7 #include <cstring>
 8 #include <string>
 9 #include <queue>
10 #include <deque>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #include <unordered_map>
15 #include <unordered_set>
16 #include <utility>
17 
18 #include <cmath>
19 #include <algorithm>
20 #include <cassert>
21 #include <bitset>
22 using namespace std;
23 
24 typedef long long ll;
25 typedef pair<int, int> ii;
26 typedef pair<ll, ll> l4;
27 
28 #define mp make_pair
29 #define pb push_back
30 
31 
32 const int maxn = 1e2;
33 int a[maxn][maxn], n, m, A, B;
34 
35 int main()
36 {
37   int T;
38   scanf("%d", &T);
39   for (int kase = 1; kase <= T; ++kase)
40     {
41       scanf("%d %d %d %d", &n, &m, &A, &B);
42       int ans = 0;
43       for (int i = 0; i < n; ++i)
44     for (int j = 0; j < m; ++j)
45       {
46         scanf("%d", &a[i][j]);
47         ans += a[i][j] < A || a[i][j] > B;
48       }
49       if (A > B)
50     {
51       puts("No Solution");
52     }
53       else
54     printf("%d
", ans);
55     }
56 }
View Code

WA：

B. Liblume

题意：

方法：

code：

WA：

C. Mergeable Stack

题意：n个stack，q个操作。（n, q <= 3e5)。操作有三种，stack[i].push(v); stack[i].pop(); insert stack[i] to stack[j]。

方法：链表。

code：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iomanip>
 5 
 6 #include <vector>
 7 #include <cstring>
 8 #include <string>
 9 #include <queue>
10 #include <deque>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #include <unordered_map>
15 #include <unordered_set>
16 #include <utility>
17 #include <list>
18 
19 #include <cmath>
20 #include <algorithm>
21 #include <cassert>
22 #include <bitset>
23 using namespace std;
24 
25 typedef long long ll;
26 typedef pair<int, int> ii;
27 typedef pair<ll, ll> l4;
28 
29 #define mp make_pair
30 #define pb push_back
31 
32 const int maxn = 3e5+1;
33 
34 list<int> s[maxn];
35 int n, q;
36 const int PUSH = 1, POP = 2, MOVE = 3;
37 int main()
38 {
39   int T;
40   scanf("%d", &T);
41   for (int kase = 1; kase <= T; ++kase)
42     {
43       scanf("%d %d", &n, &q);
44       for (int i = 1; i <= n; ++i)
45     s[i].clear();
46       for (int i = 0; i < q; ++i)
47     {
48       int op;
49       scanf("%d", &op);
50       if (op == PUSH)
51         {
52           int id, v;
53           scanf("%d %d", &id, &v);
54           s[id].push_back(v);
55         }
56       else if (op == POP)
57         {
58           int id;
59           scanf("%d", &id);
60           if (s[id].empty())
61         puts("EMPTY");
62           else 
63         {
64           int v = s[id].back();
65           s[id].pop_back();
66           printf("%d
", v);
67         }
68         }
69       else if (op == MOVE)
70         {
71           int dest, src;
72           scanf("%d %d", &dest, &src);
73           s[dest].splice(s[dest].end(), s[src]);
74         }
75       else
76         assert(false);
77     }
78     }
79 }
View Code

WA：

D. RAID-ZOJ

题意：

方法：

code：

WA：

E. Crosses Puzzles

题意：

方法：

code：

WA：

F. Schrodinger's Puzzles

题意：一种特殊的背包，容量为c。每个物品有一个大小sz和系数k，放入背包时价值是k*剩余容量。有两种物品，第一种物品的k都是k1， 第二种都是k2。问你背包最大价值是多少。

方法：首先现将同种的物品按照sz从小到大排序。枚举第一种物品放了几个，这样第二个物品放了几个也可以确定。下面就是将两种物品的清单merge到一起。

code：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iomanip>
 5 
 6 #include <vector>
 7 #include <cstring>
 8 #include <string>
 9 #include <queue>
10 #include <deque>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #include <unordered_map>
15 #include <unordered_set>
16 #include <utility>
17 #include <list>
18 
19 #include <cmath>
20 #include <algorithm>
21 #include <cassert>
22 #include <bitset>
23 using namespace std;
24 
25 typedef long long ll;
26 typedef pair<int, int> ii;
27 typedef pair<ll, ll> l4;
28 
29 #define mp make_pair
30 #define pb push_back
31 
32 const int maxn = 2e3;
33 int s[2][maxn], k[2], n[2], c;
34 int tots[maxn<<1];
35 int main()
36 {
37   int T;
38   scanf("%d", &T);
39   for (int kase = 1; kase <= T; ++kase)
40     {
41       for (int i = 0; i < 2; ++i)
42     scanf("%d", k+i);
43       scanf("%d", &c);
44       for (int i = 0; i < 2; ++i)
45     scanf("%d", n+i);
46       for (int i = 0; i < 2; ++i)
47     {
48       for (int j = 0; j < n[i]; ++j)
49         scanf("%d", &s[i][j]);
50       sort(s[i], s[i] + n[i]);
51     }
52       ll ans = 0;
53       for (int sz0 = 0; sz0 <= n[0]; ++sz0)
54     {
55       ll sz = 0;
56       for (int i = 0; i < sz0; ++i)
57         sz += s[0][i];
58       if (sz > c)
59         break;
60       int sz1 = 0;
61       while (sz1 < n[1] && sz + s[1][sz1] <= c)
62         {
63           sz += s[1][sz1];
64           ++sz1;
65         }
66       ll tmp = 0;
67       int p0 = 0, p1 = 0;
68       sz = c;
69       while (p0 < sz0 && p1 < sz1)
70         {
71           if (1ll * k[0] * s[1][p1] > 1ll * k[1] * s[0][p0])
72         {
73           //pick p0
74           sz -= s[0][p0++];
75           tmp += sz * k[0];
76         }
77           else
78         {
79           sz -= s[1][p1++];
80           tmp += sz * k[1];
81         }
82         }
83       while (p0 < sz0)
84         {
85           sz -= s[0][p0++];
86           tmp += sz * k[0];
87         }
88       while (p1 < sz1)
89         {
90           sz -= s[1][p1++];
91           tmp += sz * k[1];
92         }
93       if (tmp > ans)
94         ans = tmp;
95     }
96       printf("%lld
", ans);
97     }
98 }
View Code

WA：也可以用dp[i][j]表示第一种物品选了前i个，第二种选了前j个后，得到的最大价值。比较好写。dp[i][j] 只会由dp[i-1][j]和dp[i][j-1]更新过来。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iomanip>
 5 
 6 #include <vector>
 7 #include <cstring>
 8 #include <string>
 9 #include <queue>
10 #include <deque>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #include <unordered_map>
15 #include <unordered_set>
16 #include <utility>
17 #include <list>
18 
19 #include <cmath>
20 #include <algorithm>
21 #include <cassert>
22 #include <bitset>
23 using namespace std;
24 
25 typedef long long ll;
26 typedef pair<int, int> ii;
27 typedef pair<ll, ll> l4;
28 
29 #define mp make_pair
30 #define pb push_back
31 
32 const int maxn = 2e3+1;
33 ll s[2][maxn], k[2], n[2], c, sum[2][maxn];
34 ll d[maxn][maxn];
35 inline void Max(ll &a, ll b)
36 {
37   if (a < b) a = b;
38 }
39 int main()
40 {
41   int T;
42   scanf("%d", &T);
43   for (int kase = 1; kase <= T; ++kase)
44     {
45       for (int i = 0; i < 2; ++i)
46     scanf("%lld", k+i);
47       scanf("%lld", &c);
48       for (int i = 0; i < 2; ++i)
49     scanf("%lld", n+i);
50       for (int i = 0; i < 2; ++i)
51     {
52       for (int j = 1; j <= n[i]; ++j)
53         {
54           scanf("%lld", &s[i][j]);
55         }
56       sort(s[i]+1, s[i]+1+n[i]);
57       for (int j = 1; j <= n[i]; ++j)
58         sum[i][j] = sum[i][j-1] + s[i][j];
59     }
60       ll ans = 0;
61       for (int i = 0; i <= n[0]; ++i)
62     for (int j = 0; j <= n[1]; ++j)
63       d[i][j] = 0;
64       for (int i = 0; i <= n[0]; ++i)
65     for (int j = 0; j <= n[1]; ++j)
66       {
67         ll curc = sum[0][i] + sum[1][j];
68         if (curc <= c)
69           {
70         Max(ans, d[i][j]);
71         if (i < n[0])
72           Max(d[i+1][j], d[i][j] + (c - curc - s[0][i+1]) * k[0]);
73         if (j < n[1])
74           Max(d[i][j+1], d[i][j] + (c - curc - s[1][j+1]) * k[1]);
75           }
76       }
77       printf("%lld
", ans);
78     }
79 }
View Code

G. Traffic Light

题意：

方法：bfs

code：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iomanip>
 5 
 6 #include <vector>
 7 #include <cstring>
 8 #include <string>
 9 #include <queue>
10 #include <deque>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #include <unordered_map>
15 #include <unordered_set>
16 #include <utility>
17 #include <list>
18 
19 #include <cmath>
20 #include <algorithm>
21 #include <cassert>
22 #include <bitset>
23 using namespace std;
24 
25 typedef long long ll;
26 typedef pair<int, int> ii;
27 typedef pair<ll, ll> l4;
28 
29 #define mp make_pair
30 #define pb push_back
31 
32 const int maxn = 1e5;
33 int d[maxn][2], n, m, t[maxn], tot;
34 ii src, dest;
35 inline int id(const ii &pr)
36 {
37   return pr.first * m + pr.second;
38 }
39 int dx[2][2] = 
40   {
41     {-1, 1}, {0, 0}
42   };
43 int dy[2][2] = 
44   {
45     {0, 0}, {-1, 1}
46   };
47 
48 queue<pair<ii, int> > q;
49 inline void touch(ii &pr, int dist)
50 {
51   if (d[id(pr)][dist&1] == -1)
52     {
53       d[id(pr)][dist&1] = dist;
54       q.push(mp(pr, dist));
55     }
56       
57 }
58 int main()
59 {
60   int T;
61   scanf("%d", &T);
62   for (int kase = 1; kase <= T; ++kase)
63     {
64       scanf("%d %d", &n, &m);
65       tot = n * m;
66       for (int i = 0; i < tot; ++i)
67     {
68       scanf("%d", t+i);
69       d[i][0] = d[i][1] = -1;
70     }
71       scanf("%d %d %d %d", &src.first, &src.second, &dest.first, &dest.second);
72       --src.first, --src.second, --dest.first, --dest.second;
73       assert(q.empty());
74       touch(src, 0);
75       while (!q.empty())
76     {
77       ii cur = q.front().first;
78       int dist = q.front().second;
79       q.pop();
80       int curt = (t[id(cur)] ^ dist) & 1;
81       int nxtdist = dist + 1;
82       for (int i = 0; i < 2; ++i)
83         {
84           ii nxt;
85           nxt.first = cur.first + dx[curt][i];
86           nxt.second = cur.second + dy[curt][i];
87           if (nxt.first < 0 || nxt.second < 0 || nxt.first >= n || nxt.second >= m)
88           continue;
89           touch(nxt, nxtdist);
90         }
91     }
92       int ans = d[id(dest)][0];
93       int ans2 = d[id(dest)][1];
94       if (ans2 != -1)
95     if (ans == -1 || ans > ans2)
96       ans = ans2;
97       printf("%d
", ans);
98     }
99 }
View Code

WA：注意处理输入中1-based的坐标。记得检查坐标是否合法。

H. Boolean Expression

题意：

方法：

code：

WA：

I. Honorifics

题意：

方法：

code：

WA：

J. PPAP

题意：模拟

方法：

code：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iomanip>
 5 
 6 #include <vector>
 7 #include <cstring>
 8 #include <string>
 9 #include <queue>
10 #include <deque>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #include <unordered_map>
15 #include <unordered_set>
16 #include <utility>
17 
18 #include <cmath>
19 #include <algorithm>
20 #include <cassert>
21 #include <bitset>
22 using namespace std;
23 
24 typedef long long ll;
25 typedef pair<int, int> ii;
26 typedef pair<ll, ll> l4;
27 
28 #define mp make_pair
29 #define pb push_back
30 
31 int main()
32 {
33   ios::sync_with_stdio(false);
34   cin.tie(0);
35   int T;
36   cin >> T;
37   for (int kase = 1; kase <= T; ++kase)
38     {
39       string a, b;
40       cin >> a >> b;
41       b[0] = toupper(b[0]);
42       cout << b << a << '
';
43     }
44 }
View Code

WA：

  

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/skyette/p/8742585.html