题解

A. Median Maximization

原题链接

给定一个非负整数组的元素个数$n$与和$s$, 求数组的最大中位数.

贪心地把前面一半设为$0$, 其他取平均, 但由于是整数, 只能向下取整.

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>

int main(){
    int T, n, s;
    scanf("%d", &T);
    while (T--){
        scanf("%d %d", &n, &s);
        printf("%d\n", s / (n / 2 + 1));
    }
    return 0;
}

B. MIN-MEX Cut

原题链接

给定一个只含0和1的字符串, 求分割字符串后每段MEX和的最小值. MEX指不在数列中最小非负整数.

  • 答案的最大可能值就是2, 因为对于任意一个串, 不切割的MEX值总是不大于2的.
  • 先考虑答案是0的情况, 只能是所有字符都是1的时候才可能取到0.
  • 再考虑答案大于0的情况, 如果枚举串中0的段数, 有多少段0答案就是多少. 但是如果答案大于2就不如不切割划算, 所以大于2的话答案就修正为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
#include <stdio.h>

char s[100001];

int calc(){
    int zero = 0, one = 0, seg = 0, con = 0, i = 0;
    while (s[i] != '\0'){
        switch (s[i]){
            case '0': if (!con){seg++; con = 1;} zero++; break;
            case '1': con = 0; one++; break;
        }
        i++;
    }
    if (zero == 0) return 0;
    if (one == 0) return 1;
    return seg < 2 ? seg : 2;
}

int main(){
    int T;
    scanf("%d", &T);
    while (T--){
        scanf("%s", &s);
        printf("%d\n", calc());
    }
    return 0;
}

C. MAX-MEX Cut

原题链接

给一个$2 \times n$的矩阵, 把矩阵纵切成几段矩阵, 求每段MEX和的最大值. MEX指不在矩阵中出现的最小非负整数.

和B题思路一样 但是, 没有完全一样

  • 假设有一段出现了0和1, 那把它们单独切割出来不会减少对结果的贡献. 所以碰到$\begin{bmatrix} 0 \\ 1 \end{bmatrix}$这样的列, 单独拿出来就可以了.
  • 如果出现$\begin{bmatrix} 0 \\ 0 \end{bmatrix}$这种, 答案可以加1, 但是如果旁边有独立的$\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, 可以把它们合并, 这样本来后者没有贡献, 一合并就可以让答案再加1.
  • 其他的$\begin{bmatrix} 1 \\ 1 \end{bmatrix}$对答案没有贡献.

可以在读入数据时直接把第二行加到第一行上, 减少点空间开销, 也可以减少考虑的情况.

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
#include <stdio.h>

char b[100000];

int calc(int n){
    int i, con = 0, sum = 0;
    for (i = 0; i < n; i++){
        switch (b[i]){
            case 0: sum++; break;
            case 1: sum += 2; break;
            case 2:{
                if (i > 0 && b[i - 1] == 0) sum++;
                else if (i < n - 1 && b[i + 1] == 0){sum += 2; b[i + 1] = 3;}
            }break;
        }
    }
    return sum;
}

int main(){
    int T; char c; int n, i, j;
    scanf("%d", &T);
    while (T--){
        scanf("%d", &n);
        for (i = 0; i < 2; i++){
            for (j = 0; j < n; j++){
                scanf(" %c", &c);
                b[j] = i == 0 ? (c - '0') : (b[j] + c - '0');
            }
        }
        printf("%d\n", calc(n));
    }
    return 0;
}

D. Seating Arrangements

原题链接

有$n$行$m$列的座位和$n \times m$个人, 视力不好的人的座位编号应该比视力好的小. 这些人按照原顺序进场, 走到他们座位所在行再从左到右走找到自己座位. 如果走到自己座位之前要经过另一个人, 不满意度加1. 求最小不满意度.

对于视力不同的一堆人, 他们的所有位置是确定的, 我们要调整的是视力相同的人的位置.
所以先排序, 以视力为第一顺序, 序号为第二顺序.

qsort是C库函数, 用C习惯了就没使用C++的sort和重载运算符了. (也不知道这二者效率的分别, 等哪天找个机会测试一下)


考虑相同视力的人的内部排序. 在同一行座位中, 我们应该把序号小的放在右边, 这样同视力但序号大的人就不会增加不满意度.
对于在不同行但同视力的人, 只有靠后的行影响其他人的不满意度, 而在之前的排序中, 已经尽可能把序号大的向后放置了, 所以只要反转同一行就行.
程序思路大概是排完序后遍历每一行, 对于同视力的连续座位, 把序号reverse一下就好了.

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
#include <stdio.h>
#include <stdlib.h>

typedef struct info{
    int i, a;
}info, *pinfo;

info b[100000];

int cmp(const void *p1, const void *p2){
    const pinfo a = (const pinfo)p1, b = (const pinfo)p2;
    if (a->a != b->a) return a->a < b->a ? -1 : 1;
    return a->i < b->i ? -1 : 1;
}

void reverse(int p, int q){
    if (q - p <= 1) return;
    info tmp; int i, r;
    for (i = p; i < (p + q) / 2; i++){
        r = p + q - i - 1;
        tmp = b[i];
        b[i] = b[r];
        b[r] = tmp;
    }
}

void adjust(int n, int m){
    int r, t = 0, pos, i, j;
    for (i = 0; i < n; i++){
        for (j = 0; j < m; j++, t++){
            if (j == 0){r = b[t].a; pos = t; continue;}
            if (b[t].a != r){
                r = b[t].a;
                reverse(pos, t);
                pos = t;
            }
        }
        reverse(pos, t);
    }
}

int calc(int n, int m){
    int sum = 0, i, j, k, t;
    for (i = 0; i < n; i++){
        for (j = m - 1; j >= 0; j--){
            t = b[i * m + j].i;
            for (k = j - 1; k >= 0; k--){
                if (b[i * m + k].i < t) sum++;
            }
        }
    }
    return sum;
}

int main(){
    int T; int n, m, i, t;
    scanf("%d", &T);
    while (T--){
        scanf("%d %d", &n, &m);
        t = n * m;
        for (i = 0; i < t; i++){
            scanf("%d", &b[i].a);
            b[i].i = i;
        }
        qsort(b, t, sizeof (info), cmp);
        adjust(n, m);
        printf("%d\n", calc(n, m));
    }
    return 0;
}
比赛的时候没注意看题, 原题D1和D2是一样的, D1的$n$固定是1, 要是D2当时做不出来就难受了. 不过最后D2通过了, 妙~~啊~~.

E. Buds Re-hanging

原题链接

把树中子节点全为叶子的结点叫做bud. 给定一棵有根树, 可以把bud和它的子节点整个移动到树中其他结点, 求经过有限次移动后的新树中最小叶子数.

可以先不考虑一个bud取下来以后挂在哪个节点上, 直接把它放在一边, 等最后把所有的子树拼起来就OK, 如图.
E题图解
结果: $(2-1)+(1-1)+(1-1)+1=2$
用dfs遍历子树, 每次遇到拆解后可以形成的bud节点, 统计这棵树的叶子数. 因为最后拼接的时候其中一个叶子要和下一个bud连接, 所以实际统计的是叶子数-1. 最后一个bud没有下一个和它连接了, 就不用-1, 到最后的时候答案+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
// Referred to the code on https://codeforces.com/contest/1566/submission/128689795

#include <stdio.h>
#include <vector>

using namespace std;

vector<int> tree[200001];
int ans;

int dfs(int node, int pre){
    int n = 0, i;
    for (i = 0; i < tree[node].size(); i++){
        int next = tree[node][i];
        if (next != pre) n += dfs(next, node);
    }
    if (n == 0) return 1;
    ans += n - 1; return 0;
}

int main(){
    int T, n, a, b, i;
    scanf("%d", &T);
    while (T--){
        scanf("%d", &n);
        for (i = 1; i <= n; i++) tree[i].clear();
        for (i = 1; i < n; i++){
            scanf("%d %d", &a, &b);
            tree[a].push_back(b), tree[b].push_back(a);
        }
        ans = 1;
        dfs(1, 0);
        printf("%d\n", ans);
    }
    return 0;
}

后面的先搁着吧, 等星期八再补