Codeforces Edu Round 64 (Rated for Div. 2)

本来在快乐写题的，突然A数据炸了，全场重测，unrated……

昨晚的题也有点毒，不过总体来说还算简单。

A：

一开始我也wa on 3了，仔细想想就会发现有重点的情况。

比如n==3, 3 1 2。答案应该是6而不是7。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define fir first
 9 #define sec second
10 #define sot(a,b) sort(a+1,a+1+b)
11 #define rep1(i,a,b) for(int i=a;i<=b;++i)
12 #define rep0(i,a,b) for(int i=a;i<b;++i)
13 #define repa(i,a) for(auto &i:a)
14 #define eps 1e-8
15 #define int_inf (1<<30)-1
16 #define ll_inf (1LL<<62)-1
17 #define lson curPos<<1
18 #define rson (curPos<<1)+1
19 /* namespace */
20 using namespace std;
21 /* header end */
22 
23 int n, last = 0, ans = 0, flag = 1, llast = 0;
24 
25 int main()
26 {
27     scanf("%d%d", &n, &last);
28     n--;
29     for (int i = 1; i <= n; i++)
30     {
31         int x;
32         scanf("%d", &x);
33         if (last == 1)
34         {
35             if (x == 1)
36             {
37                 flag = 0;
38             }
39             else if (x == 2)
40             {
41                 if (llast + last == 4)
42                     ans += 2;
43                 else
44                     ans += 3;
45             }
46             else if (x == 3)
47                 ans += 4;
48         }
49         else if (last == 2)
50         {
51             if (x == 2)
52             {
53                 ans += 3;
54             }
55             else if (x == 1)
56                 ans += 3;
57             else if (x == 3)
58             {
59                 flag = 0;
60             }
61         }
62         else if (last == 3)
63         {
64             if (x == 3)
65             {
66                 ans += 4;
67             }
68             else if (x == 1)
69                 ans += 4;
70             else if (x == 2)
71             {
72                 flag = 0;
73             }
74         }
75         if (i >= 1)
76             llast = last;
77         last = x;
78     }
79     if (!flag)
80         puts("Infinite");
81     else
82     {
83         puts("Finite");
84         printf("%d
", ans);
85     }
86     return 0;
87 }
View Code

B：

各种写法都有。这题可以写得非常短。按字母在字母表的下标奇偶性来分类就好了。

然而我觉得取字母集合，sort一下再next_permutation+剪枝也可以，就是没有分类这种写法优秀。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 1e2 + 10;
 6 
 7 void print(char *a, int len)
 8 {
 9     for (int i = 1; i <= len; i++) printf("%c", a[i]);
10 }
11 
12 int main()
13 {
14     int t; scanf("%d", &t);
15     while (t--)
16     {
17         char s[maxn], a[maxn], b[maxn];
18         scanf("%s", s + 1); int len = strlen(s + 1), p = 0, q = 0;
19         sort(s + 1, s + 1 + len);
20         for (int i = 1; i <= len; i++)
21                 if (s[i] & 1) a[++p] = s[i]; else b[++q] = s[i];
22         if (!p || !q)
23         {
24             print(a, p); print(b, q);
25         }
26         else if (abs(a[p] - b[1]) != 1)
27         {
28             print(a, p); print(b, q);
29         }
30         else if (abs(b[q] - a[1]) != 1)
31         {
32             print(b, q); print(a, p);
33         }
34         else printf("No answer");
35         puts("");
36     }
37     return 0;
38 }
View Code

C：

很容易就想到二分。

 1 /* basic header */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <cstdint>
 9 #include <climits>
10 #include <float.h>
11 /* STL */
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <queue>
16 #include <stack>
17 #include <algorithm>
18 #include <array>
19 #include <iterator>
20 /* define */
21 #define ll long long
22 #define dou double
23 #define pb emplace_back
24 #define mp make_pair
25 #define fir first
26 #define sec second
27 #define sot(a,b) sort(a+1,a+1+b)
28 #define rep1(i,a,b) for(int i=a;i<=b;++i)
29 #define rep0(i,a,b) for(int i=a;i<b;++i)
30 #define repa(i,a) for(auto &i:a)
31 #define eps 1e-8
32 #define int_inf (1<<30)-1
33 #define ll_inf (1LL<<62)-1
34 #define lson curPos<<1
35 #define rson (curPos<<1)+1
36 /* namespace */
37 using namespace std;
38 /* header end */
39 
40 const int maxn = 2e5 + 10;
41 int n, z, a[maxn];
42 
43 int main()
44 {
45     scanf("%d%d", &n, &z);
46     for (int i = 0; i < n; i++) scanf("%d", &a[i]);
47     sort(a, a + n);
48     int l = 0, r = n / 2 + 1;
49     while (r - l > 1)
50     {
51         int mid = l + r >> 1, sign = 1;
52         for (int i = 0; i < mid; i++)
53             sign &= (a[n - mid + i] - a[i] >= z);
54         if (sign) l = mid; else r = mid;
55     }
56     printf("%d
", l);
57     return 0;
58 }
View Code

D：

有点像是字典树，匹配文法规则为0*1*的字符串。

树上dp，也可以DSU过。

 1 /* basic header */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <cstdint>
 9 #include <climits>
10 #include <float.h>
11 /* STL */
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <queue>
16 #include <stack>
17 #include <algorithm>
18 #include <array>
19 #include <iterator>
20 /* define */
21 #define ll long long
22 #define dou double
23 #define pb emplace_back
24 #define mp make_pair
25 #define fir first
26 #define sec second
27 #define sot(a,b) sort(a+1,a+1+b)
28 #define rep1(i,a,b) for(int i=a;i<=b;++i)
29 #define rep0(i,a,b) for(int i=a;i<b;++i)
30 #define repa(i,a) for(auto &i:a)
31 #define eps 1e-8
32 #define int_inf 0x3f3f3f3f
33 #define ll_inf 0x7f7f7f7f7f7f7f7f
34 #define lson curPos<<1
35 #define rson curPos<<1|1
36 /* namespace */
37 using namespace std;
38 /* header end */
39 
40 const int maxn = 2e5 + 10;
41 
42 int n, dp[2][maxn];
43 vector<pair<int, int>> graph[maxn];
44 ll ans;
45 
46 void calc(int u, pair<int, int> v, int mt)
47 {
48     if (!v.second)
49         dp[0][u] += mt * dp[0][v.first];
50     else
51         dp[1][u] += mt * dp[0][v.first] + mt * dp[1][v.first];
52 }
53 
54 void dfs1(int u, int p)
55 {
56     for (pair<int, int> v : graph[u])
57     {
58         if (v.first == p)
59             continue;
60         dfs1(v.first, u);
61         calc(u, v, 1);
62     }
63     ans += dp[0][u] + dp[1][u];
64     dp[0][u]++;
65 }
66 
67 void dfs2(int u, int p, int pp1, int pp2)
68 {
69     ans += pp1 + pp2;
70     for (pair<int, int> v : graph[u])
71     {
72         if (v.first == p)
73             continue;
74         calc(u, v, -1);
75         if (!v.second)
76             dfs2(v.first, u, pp1 + dp[0][u], 0);
77         else
78             dfs2(v.first, u, 0, pp1 + pp2 + dp[0][u] + dp[1][u]);
79         calc(u, v, 1);
80     }
81 }
82 
83 int main()
84 {
85     scanf("%d", &n);
86     for (int i = 1, u, v, c; i < n; i++)
87     {
88         scanf("%d%d%d", &u, &v, &c); --u; --v;
89         graph[u].pb(mp(v, c));
90         graph[v].pb(mp(u, c));
91     }
92     dfs1(0, -1); dfs2(0, -1, 0, 0);
93     cout << ans << endl;
94     return 0;
95 }
View Code

E：

看了rk1大佬的代码才意识到可以二分做。时间复杂度约等于O(NlogN)。

 1 /* basic header */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <cstdint>
 9 #include <climits>
10 #include <float.h>
11 /* STL */
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <queue>
16 #include <stack>
17 #include <algorithm>
18 #include <array>
19 #include <iterator>
20 /* define */
21 #define ll long long
22 #define dou double
23 #define pb emplace_back
24 #define mp make_pair
25 #define fir first
26 #define sec second
27 #define sot(a,b) sort(a+1,a+1+b)
28 #define rep1(i,a,b) for(int i=a;i<=b;++i)
29 #define rep0(i,a,b) for(int i=a;i<b;++i)
30 #define repa(i,a) for(auto &i:a)
31 #define eps 1e-8
32 #define int_inf (1<<30)-1
33 #define ll_inf (1LL<<62)-1
34 #define lson curPos<<1
35 #define rson (curPos<<1)+1
36 /* namespace */
37 using namespace std;
38 /* header end */
39 
40 const int maxn = 2e5 + 10;
41 int a[maxn], n;
42 
43 ll solve(int l, int r)
44 {
45     if (r - l == 1) return 0;
46     int mid = l + r >> 1;
47     ll ret = solve(l, mid) + solve(mid, r); //避免处理长度为1的区间
48     {
49         set<int>s;
50         //把p当做区间的左端点&&最大值，往右扩展。下法同理。
51         for (int i = mid - 1, j = mid, p = 0; i >= l; i--)
52         {
53             p = max(p, a[i]);
54             while (j < r && a[j] < p) s.insert(a[j++]);
55             ret += s.count(p - a[i]);
56         }
57     }
58     {
59         set<int>s;
60         for (int i = mid, j = mid - 1, p = 0; i < r; i++)
61         {
62             p = max(p, a[i]);
63             while (j >= l && a[j] < p) s.insert(a[j--]);
64             ret += s.count(p - a[i]);
65         }
66     }
67     return ret;
68 }
69 
70 int main()
71 {
72     scanf("%d", &n);
73     rep0(i, 0, n) scanf("%d", &a[i]);
74     printf("%lld
", solve(0, n));
75     return 0;
76 }
View Code

F && G：

太神仙了……再见

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