Codeforces Round #526 (Div. 2) Solution

A. The Fair Nut and Elevator

Solved.

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 110
 5 int n, a[N];
 6 
 7 int main()
 8 {
 9     while (scanf("%d", &n) != EOF)
10     {
11         for (int i = 1; i <= n; ++i) scanf("%d", a + i);
12         int res = 1e9;
13         for (int x = 1, tmp = 0; x <= 100; ++x, res = min(res, tmp), tmp = 0) for (int i = 1; i <= n; ++i) if (a[i])
14         {
15             tmp += a[i] * (abs(x - i) + abs(i - 1) + abs(x - 1) + abs(x - 1) + abs(i - 1) + abs(x - i)); 
16         }
17         printf("%d
", res);
18     }
19     return 0;
20 }

View Code

B. Kvass and the Fair Nut

Upsolved.

题意：

刚开始题意读错，过了pretest就没管了

有$n桶啤酒，要从中取出s升，求取出后剩余的量最少的那桶啤酒最大$

思路：

二分或者直接算都行

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 1010
 6 int n;
 7 ll s, v[N];
 8 
 9 bool check(ll x)
10 {
11     ll tot = 0;
12     for (int i = 1; i <= n; ++i) 
13     {
14         if (v[i] < x) return false;  
15         tot += v[i] - x;
16     }
17     return tot >= s;
18 }
19 
20 int main()
21 {
22     while (scanf("%d%lld", &n, &s) != EOF)
23     {
24         for (int i = 1; i <= n; ++i) scanf("%lld", v + i);
25         ll l = 0, r = 1e9, res = -1; 
26         while (l <= r)
27         {
28             ll mid = (l + r) >> 1;
29             if (check(mid))
30             {
31                 res = mid;
32                 l = mid + 1;
33             }
34             else
35                 r = mid - 1;
36         }
37         printf("%lld
", res);
38     }
39     return 0;
40 }

View Code

C. The Fair Nut and String

Solved.

题意：

有一串字符串，求有多少个字符串，是abababab形式的。

思路：

字符不是‘a’ 也不是‘b’ 的话是没用的，然后如果两个'a'之间有多个'b'也没用

缩短字符串后

必然是aaabaaababab 这样的形式的

那么像统计DAG那样统计就没了

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 100010
 6 const ll MOD = (ll)1e9 + 7;
 7 char s[N], t[N];
 8 
 9 int main()
10 {
11     while (scanf("%s", s + 1) != EOF)
12     {
13         int n = 0; 
14         for (int i = 1, len = strlen(s + 1); i <= len; ++i) if (s[i] == 'a' || s[i] == 'b')
15         {
16             if (s[i] == 'a') t[++n] = 'a';  
17             else if (s[i] == 'b' && t[n] == 'a') t[++n] = 'b';  
18         }
19         if (n == 0)
20         {
21             puts("0");
22             continue;
23         }
24         ll res = 1, pre = 1, cnt = 1; 
25         for (int i = 2; i <= n; ++i)  
26         {
27             if (t[i] == 'b') 
28             {
29                 pre = (pre * (cnt + 1)) % MOD;
30                 cnt = 0; 
31             }    
32             else 
33             {
34                 ++cnt;
35                 res = (res + pre) % MOD;
36             }
37         }
38         printf("%lld
", res);
39     }
40     return 0;
41 }

View Code

D. The Fair Nut and the Best Path

Upsolved.

题意：

在一棵树上，每个点是加油站，最多加油$w_i，然后每条边是路，耗费油v_i$

$定义f(u, v)为u->v的简单路径上每个点都加满油，假设油箱容量无限，最后剩下的油量$

如果其中某条路上油耗尽了，那么这条路是不可行的

思路：

我们把点权视为正直，边权视为负值

然后就是求任意两点之间的最大权值和

不需要考虑不合法的路径，因为如果存在不合法的路劲，

那么肯定存在另一条合法的路径使得答案比它更优。

令$f[u] 表示到达u的子树中某点的最大权，这是纵向路径$

再考虑横向路径即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 300010
 6 #define pii pair <int, int>
 7 int n, w[N];
 8 vector <pii> G[N];
 9 ll res, f[N];
10 
11 void DFS(int u, int fa)
12 {
13     f[u] = w[u];
14     ll Max[2] = {0, 0};
15     for (auto it : G[u]) 
16     {
17         int v = it.first; 
18         if (v == fa) continue;
19         DFS(v, u);
20         ll cost = it.second;
21         f[u] = max(f[u], f[v] - cost + w[u]);
22         ll tmp = f[v] - cost;
23         if (tmp > Max[0])
24         {
25             Max[1] = Max[0];
26             Max[0] = tmp;
27         }
28         else if (tmp > Max[1])
29             Max[1] = tmp;
30     }
31     res = max(res, max(f[u], Max[0] + Max[1] + w[u])); 
32 }
33 
34 int main()
35 {
36     while (scanf("%d", &n) != EOF)
37     {
38         for (int i = 1; i <= n; ++i) scanf("%d", w + i);
39         for (int i = 1; i <= n; ++i) G[i].clear();
40         for (int i = 1, u, v, w; i < n; ++i)
41         {
42             scanf("%d%d%d", &u, &v, &w);
43             G[u].emplace_back(v, w);
44             G[v].emplace_back(u, w);
45         }
46         res = 0;
47         DFS(1, 1);
48         printf("%lld
", res);
49     }    
50     return 0;
51 }

View Code

E. The Fair Nut and Strings

Upsolved.

题意：

一共有$k个长度为n的字符串，他们的范围是[s, t] 之间，按字典序排序$

求这些字符串(构造k个满足字典序要求的字符串)最多有多少个前缀

思路：

相当于给出一棵二叉字典树，给出左右界，叶子节点不超过$k个$

求最多节点个数

能扩展就扩展，贪心一下即可

注意特判$k = 1$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 500010
 6 int n, k;
 7 char s[N], t[N];
 8 
 9 int main()
10 {
11     while (scanf("%d%d", &n, &k) != EOF)
12     {
13         scanf("%s%s", s + 1, t + 1);
14         if (k == 1)
15         {
16             printf("%d
", n);
17             continue;
18         }
19         int flag = 0;
20         ll cur = 0, res = 0; k -= 2;
21         for (int i = 1; i <= n; ++i)
22         {
23             if (flag == 0 && s[i] != t[i])
24                 flag = 1;  
25             else if (flag == 1)
26             {
27                 ll extend = cur;
28                 if (s[i] == 'a') ++extend;
29                 if (t[i] == 'b') ++extend; 
30                 if (extend <= k)
31                 {
32                     k -= extend;
33                     cur += extend;
34                 }
35                 else
36                 {
37                     cur += k;
38                     k = 0;
39                 }
40             }
41             res += cur + 1 + flag;
42         }
43         printf("%lld
", res); 
44     }
45     return 0;
46 }

View Code

F. Max Mex

Upsolved.

题意：

一棵树上，两种操作

$交换两点的p[]值$

$询问MEX(v(l)), l表示某挑简单路径上权值的集合$

思路：

我们考虑将点按权值排序

我们考虑$1 -> i 和 i + 1 -> j$

$这两段的合并$

如果可以合并，那么答案的下限就是$j$

$树上的路径有三种类型$

$1、一个点$

$2、一条链$

$3、两条链$

那分情况讨论，一共只有6种情况

$但是这样太麻烦了$

$我们考虑这三种状态都可以用两条链的情况来表示$

$那么合并的时候，一条路径可以用两个点来表示$

$那么一条路径如果包含另外一条路径的两个端点$

$那么这条路径就包含另外一条路径$

$也就是说我们只需要分两次合并另外一条路径的两点即可$

$这样就只有一种情况$

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 200010
  5 int n, q, p[N];
  6 vector <int> G[N];
  7 
  8 int in[N], out[N];
  9 namespace ST
 10 {
 11     int rmq[N << 1];
 12     int mm[N << 1];
 13     int dp[N << 1][20]; 
 14     int F[N << 1], P[N];
 15     int cnt, cnt2;
 16     void init(int n)
 17     {
 18         mm[0] = -1;
 19         for (int i = 1; i <= n; ++i)
 20         {
 21             mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
 22             dp[i][0] = i;
 23         }
 24         for (int j = 1; j <= mm[n]; ++j)
 25             for (int i = 1; i + (1 << j) - 1 <= n; ++i)
 26             {
 27                 dp[i][j] = rmq[dp[i][j - 1]] < rmq[dp[i + (1 << (j - 1))][j - 1]] ? 
 28                     dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1];
 29             }
 30     }
 31     void DFS(int u, int pre, int dep)
 32     {
 33         F[++cnt] = u;
 34         rmq[cnt] = dep;
 35         P[u] = cnt;
 36         in[u] = ++cnt2;
 37         for (auto v : G[u]) if (v != pre)
 38         {
 39             DFS(v, u, dep + 1);
 40             F[++cnt] = u;
 41             rmq[cnt] = dep;
 42         }
 43         out[u] = cnt2;
 44     }
 45     void init(int root, int node_num)
 46     {
 47         cnt = 0; cnt2 = 0;
 48         DFS(root, root, 0);
 49         init(2 * node_num - 1);
 50     }
 51     int query(int a, int b)
 52     {
 53         a = P[a], b = P[b];
 54         if (a > b) swap(a, b);
 55         int k = mm[b - a + 1];
 56         return F[rmq[dp[a][k]] <= rmq[dp[b - (1 << k) + 1][k]] ?
 57                     dp[a][k] : dp[b - (1 << k) + 1][k]];
 58     }
 59 }
 60 
 61 namespace SEG
 62 {
 63     struct node
 64     {
 65         int u, v, p;   
 66         void init() { u = v = p = 0; }
 67         node () {} 
 68         node (int u, int v, int p) : u(u), v(v), p(p) {}
 69     }a[N << 2], res; 
 70     int ans;
 71     void init() { memset(a, 0, sizeof a); }
 72     bool anc(int x, int y)
 73     {
 74         return in[x] <= in[y] && out[x] >= out[y];
 75     }
 76     node check(node a, int y)
 77     {
 78         if (a.u == -1 || y == -1) return node(-1, -1, -1);
 79         if (!y) return a;
 80         if (!a.u) return node(y, y, y);
 81         if (!anc(a.u, a.v)) swap(a.u, a.v);
 82         if (anc(a.u, a.v))
 83         {
 84             if (anc(a.u, y))
 85             {
 86                 int p = ST::query(y, a.v);
 87                 if (p == y)
 88                     return a; 
 89                 else if (p == a.u) 
 90                     return node(a.v, y, a.u);
 91                 else if (p == a.v)
 92                     return node(a.u, y, a.u); 
 93                 else
 94                     return node(-1, -1, -1);
 95             }
 96             else if (anc(y, a.u))
 97                 return node(y, a.v, y);
 98             else
 99             {
100                 int p = ST::query(a.v, y);
101                 return node(a.v, y, p);
102             }
103         }
104         else if (anc(a.p, y))
105         {
106             if (anc(a.u, y))
107                 return node(y, a.v, a.p);
108             else if (anc(a.v, y))
109                 return node(a.u, y, a.p);
110             else if (anc(y, a.u) || anc(y, a.v))
111                 return a;
112             else 
113                 return node(-1, -1, -1);
114         }
115         else
116             return node(-1, -1, -1); 
117     }
118     node merge(node a, node b)
119     {
120         a = check(a, b.u);
121         a = check(a, b.v);
122         return a;
123     }
124     void update(int id, int l, int r, int pos, int v)
125     {
126         if (l == r)
127         {
128             a[id] = node(v, v, v);   
129             return;
130         }
131         int mid = (l + r) >> 1;
132         if (pos <= mid) update(id << 1, l, mid, pos, v);
133         else update(id << 1 | 1, mid + 1, r, pos, v);
134         a[id] = merge(a[id << 1], a[id << 1 | 1]);
135     //    printf("%d %d %d %d %d %d
", l, r, a[id].t, a[id].u, a[id].v, a[id].p);
136     //    printf("%d %d %d %d %d %d
", l, mid, a[id << 1].t, a[id << 1].u, a[id << 1].v, a[id << 1].p);
137     //    printf("%d %d %d %d %d %d
", mid + 1, r, a[id << 1 | 1].t, a[id << 1 | 1].u, a[id << 1 | 1].v, a[id << 1 | 1].p);
138     //    puts("*************************************");
139     }
140     bool query(int id, int l, int r)
141     {
142         node tmp = merge(res, a[id]);
143     //    printf("bug %d %d %d %d %d
", l, r, a[id].u, a[id].v, a[id].p);
144     //    printf("bug %d %d %d %d %d
", l, r, res.u, res.v, res.p);
145     //    printf("bug %d %d %d %d %d
", l, r, tmp.u, tmp.v, tmp.p);
146     //    puts("**********************");
147         if (tmp.u != -1) 
148         {
149             res = tmp;
150             ans = r;
151             return 1;
152         }
153         if (l == r) return 0;
154         int mid = (l + r) >> 1;
155         if (query(id << 1, l, mid))
156             query(id << 1 | 1, mid + 1, r);
157         return 0;
158     }
159 }
160 
161 int main()
162 {
163     while (scanf("%d", &n) != EOF) 
164     {
165         for (int i = 1; i <= n; ++i) G[i].clear();
166         for (int i = 1; i <= n; ++i) scanf("%d", p + i), p[i] += 1;
167         for (int v = 2, u; v <= n; ++v)
168         {
169             scanf("%d", &u);
170             G[u].push_back(v);
171             G[v].push_back(u);
172         }
173         ST::init(1, n);
174         SEG::init();
175         for (int i = 1; i <= n; ++i) 
176         {
177             //printf("%d %d
", p[i], i);
178             SEG::update(1, 1, n, p[i], i); 
179         }
180         scanf("%d", &q);
181         for (int i = 1, op, x, y; i <= q; ++i)
182         {
183             scanf("%d", &op);
184             if (op == 1)
185             {
186                 scanf("%d%d", &x, &y);
187                 swap(p[x], p[y]);
188                 SEG::update(1, 1, n, p[x], x);
189                 SEG::update(1, 1, n, p[y], y);
190             }
191             else
192             {
193                 //for (int i = 1; i <= n; ++i) printf("%d%c", p[i], " 
"[i == n]);
194                 SEG::res.init(); SEG::ans = 1;
195                 SEG::query(1, 1, n);
196                 printf("%d
", SEG::ans);
197             }
198         }
199     }
200     return 0;
201 }

View Code