首页 > 代码库 > Codeforces Round #384 (Div. 2)

Codeforces Round #384 (Div. 2)

2024-08-27 07:24:44   238人阅读

A. Vladik and flights（water）

题意：从a位置到b位置去, 问最短花费 想通了就是大水题

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int maxn = 100000 + 5;
 5 char s[maxn];
 6 int main()
 7 {
 8     int n, a, b;
 9     scanf("%d%d%d", &n, &a, &b);
10     scanf("%s", s + 1);
11     if(s[a] == s[b])
12         puts("0");
13     else
14         puts("1");
15     return 0;
16 }
View Code

 

B. Chloe and the sequence （构造？）

题意：给出n和k, 按照它的规则构成一串数字，问第k个是哪个数字

思路：我的做法是用递归，根据构造规则反向求出解。

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned long long uLL;
 4 typedef long long LL;
 5 const int INF = 0x3f3f3f3f;
 6 const int maxn = 10000 + 5;
 7 int ok;
 8 void solve(uLL n, uLL k)
 9 {
10     if(n < 1) return;
11     uLL mid = (( (uLL) 1 << n) + 1) / 2;
12     if(k == mid)
13     {
14         cout << n << endl;
15         ok = 1;
16     }
17     else if(k < mid)
18     {
19         solve(n - 1, k);
20     }
21     else if(k > (n + 1) / 2)
22     {
23         solve(n - 1, k - mid);
24     }
25 }
26 
27 int main()
28 {
29     uLL n, k;
30     cin >> n >> k;
31     solve(n, k);
32     return 0;
33 }
View Code

 

C. Vladik and fractions （构造）

题意：已知n, 问是否存在整数x, y, z使得 2/n = 1/x + 1/y + 1/z 成立。

思路：应该算是一个构造吧，直接推公式秒了。

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int INF = 0x3f3f3f3f;
 5 const int maxn = 10000 + 5;
 6 
 7 int main()
 8 {
 9     int n;
10     int ok = 0;
11     scanf("%d", &n);
12     if(n == 1)
13     {
14         puts("-1");
15     }
16     else
17     {
18         cout << n << " " << n + 1 << " " << n*(n +1) << endl;
19     }
20     
21     return 0;
22 }
View Code

 

D. Chloe and pleasant prizes（树dp）

题意：大概就是一颗树上面，选两棵不相交子树使得点权和最大

思路：树dp入门题。注意！！！初始化！！！vmax的初始化是-INF，因为你要选一个子树，而不是选择其中某些点。

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 200000 + 5;
 5 const LL INF = 0x3f3f3f3f3f3f3f3f;
 6 int a[maxn];
 7 LL ans;
 8 vector<int>G[maxn];
 9 LL sum[maxn], val_max[maxn];
10 
11 void dfs(int cur, int fa)
12 {
13     sum[cur] = a[cur];
14     val_max[cur] = -INF;
15     vector<LL>temp;
16     for(auto to : G[cur])
17     {
18         if(to == fa) continue;
19         dfs(to, cur);
20         val_max[cur] = max(val_max[cur], val_max[to]);
21         sum[cur] += sum[to];
22         temp.push_back(val_max[to]);
23 
24     }
25     sort(temp.begin(), temp.end(), greater<LL>());
26     if(temp.size() >= 2)
27     {
28         ans = max(ans, temp[0] + temp[1]);
29     }
30     val_max[cur] = max(val_max[cur], sum[cur]);
31 
32 }
33 
34 int main()
35 {
36     int n;
37     scanf("%d", &n);
38     for(int i = 1; i <= n; i++)
39     {
40         scanf("%d", &a[i]);
41     }
42     for(int i = 0; i < n - 1; i++)
43     {
44         int u, v;
45         scanf("%d%d", &u, &v);
46         G[u].push_back(v);
47         G[v].push_back(u);
48     }
49 
50     ans = -1LL << 63;
51     dfs(1, 0);
52 
53     if(ans == -1LL << 63)
54         puts("Impossible");
55     else
56         cout << ans << endl;
57     return 0;
58 }
View Code

 

Codeforces Round #384 (Div. 2)


联系
我们