Codeforces Round 1087 (Div. 2)

Posted on Edited on

Codeforces Round 1087 (Div. 2)

A. Flip Flops

Solution

显然从最弱的开始打，不容易死。只要不死，就使劲丢flip-flop，提升战斗力。

Code

Show Code 
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
signed main() {
    int t; io >> t;
    while (t--) {
        int n;
        LL c, k;
        io >> n >> c >> k;
        std::vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            io >> a[i];
        }
        std::sort(a.begin() + 1, a.end());
        for (int i = 1; i <= n; ++i) {
            if (c < a[i]) {
                break;
            }
            LL now = a[i];
            if (k >= c - a[i]) now = c, k -= (c - a[i]);
            else now = a[i] + k, k = 0;
            c += now;
        }
        io << c << '\n';

    }
    return 0;
}

B. Array

Solution

题意是，对于每个下标ii，找到一个kk，使得j>i,∣ai−k∣>∣aj−k∣j > i, \left|a_i - k\right| > \left|a_j - k\right|的jj个数最多，输出这个最多的个数。

∣ai−k∣\left|a_i - k\right|等价于aia_i到kk的距离。如果k<aik<a_i，则所有的aj>aia_j>a_i到kk的距离都比aia_i大，反之亦然，所以说最大的数量就是满足j>i,aj>aij>i, a_j>a_i和j<i,aj<aij<i, a_j<a_i的数量中较多的那一个。

nn比较小，O(n2)O(n^2)暴力计算即可。倒着遍历加一个树状数组可以做到O(nlog⁡n)O(n\log n)。

Code

Show Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
signed main() {
    int t; io >> t;
    while (t--) {
        int n; io >> n;
        std::vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            io >> a[i];
        }
        std::vector<int> ans;
        for (int i = 1; i <= n; ++i) {
            int lo = 0, hi = 0;
            for (int j = i + 1; j <= n; ++j) {
                if (a[j] > a[i]) hi++;
                else if (a[j] < a[i]) lo++;
            }
            ans.push_back(std::max(lo, hi));
        }
        for (auto x : ans) {
            io << x << ' ';
        }
        io << '\n';
    }
    return 0;
}

C. Find the Zero

Solution

有趣的小题。

首先，可以发现，只要评测机告诉你一次11，答案就是你问的两个中随便一个。

由于只有n+1n+1次询问，所以有两个思考的方向：

  1. 全部询问都和某一个aia_i相关。但是只要aia_i是一个非00的就等于只得到了ai≠0a_i\neq 0一个信息，肯定不够。
  2. 两两组成一对来问。

现在分析第二种：

  • 我们先花nn次询问两两全部问好（第ii个和第i+ni+n个绑定，且评测机报了nn个00），那么我们就知道，每两个之间有一个00和一个非00；
  • 现在我们选择第nn个和第11个，以及第nn个和第n+1n + 1个做两次询问。如果报的是两个00，那么第nn个一定不是00，报告答案为2n2n；否则输出nn即可。

这样就获得了一个n+2n+2的方法。但是题目要求n+1n+1，可以尝试优化。

现在我们现不问(n,2n)(n, 2n)，保持询问(n,1)(n, 1)和(n,n+1)(n, n+1)，则

  • 由于前面n−1n-1次询问都是00，所以我们可以确定，nn和2n2n中一定有一个00，否则前面应当有11；
  • 如果(n,1)(n,1)和(n,n+1)(n, n+1)都是00，那么1. 如果nn是00，那么11和n+1n+1都不是00，则2n2n一定是00；2. 如果nn不是00，那么2n2n一定是00。所以不管怎样2n2n都是00，直接报告2n2n即可。

这样就得到了n+1n+1次的方法。

Code

Show Code 
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
signed main() {
    int t; std::cin >> t;
    while (t--) {
        int n; std::cin >> n;
        bool flag = 0;
        for (int i = 1; i <= n - 1; ++i) {
            std::cout << "? " << i << ' ' << i + n << std::endl;
            std::cout.flush();
            int op; std::cin >> op;
            if (op == 1) {
                std::cout << "! " << i << std::endl;
                std::cout.flush();
                flag = 1;
                break;
            }
        }
        if (flag) continue;
        std::cout << "? " << n << ' ' << 1 << std::endl;
        std::cout.flush();
        int op; std::cin >> op;
        if (op == 1) {
            std::cout << "! " << n << std::endl;
            std::cout.flush();
            flag = 1;
            continue;
        }
        std::cout << "? " << n << ' ' << n + 1 << std::endl;
        std::cout.flush();
        std::cin >> op;
        if (op == 1) {
            std::cout << "! " << n << std::endl;
            std::cout.flush();
            flag = 1;
            continue;
        }
        std::cout << "! " << n * 2 << std::endl;
        std::cout.flush();
    }
    return 0;
}

D. Ghostfires

Solution

按照r,g,br,g,b中00的数量分情况考虑：

  1. 只有一个不为00：最多再放一个；
  2. 只有两个不为00：两个交替放，直到回到情况11；
  3. 三个都不为00，则有两种情况：
    a. 如果三个数量相同，则类似RGB|GBR|BRG|...轮换放，可以全部放完（第一个RGB一定有办法放出，可见后续证明）；
    b. 如果三个数量不完全相同，每次放较多的两个直到三者相同，或者回到情况2。如果只有最多的多一个，先放一个最多的，然后回到三者相同的情况。

现在证明三个相同时，一定有合法的放法：

设当前字符串为ss。不失一般性，

  1. 假设ss的最后三个字母是RGB（如果∣s∣<3\left|s\right| < 3，补到三个，后续去掉不会影响结论），那么加上GBR即可；
  2. 假设最后三个字母是RGR（如果∣s∣<3\left|s\right| < 3，补到三个，后续去掉不会影响结论），则加上GRB即可。

所以不管ss之前怎么放，只要到了三者相同的情况，一定能全部放完。

Code

Show Code 
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
struct node {
    int cnt;
    char c;
    int done() const {
        return cnt > 0 ? 1 : 0;
    }
    bool operator < (const node& other) const {
        return cnt < other.cnt;
    }
    bool operator > (const node& other) const {
        return cnt > other.cnt;
    }
    bool operator == (const node& other) const {
        return cnt == other.cnt;
    }
};

node* max(node& a, node& b) {
    return a > b ? &a : &b;
}

std::string nxt(std::string x) {
    return x.substr(1) + x[0];
}

signed main() {
    int t; io >> t;
    while (t--) {
        node a[3];
        io >> a[0].cnt; a[0].c = 'R';
        io >> a[1].cnt; a[1].c = 'G';
        io >> a[2].cnt; a[2].c = 'B';
        std::sort(a, a + 3);
        std::string s;
        auto add = [&](node& x) {
            if (x.cnt > 0 && (!s.empty() || s.back() != x.c)) {
                x.cnt--;
                s += x.c;
            }
        };
        auto judge3 = [&]() {
            for (int i = s.length() - 6; i + 3< int(s.length()); ++i) {
                if (i >= 0) {
                    if (s[i] == s[i + 1] || s[i] == s[i + 3]) {
                        return false;
                    }
                }
            }
            return true;
        };
        auto rep3 = [&]() {
            assert(a[0] == a[1] && a[1] == a[2]);
            std::string ss[6] = {
                "RGB", "RBG",
                "GBR", "GRB",
                "BGR", "BRG"
            };
            std::string sel;
            for (int i = 0; i < 6; ++i) {
                s += ss[i];
                if (!judge3()) {
                    for (int j = 0; j < 3; ++j) {
                        s.pop_back();
                    }
                } else {
                    sel = ss[i];
                    break;
                }
            }
            assert(sel.length());
            for (int i = 0; i < 3; ++i) --a[i].cnt;
            while (a[0].cnt) {
                sel = nxt(sel);
                s += sel;
                for (int i = 0; i < 3; ++i) --a[i].cnt;
            }
        };
        while (a[0].done() + a[1].done() + a[2].done() > 1) {
            // printf("a = %d, %d, %d\n", a[0].cnt, a[1].cnt, a[2].cnt);
            if (a[0] == a[1] && a[1] == a[2]) {
                rep3();
            } else if (a[2] == a[1]) {
                add(a[2]);
                add(a[1]);
            } else if (a[1] == a[0]) {
                add(a[2]);
                add(a[0]);
            } else {
                add(a[2]);
                add(a[1]);
            }
        }
        add(a[0]), add(a[1]), add(a[2]);
        io << s << '\n';
    }
    return 0;
}

E. A Trivial String Problem

Solution

n=1e6,q=1e2n=1e6,q=1e2，看起来O(nq)O(nq)可过。

所以我们直接拆到每一次询问，问题变成：

对于一个长度为nn的字符串ss，求出$$\sum_{i=1}^n f(s[1:i])$$

令f[i]=f(s[1:i])f[i] = f(s[1:i])，假设当前已经求出了f[1],f[2],⋯ ,f[i−1]f[1], f[2], \cdots, f[i - 1]，且假设f[0]=0f[0]=0，假设字符串tt是满足：

  1. ∣t∣=m≤i\left|t\right| = m\leq i；
  2. tt是ss的前缀，也是s[1:i]s[1:i]的后缀；
  3. tt是满足条件1, 2的字符串中最短的一个。

那么我们就可以做更新：$$f[i] = f[i - m] + 1$$

证明：

假设存在一种分割方式，没有在i−m+1i-m+1处做分割，那么这种分割方式的最后一次分割一定在i−m+1i-m+1之前（如果在后面就不满足tt的最短性质），所以我们添加一个i−m+1i-m+1的分割，一定是更优的，矛盾。

关键是怎么对于ii，求出这个tt。

回顾KMP，它做的是满足条件1, 2的字符串中，最长的一个。那么我们不停的跳失配指针，直到跳到00之前，获得的应该就是最短的（如果不是最短的，那么不应该跳到00）。

所以，我们记一个数组gg：

g[i]={iif p[i]=0g[p[i]]if p[i]≠0g[i] = \begin{cases} i & \text{if}\, p[i] = 0\\ g[p[i]] & \text{if}\, p[i] \neq 0\\ \end{cases}

这样，g[i]g[i]就代表了ii对应的字符串tt的长度。

所以转移的时候

f[i]=f[i−g[i]]+1f[i] = f[i - g[i]] + 1

Code

Show Code 
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
using it = std::string::iterator;

LL solve(it begin, int len) {
    std::vector<int> f(len + 1, 0);
    std::vector<int> p(len + 1, 0);
    std::vector<int> g(len + 1, 0);
    auto get = [&](int x) {
        if (!x) return ' ';
        return *(begin + x - 1);
    };
    g[1] = 1;
    for (int j = 0, i = 2; i <= len; ++i) {
        while (j && get(j + 1) != get(i)) j = p[j];
        if (get(j + 1) == get(i)) p[i] = ++j;
        g[i] = (p[i] ? g[p[i]] : i);
    }
    LL res = 0;
    for (int i = 1; i <= len; ++i) {
        f[i] = f[i - g[i]] + 1;
        res += f[i];
    }
    return res;
}

signed main() {
    std::ios::sync_with_stdio(false); std::cin.tie(0), std::cout.tie(0);
    int t; std::cin >> t;
    while (t--) {
        int n, q; std::cin >> n >> q;
        std::string a; std::cin >> a;
        a = ' ' + a;
        while (q--) {
            int l, r; std::cin >> l >> r;
            std::cout << solve(a.begin() + l, r - l + 1) << std::endl;
        }
    }
    return 0;
}

F. Dynamic Values And Maximum Sum

Solution

最重要的observation：取完第一次后，所有的value都集中在叶子结点，后面再怎么取，value都不会改变。

所以问题转化为：挑选一个跟节点rr，让除了rr以外的所有节点都跑到自己子树中，离自己最远，且编号最小的节点去，然后取前k−1k-1大的value。

对于确定根情况下，每个点会跑到哪个节点去，是可以O(n)O(n)遍历求出来的。所以得到了一个简单的O(n2)O(n^2)办法。

我们不妨先假设11为根节点，求出每个节点会跑到的节点。然后开始换根，每次根从uu换到vv的时候，只需要将uu要到的节点改为vv子树外离uu最远的节点（这个可以通过上面传下来的+uu子树内但非vv子树内的部分合并求解）。

同时维护两个multiset：hihi里面放较多的k−1k-1个value，lolo里面放较少的n−k+1n-k+1个value。每次换根的时候，从hihi或者lolo里面重新erase再insert一下，然后维护一下hihi比lolo大的性质，这一部分是O(log⁡n)O(\log n)的。再维护一个sumsum，在hihi和lolo变动时，sumsum也同步变动。这样就可以O(nlog⁡n)O(n\log n)求解。

Code

Show Code (nlogn) 
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
using LL = long long;

void Dfs1(
    int u, 
    const std::vector<std::vector<int> >& G, 
    std::vector<int>& dep,
    std::vector<int>& down
) {
    int maxk = u;
    for (int v : G[u]) {
        if (!dep[v]) {
            dep[v] = dep[u] + 1;
            Dfs1(v, G, dep, down);
            if (dep[down[v]] > dep[maxk] || (dep[down[v]] == dep[maxk] && maxk > down[v])) {
                maxk = down[v];
            }
        }
    }
    down[u] = maxk;
}

void maintain(
    std::multiset<LL>& hi,
    std::multiset<LL>& lo,
    LL& sum
) {
    while (!hi.empty() && !lo.empty() && (*hi.begin()) < (*(--lo.end()))) {
        LL x = *hi.begin();
        LL y = *lo.rbegin();
        hi.erase(hi.begin());
        lo.erase(--lo.end());
        hi.insert(y);
        lo.insert(x);
        sum += y - x;
    }
}

void replace(
    LL ori,
    LL now,
    std::multiset<LL>& hi,
    std::multiset<LL>& lo,
    LL& sum
) {
    if (ori > (*lo.rbegin())) {
        hi.erase(hi.find(ori));
        hi.insert(now);
        sum += now - ori;
    } else {
        lo.erase(lo.find(ori));
        lo.insert(now);
    }
    maintain(hi, lo, sum);
}

LL Dfs2(
    int u,
    int upk,
    int upv,
    LL& sum,
    const std::vector<std::vector<int> >& G,
    const std::vector<int>& down,
    const std::vector<int>& dep,
    std::multiset<LL>& hi,
    std::multiset<LL>& lo,
    std::vector<LL>& val,
    std::vector<int>& a
) {
    replace(val[down[u]], val[down[u]] - a[u], hi, lo, sum);
    val[down[u]] -= a[u]; // delete itself
    LL res = sum + a[u];
    // printf("u = %d\n", u);
    // for (int i = 1; i < int(val.size()); ++i) {
    //     printf("val[%d] = %lld\n", i, val[i]);
    // }
    int max1 = upk, dis1 = upv;
    int max2 = 0, dis2 = 0;
    for (int v : G[u]) {
        if (dep[v] > dep[u]) {
            int dis = dep[down[v]] - dep[u];
            if (dis > dis1 || (dis == dis1 && down[v] < max1)) {
                max2 = max1, dis2 = dis1;
                max1 = down[v], dis1 = dis;
            } else if (dis > dis2 || (dis == dis2 && down[v] < max2)) {
                max2 = down[v], dis2 = dis;
            }
        }
    }

    for (int v : G[u]) {
        if (dep[v] > dep[u]) {
            if (down[v] != max1) {
                replace(val[max1], val[max1] + a[u], hi, lo, sum);
                val[max1] += a[u]; // switch to up
                res = std::max(res, Dfs2(v, max1, dis1 + 1, sum, G, down, dep, hi, lo, val, a));
                replace(val[max1], val[max1] - a[u], hi, lo, sum);
                val[max1] -= a[u]; // back to down
            } else {
                replace(val[max2], val[max2] + a[u], hi, lo, sum);
                val[max2] += a[u]; // switch to up
                res = std::max(res, Dfs2(v, max2, dis2 + 1, sum, G, down, dep, hi, lo, val, a));
                replace(val[max2], val[max2] - a[u], hi, lo, sum);
                val[max2] -= a[u]; // back to down
            }
        }
    }
    replace(val[down[u]], val[down[u]] + a[u], hi, lo, sum);
    val[down[u]] += a[u]; // add itself
    return res;
}


signed main() {
    int t; io >> t;
    while (t--) {
        int n, k;
        io >> n >> k;
        std::vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            io >> a[i];
        }
        std::vector<std::vector<int> > G(n + 1);
        std::vector<int> dep(n + 1, 0);
        std::vector<int> down(n + 1, 0);
        for (int i = 1; i <= n - 1; ++i) {
            int u, v; io >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        // for (int i = 1; i <= n; ++i) {
        //     std::sort(G[i].begin(), G[i].end());
        // }
        dep[1] = 1;
        Dfs1(1, G, dep, down); // down
        // for (int i = 1; i <= n; ++i) printf("i = %d, down = %d, dep = %d\n", i, down[i], dep[i]);

        std::vector<LL> val(n + 1, 0);
        std::vector<LL> v(n + 1, 0);
        std::multiset<LL> hi;
        std::multiset<LL> lo;
        for (int i = 1; i <= n; ++i) {
            val[down[i]] += a[i];
        }
        for (int i = 1; i <= n; ++i) {
            v[i] = val[i];
        }
        std::sort(v.begin() + 1, v.end());
        LL sum = 0;
        for (int i = n; i >= 1; --i) {
            if (i >= n - (k - 1) + 1) {
                hi.insert(v[i]);
                sum += v[i];
            } else {
                lo.insert(v[i]);
            }
        }
        io << Dfs2(1, 0, 0, sum, G, down, dep, hi, lo, val, a) << '\n';
    }
    return 0;
}/*
1
10 4
7 9 71 48 17 8 37 47 77 85 
2 6
8 2
1 2
4 2
5 6
3 2
7 3
10 3
9 1

*/
Show Code (n^2) 
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
int Dfs1(
    int u,
    int fa,
    const std::vector<std::vector<int> >& G,
    const std::vector<int>& a,
    std::vector<LL>& val,
    std::vector<int>& dep
) {
    dep[u] = dep[fa] + 1;
    int maxk = u;
    for (int v : G[u]) {
        if (v != fa) {
            int nowk = Dfs1(v, u, G, a, val, dep);
            if (dep[nowk] > dep[maxk] || (dep[nowk] == dep[maxk] && nowk < maxk)) {
                maxk = nowk;
            }
        }
    }
    if (fa) val[maxk] += a[u];
    return maxk;
}

signed main() {
    int t; io >> t;
    while (t--) {
        int n, k;
        io >> n >> k;
        std::vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            io >> a[i];
        }
        std::vector<std::vector<int> > G(n + 1);
        for (int i = 1; i <= n - 1; ++i) {
            int u, v; io >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        LL ans = 0;
        for (int i = 1; i <= n; ++i) {
            std::vector<LL> val(n + 1, 0);
            std::vector<int> dep(n + 1, 0);
            Dfs1(i, 0, G, a, val, dep);
            std::sort(val.begin() + 1, val.end());
            LL res = a[i];
            for (int j = n; j >= n - (k - 1) + 1; --j) {
                res += val[j];
            }
            ans = std::max(ans, res);
        }
        io << ans << '\n';
    }
    return 0;
}
datamaker 
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
#include <iostream>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;
signed main() {
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    int t = 1000; std::cout << t << std::endl;
    int maxn = 100;
    while (t--) {
        int n = 100, k = rnd() % n + 1;
        cout << n << ' ' << k << endl;
        for (int i = 1; i <= n; ++i) {
            int a = rnd() % maxn + 1;
            cout << a << ' ';
        }
        cout << endl;
        vector<int> v(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            v[i] = i;
        }
        shuffle(v.begin() + 1, v.end(), rnd);
        for (int i = 2; i <= n; ++i) {
            int fa = rnd() % (i - 1) + 1;
            int a = v[fa], b = v[i];
            if (rnd()) swap(a, b);
            cout << a << ' ' << b << endl;
        }
    }
    return 0;
}
judger (python) 
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
import os
import subprocess

def comp(filename1: str, filename2: str):
    with open(filename1, 'r') as f1, open(filename2, 'r') as f2:
        l1 = [l.strip() for l in f1.readlines()]
        l2 = [l.strip() for l in f2.readlines()]
        if l1[-1] == '': l1.pop()
        if l2[-1] == '': l2.pop()
        for i in range(min(len(l1), len(l2))):
            if l1[i] != l2[i]:
                return f"Wrong answer, diff at line {i + 1}."
        if len(l1) != len(l2):
            return f"Diff len."
    return "y"

if __name__ == "__main__":
    n = 100
    for i in range(n):
        subprocess.run(
            "./F_datamaker",
            stdout=open("in.txt", 'w'),
            shell=True,
            check=True,
        )
        subprocess.run(
            "./F",
            stdin=open("in.txt", 'r'),
            stdout=open("out1.txt", 'w'),
            shell=True,
            check=True,
        )
        subprocess.run(
            "./F_",
            stdin=open("in.txt", 'r'),
            stdout=open("out2.txt", 'w'),
            shell=True,
            check=True,
        )
        
        s = comp("out1.txt", "out2.txt")
        if s == 'y':
            print(f"test case {i + 1} / {n} passed.")
        else:
            print(s)
            break