您的位置: 首页 > IT文章 > Codeforces Round #525 (Div. 2) Solution

Codeforces Round #525 (Div. 2) Solution

分类: IT文章 • 2022-05-16 11:11:09

A. Ehab and another construction problem

Water.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int x;
 5 
 6 int main()
 7 {
 8     while (scanf("%d", &x) != EOF)
 9     {
10         int a = -1, b = -1;
11         for (int i = 1; i <= x && a == -1 && b == -1; ++i)
12         {
13             for (int j = i; j <= x; ++j)
14             {
15                 if (j % i == 0 && i * j > x && j / i < x)
16                 {
17                     a = j, b = i;
18                     break;
19                 }
20             }    
21         }
22         if (a == -1) puts("-1");
23         else printf("%d %d
", a, b);
24     }
25     return 0;
26 }

View Code

B. Ehab and subtraction

Water.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 int n, k;
 6 
 7 int main()
 8 {
 9     while (scanf("%d%d", &n, &k) != EOF)
10     {
11         priority_queue <int, vector <int>, greater <int> > q;
12         for (int i = 1, x; i <= n; ++i)
13         {
14             scanf("%d", &x);
15             if (x) q.push(x);
16         }
17         int add = 0;
18         for (int kk = 1; kk <= k; ++kk)
19         {
20             while (!q.empty() && q.top() == add) q.pop();     
21             if (q.empty()) puts("0");
22             else
23             {
24                 int top = q.top(); q.pop();
25                 top -= add;
26                 add += top;
27                 printf("%d
", top);
28             }
29         }
30     }
31     return 0;
32 }

View Code

C. Ehab and a 2-operation task

Solved.

题意：

有两种操作

$将前j个数全都加上x$

$将前j个数全都mod x$

要求用不超过$n + 1 次操作，使得给定序列变成严格的上升序列$

思路：

先全部加上一个较大的数$D$

然后每一次模一个数$D + a_i - i之后使得a_i 变成 i, 并且这样可以保证D + a_i - i > i - 1 只要D足够大$

那么前面已经弄好的数不会受到影响

操作数刚好$n + 1$

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

View Code

D. Ehab and another another xor problem

Upsolved.

题意：

交互题。

要求猜两个数 $(a, b)$

每次可以给出询问$c, d$

根据$a oplus c 和 b oplus d 的大小关系给出1 0 -1 三种状态$

要求根据这些关系得出$(a, b)，询问次数<= 62$

思路：

此处我们约定$(x, y) 表示给出询问(? x y)$

先考虑$a == b 的情况，那么我们只需要每一次按位给出询问$

$此处约定i 表示第i位，给出询问 (1 << i, 0) 根据所给结果即可判断当前位为0还是1$

注意到对于两个数$a, b 根据二进制拆分之后，如果它们最高位所在位置不同$

那么谁的最高位高谁就更大

$那么我们从高位往低位确定，用aa, bb 表示a, b 中高位已经确定的数$

我们用$zero 表示 a 和 b 的大小关系，这个可以通过给出询问(0, 0) 得到$

$这样就可以每一次消除前面高位影响，判断当前位是否相同，或者大小关系$

$注意到如果当前位相同（即当前状态和zero状态相同），那么对于下面的低位, zero 的状态是不会变的$

$那么我们再给出询问(1 <<i , 0)即可知道当前位的大小$

$否则，如果当前位不同，根据当前的状态和zero 状态的比较也可以知道当前位二者是1还是0$

$如果当前状态和zero不同，那么如果当前状态是1，那么a = 0, b = 1 (此处指当前位)$

$反之同理，此处指a和b的当前位$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a, b, st, zero;
 4 int d = (1 << 30) - 1;
 5 
 6 int main()
 7 {
 8     a = 0, b = 0;
 9     puts("? 0 0");
10     fflush(stdout);
11     scanf("%d", &zero);
12     for (int i = 29; i >= 0; --i) 
13     {
14         if (zero == 0)
15         {
16             printf("? %d %d
", a | (1 << i), b);
17             fflush(stdout);
18             scanf("%d", &st);
19             if (st == -1) a |= 1 << i, b |= 1 << i;      
20         }
21         else
22         {
23             printf("? %d %d
", a | (1 << i), b | (1 << i));   
24             fflush(stdout);
25             scanf("%d", &st); 
26             if (st == zero)
27             {
28                 printf("? %d %d
", a | (1 << i), b);
29                 fflush(stdout);
30                 scanf("%d", &st);
31                 if (st == -1) a |= 1 << i, b |= 1 << i;   
32             }
33             else
34             {
35                 if (st == 1) b |= 1 << i; 
36                 else a |= 1 << i;
37                 printf("? %d %d
", a, b);
38                 fflush(stdout);
39                 scanf("%d", &zero);
40             }
41         }
42     }
43     printf("! %d %d
", a, b); 
44     fflush(stdout);
45 }

View Code

E. Ehab and a component choosing problem

Upsolved.

题意：

找出$k个连通块，将所有元素放进s(set)中，求frac{sum_{u in s} a_u}{k}最大$

$如果有多解，要让k也更大$

思路：

注意到$max(a_1, a_2, a_3..) >= average(a_1, a_2, a_3) 当且仅当a_1 == a_2, a_1 == a_3.. 的情况下等号成立$

那么显然每个连通块中的$sum a_u 是相同的$

$dp求解即可$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 300010
 6 int n, a[N];
 7 vector <int> G[N];
 8 ll dp[N], ans = -0x3f3f3f3f3f3f3f3f, k;
 9 
10 void DFS(int u, int fa, int p)
11 {
12     dp[u] = a[u];
13     for (auto v : G[u]) if (v != fa)
14     {
15         DFS(v, u, p);
16         dp[u] += max(dp[v], 0ll);
17     }
18     if (p) 
19         ans = max(ans, dp[u]);
20     else if (dp[u] == ans)
21     {
22         dp[u] = 0;
23         ++k;    
24     }
25 }
26 
27 int main()
28 {
29     while (scanf("%d", &n) != EOF)
30     {
31         for (int i = 1; i <= n; ++i) G[i].clear();
32         for (int i = 1; i <= n; ++i) scanf("%d", a + i);
33         for (int i = 1, u, v; i < n; ++i)
34         {
35             scanf("%d%d", &u, &v);
36             G[u].push_back(v);
37             G[v].push_back(u);
38         }
39         DFS(1, 0, 1);
40         DFS(1, 0, 0);
41         printf("%lld %lld
", ans * k, k);
42     }
43     return 0;
44 }

View Code

F. Ehab and a weird weight formula

Upsolved.

题意：

给出一棵树，要求构造一棵树使得

$deg_u cdot a_u add to w$

$lceil log_2(dist(u, v)) ceil cdot min(a_u, a_v) 对于每个edge(u, v) 都加起来$

$dist(u, v) 指的是原数中两点之间的简单路径$

给出的原树有一个限制就是，对于每个$a_u, 最小值的唯一的$

并且对于每一个非最小值的$a_u, 都至少有一个邻居使得a_v < a_u$

思路：

如果将最小的$a_u作为根，那么往下走，a_u 是递增的$

证明：

假如存在某一个点$a_u < a_{fa[u]}$

那么对于这个点，肯定有一个儿子使得$a_u > a_{son[u]}$

那么这个儿子也同理，直到最后一个叶子结点便不满足

因为$lceil log_2(dist(u, v)) ceil 这个式子的特性，所以在一定范围内的 dist(u, v) 这个值是相同的$

$那么我们肯定选取最小的那个来乘，因为祖先们都是比自己小$

$而且，我们肯定选取较短路径往上爬，倍增找祖先即可$

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

View Code

Codeforces Round #525 (Div. 2) Solution

相关推荐