Educational Codeforces Round 54 (Rated for Div. 2) Solution

solved

题意：给出一个字符串，可以移掉最多一个字符，在所有可能性中选取一个字典序最小的。

思路：显然，一定可以移掉一个字符，如果移掉的字符的后一个字符大于当前字符，那么字典序会变大。

那只需要从左往右，遇到第一个后面的字符大于当前字符的就可以移掉该字符。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 200010
 5 int n;
 6 char s[N];
 7 
 8 int main()
 9 {
10     while (scanf("%d%s", &n, s + 1) != EOF)
11     {
12         int pos = n;
13         for (int i = 1; i < n; ++i) if (s[i + 1] < s[i])
14         {
15             pos = i;
16             break;  
17         }
18         s[pos] = 0;
19         printf("%s", s + 1);
20         printf("%s
", s + pos + 1);
21     }
22     return 0;
23 }

View Code

B - Divisor Subtraction

solved

题意：给出一个数n，如果n = 0,那么程序就结束。否则减去这个数的最小质因子，再循环执行该算法，问程序会执行多少步。

思路：

我们假设数$n的最小质因子为x, 令 y = frac{n}{x}$

如果$y$是偶数，那么答案就很明显，直接不断减去2

如果$y是奇数，那么我们先减去一个x，那么就会变成 n = (y - 1) cdot x$

$此时 (y - 1) 显然为偶数就不断减去2就可以$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 ll x;
 6 
 7 ll find(ll x)
 8 {
 9     ll limit = sqrt(x + 1); 
10     for (ll i = 2; i <= limit; ++i) if (x % i == 0) return i; 
11     return x;
12 }
13 
14 int main()
15 {
16     while (scanf("%lld", &x) != EOF)
17     {
18         ll y = find(x); ll z = x / y;
19         printf("%lld
", (z - 1) * y / 2 + 1);    
20     }
21     return 0;
22 }

View Code

C - Meme Problem

solved

题意：给出一个$d, 找a + b = d and a cdot b = d$

思路：将$a = d - b$ 代入第二个式子，解二元一次方程。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int t, d;
 5 
 6 int main()
 7 {
 8     scanf("%d", &t);
 9     while (t--)
10     {
11         scanf("%d", &d);
12         if (d * d < 4 * d) puts("N");
13         else
14         {
15             double delta = sqrt(d * d - 4 * d);
16             double b = (d - delta) / 2;
17             double a = d - b;
18             printf("Y %.10f %.10f
", a, b);
19         }
20     }
21     return 0;
22 }

View Code

D - Edge Deletion

Upsolved

题意：给出一个无向图，定义$d_i为 1 - i 的最短路径$，定义一个点为好点为1 - 这个点的最短路径为 $d_i$，最多保留k条边，使得剩下的点中好点最多。

思路：Dijkstra构造最短路树，对最短路树DFS或者BFS皆可，按这个搜索顺序选取边，显然每选取一条边都会增加一个好点，所以最后好点的数量显然为$min(k + 1, n)$

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define ll long long
  5 #define INFLL 0x3f3f3f3f3f3f3f3f
  6 #define N 300010
  7 int n, m, k;
  8 
  9 struct Edge
 10 {
 11     int u, v; ll w; 
 12     Edge() {}
 13     Edge(int u, int v, ll w) : u(u), v(v), w(w) {}  
 14 }edge[N]; 
 15 
 16 struct graph
 17 {
 18     struct node
 19     {
 20         int to, nx, id; ll w;
 21         node () {}
 22         node (int to, int nx, int id, ll w) : to(to), nx(nx), id(id), w(w) {}
 23     }a[N << 1];
 24     int head[N], pos;
 25     void init() { memset(head, 0, sizeof head); pos = 0; } 
 26     void add(int u, int v, int id, ll w)
 27     {
 28         a[++pos] = node(v, head[u], id, w); head[u] = pos;
 29         a[++pos] = node(u, head[v], id, w); head[v] = pos;
 30     }
 31 }G, g;  
 32 #define erp(G, u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w)
 33 
 34 struct Dijkstra
 35 {
 36     struct node
 37     {
 38         int to; ll w;
 39         node () {}
 40         node (int to, ll w) : to(to), w(w) {}
 41         bool operator < (const node &r) const { return w > r.w; } 
 42     };
 43     struct DIST 
 44     {
 45         ll w; int id;
 46         DIST() {}
 47         DIST(ll w, int id) : w(w), id(id) {}
 48     }dist[N]; bool used[N]; 
 49     void solve() 
 50     {
 51         for (int i = 1; i <= n; ++i)
 52         {
 53             dist[i] = DIST(INFLL, -1); 
 54             used[i] = false; 
 55         }
 56         dist[1] = DIST(0, -1); 
 57         priority_queue <node> q; q.emplace(1, 0);
 58         while (!q.empty())
 59         {
 60             int u = q.top().to; q.pop();
 61             if (used[u]) continue;
 62             used[u] = 1; 
 63             int id = dist[u].id; if (id != -1) g.add(edge[id].u, edge[id].v, id, edge[id].w); 
 64             erp(G, u) if (!used[v] && dist[v].w > dist[u].w + w) 
 65             {
 66                 dist[v].w = dist[u].w + w; 
 67                 dist[v].id = G.a[it].id;
 68                 q.emplace(v, dist[v].w);
 69             }
 70         }
 71     }
 72 }dij;
 73 
 74 vector <int> res;
 75 void DFS(int u, int fa)
 76 {
 77     erp(g, u) if (v != fa && res.size() < k)
 78     {
 79         res.push_back(g.a[it].id); 
 80         DFS(v, u);
 81     }
 82 }
 83 
 84 int main()
 85 {
 86     while (scanf("%d%d%d", &n, &m, &k) != EOF)
 87     {
 88         G.init(); g.init(); res.clear();
 89         for (int i = 1, u, v, w; i <= m; ++i)
 90         {
 91             scanf("%d%d%d", &u, &v, &w);
 92             edge[i] = Edge(u, v, w);
 93             G.add(u, v, i, w);
 94         } dij.solve(); DFS(1, 1); 
 95         int len = res.size(); 
 96         printf("%d
", len);
 97         for (int i = 0; i < len; ++i) printf("%d%c", res[i], " 
"[i == len - 1]);
 98     }
 99     return 0;
100 }

View Code

E - Vasya and a Tree

solved

题意：给出一棵树，有m次操作，每次将以x为根的子树下，和x的距离不超过d的所有点的权值都加上v,最后输出每个点的权值。

思路：首先考虑$d$特别大的情况下，也就是子树下所有点都要加上，那么更新的时候直接在那个点上更新，

最后只需要DFS一遍，每个点都加上父亲的权值即可。

再考虑加入限制的情况：

其实对于一个点，我们DFS下去的时候，到回溯上来这段时间，遍历的都是它的子树，那么我们可以设立一个标记

对于每个点，给他加上更新的权值的时候，我们在对应的子树的deep界限那里加上，那么每次遍历下去的时候，首先要减去这个当前深度对应的lazy值，然后再更新答案，回溯上来的时候取消标记即可。

 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, m;
 8 vector <int> G[N]; 
 9 vector <pii> vec[N];
10 ll ans[N], gap[N];
11 
12 int deep[N], fa[N];
13 void DFS(int u, ll res)
14 {
15     res -= gap[deep[u]];
16     for (auto it : vec[u]) 
17     {
18         int dep = min(deep[u] + it.first + 1, n + 1);
19         gap[dep] += it.second;  
20         res += it.second;
21     }
22     ans[u] = res;
23     for (auto v : G[u]) if (v != fa[u])
24     {
25         fa[v] = u;
26         deep[v] = deep[u] + 1;
27         DFS(v, res); 
28     }
29     for (auto it : vec[u])
30     {
31         int dep = min(deep[u] + it.first + 1, n + 1);
32         gap[dep] -= it.second;
33         res -= it.second;
34     }
35     res += gap[deep[u]];
36 }
37     
38 void init()
39 {
40     for (int i = 1; i <= n; ++i)
41     {
42         G[i].clear();
43         vec[i].clear();
44     }
45     memset(gap, 0, sizeof gap);
46     deep[1] = 0; 
47 }
48 
49 int main()
50 {
51     while (scanf("%d", &n) != EOF)
52     {
53         init(); 
54         for (int i = 1, u, v; i < n; ++i)
55         {
56             scanf("%d%d", &u, &v);
57             G[u].push_back(v);
58             G[v].push_back(u);
59         }
60         scanf("%d", &m);
61         for (int i = 1, x, d, v; i <= m; ++i)
62         {
63             scanf("%d%d%d", &x, &d, &v);
64             vec[x].emplace_back(min(d, n), v); 
65         }
66         DFS(1, 0);
67         for (int i = 1; i <= n; ++i) printf("%lld%c", ans[i], " 
"[i == n]);
68     }
69     return 0; 
70 }

View Code

F. Summer Practice Report

Upsolved.

题意：

$第i天有x_i个糖果，y_i个果冻，要求将他们放在一排，且相同的东西连续最多放k个，要放n天，求是否有放置方案满足$

思路：

$dp[i][1/0] 表示第i天最后一部分放糖果还是果冻的最小数量，然后枚举四种状态DP转移即可。$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define INF 0x3f3f3f3f
 6 #define N 300010
 7 int n, k, x[N], y[N], dp[N][2]; 
 8 
 9 int calc(int pa, int pb, int a, int b)
10 {
11     int ans = INF;
12     if (pa <= k)
13     {
14         int tot = pa + a;
15         int cnt = (tot + k - 1) / k - 1;
16         if (b == cnt) ans = min(ans, tot - cnt * k);    
17         else if (b > cnt && b <= (ll)a * k) ans = min(ans, 1);
18     }
19     if (pb <= k)
20     {
21         int cnt = (a + k - 1) / k - 1;
22         if (b == cnt) ans = min(ans, a - cnt * k);
23         else if (b > cnt && b <= (ll)a * k - pb) ans = min(ans, 1);
24     }
25     return ans;
26 }    
27 
28 bool solve()
29 {
30     memset(dp, 0x3f, sizeof dp); dp[0][0] = dp[0][1] = 0;
31     for (int i = 1; i <= n; ++i)
32     {
33         dp[i][0] = calc(dp[i - 1][0], dp[i - 1][1], x[i], y[i]);
34         dp[i][1] = calc(dp[i - 1][1], dp[i - 1][0], y[i], x[i]);
35         if (dp[i][0] == INF && dp[i][1] == INF) return false;
36     }
37     return true;
38 }
39 
40 int main()
41 {
42     while (scanf("%d%d", &n, &k) != EOF)
43     {
44         for (int i = 1; i <= n; ++i) scanf("%d", x + i);
45         for (int i = 1; i <= n; ++i) scanf("%d", y + i);
46         puts(solve() ? "YES" : "NO");
47     }
48     return 0;
49 }

View Code

G. Array Game

Unsolved.