Codeforces Global Round 2 题解

发表于 |
字数统计: 2,661 字

难题不会写，简单题写的慢
绝了

A

题目大意：数轴上有$n$个点，每一个点间距$1$，每一个点有一个颜色，求选出距离最远，颜色不同的两个点，输出此距离。

只要考虑第一个点的颜色和其他颜色，其他颜色最远延伸到第一个点，和第一个点颜色相同的点延伸到最左端第一个颜色和第一个点颜色不同的点。

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, col[300005];
void init(){
    n = read();
    for (int i = 1; i <= n; ++i){
        col[i] = read();
    }
}
void solve(){
    int lst = 2;
    while(lst <= n && col[lst] == col[1])
        lst++;
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        if(col[i] == col[1])
            ans = max(ans, i - lst);
        else
            ans = max(ans, i - 1);
    }
    cout << ans << endl;
}
int main(){
    init();
    solve();
    return 0;
}

B

题目大意：给一个冰箱，高为$h$，宽度为$2$，有$n$瓶牛奶，每瓶牛奶有一个高度，宽度都是1。冰箱可以在任意非负整数高度安放隔板，牛奶必须放在隔板上。问最多可以按编号放多少牛奶进去。

可以看出这个问题的答案是确定的，并且有单调性，因此可以二分。设二分的答案是$k$，对前$k$瓶牛奶的高度排序，然后跑一个DP即可（这里可以用DP，但可以发现实际上答案就是降序排序后，奇数位置牛奶的高度之和）。
下面用的是不带二分的做法，时间复杂度$O(n^2\log n)$。用二分的话时间复杂度是$O(n\log ^2 n)$。
实际上用平衡树应该可以做成$O(n\log n)$。（考虑奇偶转化）

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, h, hh[3005], f[3005], hhh[3005];
void init(){
    n = read(), h = read();
    for (int i = 1; i <= n; ++i)
        hh[i] = read();
}
void solve(){
    int ans = 0;
    for (ans = 1; ans <= n; ++ans){
        for (int i = 1; i <= ans; ++i)
            hhh[i] = hh[i];
        sort(hhh + 1, hhh + ans + 1);
        f[0] = 0, f[1] = hhh[1];
        for (int i = 2; i <= ans; ++i){
            int mm = max(hhh[i], hhh[i - 1]);
                f[i] = min(f[i - 1] + hhh[i], f[i - 2] + mm);
        }
        if(f[ans] > h)
            break;
    }
    ans--;
    cout << ans << endl;
}
int main(){
    init();
    solve();
    return 0;
}

C

题目大意：对01矩阵定义一个操作：选定一个大小至少是$2\times 2$的子矩阵，对矩阵的4个角做异或操作。给定两个矩阵$A$和$B$，问$A$可否通过有限次这样的操作变成$B$。

设$C=A \text{ xor } B$，观察（这听起来实在玄学）发现$A$可通过操作变成$B$的充要条件是$C$的每一行、每一列的含$1$数目都是偶数。然后就很简单了。
这个充要条件主要是观察出来的，但其实是可以证明的，可以通过构造进行证明。

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, aa[505][505], bb[505][505];
void init(){
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)    
        for (int j = 1; j <= m; ++j)    
            aa[i][j] = read();
    for (int i = 1; i <= n; ++i)    
        for (int j = 1; j <= m; ++j)    
            bb[i][j] = read(), bb[i][j] ^= aa[i][j];
}
void solve(){
    int flag = 1;
    for (int i = 1; i <= n; ++i){
        int cnt = 0;
        for (int j = 1; j <= m; ++j)
            cnt ^= bb[i][j];
        if(cnt) flag = 0;
    }
    for (int i = 1; i <= m; ++i){
        int cnt = 0;
        for (int j = 1; j <= n; ++j)
            cnt ^= bb[j][i];
        if(cnt) flag = 0;
    }
    printf("%s\n", flag ? "Yes" : "No");    
}
int main(){
    init();
    solve();
    return 0;
}

D

题目大意：给定一个$n\times (10^{18}+1)$矩阵$A$，，是给定的数列。有$q$个询问，每次询问两个数$l, r$，求矩阵第$l$列到第$r$列中不同数的个数。

行之间的顺序和答案无关。先对升序排序，然后发现：对于一个询问$l, r$，第$i$行和第$i+1$行相重复的数的个数是。答案就是$n(r-l+1)-tot$，$tot$就是每一行这些重复数的个数之和。
然而这个$\max$不好搞。我们用离线做法，把$r-l+1$排序，然后依次处理就行了。
时间复杂度$O(n\log n + q\log q)$。

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n;
ll s[100005], sum[100005];
ll gap[100005];
pair<ll, int> pp[100005];
ll ans[100005] = {0};
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        scanf("%I64d", &s[i]);
    sort(s + 1, s + n + 1);
}
void solve(){
    for (int i = 1; i < n; ++i)
        gap[i] = s[i] - s[i + 1];
    sort(gap + 1, gap + n);
    sum[0] = 0;
    for (int i = 1; i < n; ++i)
        sum[i] = sum[i - 1] + gap[i];
    int q = read();
    for (int i = 1; i <= q; ++i){
        ll l, r;
        scanf("%I64d%I64d", &l, &r);
        pp[i].first = r - l + 1, pp[i].second = i;
    }
    sort(pp + 1, pp + q + 1);
    int cur = n - 1;
    for (int i = 1; i <= q; ++i){
        ll ggap = pp[i].first;
        while(cur > 0 && ggap + gap[cur] >= 0ll)
            cur--;
        ans[pp[i].second] = 1ll * n * ggap - (sum[n - 1] - sum[cur]);
        ans[pp[i].second] -= 1ll * (n - 1 - cur) * ggap;
    }
    for (int i = 1; i <= q; ++i)
        printf("%I64d ", ans[i]);
}
int main(){
    init();
    solve();
    return 0;
}

E

题目大意：有一堆木棒，长度分别为$2^1, 2^2, \cdots, 2^n$。给出每一种长度的木棒的个数，求用这些木棒最多可以拼出多少个三角形。

这题应该是贪心，但我好像是用DP的手法把答案弄了出来。（？）
首先要发现的是：只有用两根同样长的木棒和一根不长于它们的木棒才能拼成三角形。
设$f(i)$为到第$i$种木棒为止，总共可以拼出的三角形的最大数目。设用$2k$根该长度木棒去和长度比$2^i$小的，没有拼成三角形的木棒拼三角形，这样可以拼出$k$个；那么剩下根这种长度的木棒自行构成等边三角形。
答案就是。所以$k$要尽量大。
这样每一个长度过一遍就是答案。

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 <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[300005];
ll sum[300005] = {0};
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read(), sum[i] = sum[i - 1] + 1ll * a[i];
}
void solve(){
    ll ans = 0, ssum = 0;
    for (int i = 1; i <= n; ++i){
        ll half = min((1ll * a[i]) >> 1, ssum);
        ans += half + (a[i] - half - half) / 3;
        ssum = sum[i] - ans * 3ll;
    }
    printf("%I64d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}

F

题目大意：给定一棵$n$个点的带权树，对于每一个$x\in [0, n-1]$，求出需要移除的边的最小权值和，使得整棵树没有度超过$x$的点。

对于一个固定的$x$，容易通过树形DP求出答案。
我们可以把问题转换成为保留最大权的问题。设$f(i, 0)$为对以$i$为根的子树，使其度$\le x$的最大权值和，$f(i, 1)$为对以$i$为根的子树，使其度$\le x -1$的最大权值和。这样容易在$O(n\log n)$的时间内求出答案，因为只要先把所有子节点的$f(j, 0)$加上，然后按照$f(j, 1)+w-f(j, 0)$值排序，选取其中最大的$x$（或者$x-1$，根据当前要更新$f(i, 0)$还$f(i, 1)$而定）项就可以拼出当前节点的答案（$w$是连接这个点和子节点的边权）。
这样实际上对于所有度数小于等于$x$的点的$f$是没什么用的，因为在这种情况下必然会选满。所以在具体操作时，处理到$x$时
我们令$x$从$0$开始递增，每次对所有度数大于$x$的点跑一次DP。
然后需要注意到

对这个式子的理解可以从看每一个点对左边式子的贡献，一个度是$x$的点会被计算$x$次，因而导出右式。
每一个点用一个平衡树维护，所以总复杂度还是$O(n\log n)$。

1
2


G

题目大意：你有$n$个士兵，有$m$组敌人，每一组敌人有一个血量。你要把兵分成$m$组，可以有没有人的组。每一回合都可以令每一组兵攻击一组敌人，敌人掉血量为这组兵的人数，一组敌人血量为0或负数时这组敌人阵亡。求怎么安排兵可以使得所有敌人阵亡的回合数最少。

显然答案的下界是总血量除以$n$（向上取整）。所以就需要看怎么分配可以达到这个下界。
这里有一个神奇的构造方法：先令所有人攻击第一组敌人，直到敌人的血量小于$n$，为。那么令某一些组的兵的人数为。再令所有人攻击第二组敌人，直到敌人的血量小于$n$，为。那么令某一些组的兵的人数为。以此类推。可以发现。
对最后一组就并不限定某一组兵的人数，因为我们假设所有兵一起对最后一组兵进行攻击。
这样就可以达成效果（虽然不知道这是为什么）。可能是因为这么做可以保证每一次把一组敌人击杀的时候都不会导致兵力的浪费？
然后分配每一组兵的人数。对排序，利用差分就可以做到使前$i$组兵的总兵力为。
然后就是模拟。

1
2