Codeforces Round #384 (Div. 2) WriteUp

Veröffentlicht am   |  

概览

一共5道题，历时2个小时，一共做出两道题，再加上总司翻车，真是不幸的一天（垃圾游戏，毁我青春)。

743A Vladik and flights

从这道题就能看出这套题的整体风格了，就是取巧。。。题目中有两种机场，那么我们知道当两个地方的机场属于同一个公司时，花费是0.那么我们只需要考虑不是同一个公司的情况。当不是同一个公司时，花费的下界是1。而采用一种策略，那么上界也是1。也就是当不属于同一个公司时，花费为1。策略就是，如果不在同一个公司，那么就朝着目标方向迁移，直到遇到目的地一样的公司或者到达目的地。哈。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    if (s[a-1] == s[b-1])
        cout << 0;
    else
        cout << 1;
    return 0;
}

743B Chloe and the sequence

仔细观察生成的序列，发现是对称的（废话），那么自然想到折半的方法，中心点就是每次新加入的数。那么什么时候停止呢。我们发现，位置是二的幂次的数我们是能确认他的值的，他的值就是幂次加1。比如4所在位置就是8，也即2的三次方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    long long n, k;
    cin >> n >> k;
    long long ans = 1;
    while (n--)
    {
        if(k > pow(2, n))
            k = pow(2,n)*2 - k;
        if (k == pow(2, n))
        {
            ans = n+1;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

提交了三次才过，被自己蠢哭。

743C Vladik and fractions

一道数论题？开始想了一些可能，也想到因数分解什么的，后来发现我想多了。
$$ \frac2n = \frac1n + \frac1n$$
首先可以像上面这样分解一次，我们就找到了第一个数（n)，接下来就是考虑怎么把$\frac1n$分解开了。
$$ \frac1n = \frac1{n+1} + \frac1{n(n+1)}$$
所以我们只需要输出,n 、n+1和n(n+1)就可以了。
桥豆麻袋。有一种情况无法分解，那就是n为1的情况。因为这么分解能得到的最大值为$ 1+\frac12+\frac13 = \frac53 < 2$。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    if (n == 1)
        cout << -1 << endl;
    else
        cout << n << " " << n+1 << " " << n*(n+1) << endl;
    return 0;
}

这一定是A题吧。吧？

743D Chloe and pleasant prizes

图论加DP。
我们先来考虑不可能的情况。无法得到一种分配方案，当且仅当树没有分支的时候。因为只要有分支，我们总可以取这两个分支。这里维护两个数组。一个保存每个节点及其所有子节点的分数和，另个数组保存每个节点的子树中的最大分数。做一次DFS，每次找出节点的所有子树种分数最大的两个，如果找不出两个，则说明不存在合法的分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
typedef  long long ll;
const ll inf=1LL<<60;
#define fi first
#define sec second
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define vp vector<pair<int, int> >
#define FF fflush(stdout);
ll a[200001], m[200001], sums[200001];
ll ans = -inf;
vector<ll> g[200001];
void dfs(ll r, ll pa)
{
    sums[r] = a[r];
    ll m1 = -inf, m2 = -inf;
    for (int i = 0;i < g[r].size();i++)
    {
        ll to = g[r][i];
        if (to == pa)
            continue;
        dfs(to , r);
        sums[r] += sums[to];
        ll x = m[to];
        if (x > m1) swap(x, m1);
        if (x > m2) swap(x, m2);
    }
    if (m1 != -inf && m2 != -inf)
        ans = max(ans, m1+m2);
    m[r] = (sums[r] > m1) ? sums[r] : m1;
}
int main()
{
    int n;
    ios::sync_with_stdio(false);cin.tie(false);
    cin >> n;
    for (ll i = 1;i <= n;i++)
        cin >> a[i];
    for (ll i = 1;i < n;i++)
    {
        ll x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1, 0);
    if (ans > -inf)
        cout << ans << endl;
    else
        cout << "Impossible" << endl;
    return 0;
}

参考答案是做两趟DFS，但其实只需要一趟。

总结

分数下降到了1389T_T，还是太菜。这次题目的代码量都比较小，只要想清楚了解法，都能很快写出代码。所以主要还在于思考，也没有用到复杂的数据结构和算法。还是太菜了。。。