2020 牛客寒假算法基础集训营 6

解题报告（ABFGJ/10)

链接：https://ac.nowcoder.com/acm/contest/3007

A. 配对

题目链接：https://ac.nowcoder.com/acm/contest/3007/A

分析：贪心，先把两个数组的前 $k$ 大都取出来，在这些数中来进行匹配，需要使得最小值最大，那么构造方案显然就是：最小+最大，次小+次大...。简陋证明如下：

假设存在 $a_1 > a_2,\ b_1 > b_2$，如果匹配方式为：$a_1+b_1,\ a_2 + b_2$，那么最小值为 $a_2+b_2$，而采取上面所说的构造方案：$a_1+b_2,\ a_2+b_1$，最小值一定在这两个数之间，且一定大于上一种方式。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, k;
int a[N], b[N], c[N], cnt;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    sort(a + 1, a + n + 1, greater<int>()); 
    sort(b + 1, b + n + 1, greater<int>());
    for (int i = 1; i <= k; i++) c[cnt++] = a[i] + b[k - i + 1];
    sort(c, c + cnt);
    cout << c[0] << endl;
    return 0;
}

B. 图

题目链接：https://ac.nowcoder.com/acm/contest/3007/B

闲话：比较喜欢图论问题，所以看到这么简单粗暴的标题我就直接进来了。结果没想到这题变成了我的签到题，然后在 $J$ 题（真·签到）卡了好久。

分析：题意要求一条最长链。假如这是一个有向无环图，那么问题就很简单了，只要按照拓扑序求最长路即可。但是题目特别提到了简单路径，说明图中可能存在正环。所以，自然想到 $Tarjan$ 缩点，原图转化成了 $DAG$，然后按拓扑序求一遍最长路就行了啊。（不过看完题解，发现我还是做麻烦了，~~板子有啥麻烦~~）

 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
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1000010, M = N * 2;
 
int n;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], tt;
bool in_stk[N];
int id[N], sz[N], scc_cnt;
int dist[N], cnt[N];
 
void add(int h[], int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++tt] = u, in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stk[tt--];
            in_stk[v] = false;
            id[v] = scc_cnt;
            sz[scc_cnt]++;
        } while (v != u);
    }
}
 
int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        add(h, i, x);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) add(hs, a, b);
        }
    }
    for (int i = scc_cnt; i; i--) {
        if (!dist[i]) dist[i] = sz[i];
        for (int j = hs[i]; ~j; j = ne[j]) {
            int k = e[j];
            dist[k] = max(dist[k], dist[i] + sz[k]);
        }
    }
    int res = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        res = max(res, dist[i]);
    }
    printf("%d\n", res);
    return 0;
}

C. 汉诺塔（待补）

题目链接：https://ac.nowcoder.com/acm/contest/3007/C

分析：

D. 重排列（已补）

题目链接：https://ac.nowcoder.com/acm/contest/3007/D

闲话：这题就白给了，WA了好几次，以为是构造 $b[\ ]$，求方案数，比赛结束，经过别人提醒，才发现看反了要求，枯。

分析：计数问题。排序不影响方案数，从小到大枚举每一个 $b[i]$，求一下 $a[\ ]$ 中 $\le b[i]$ 的数的个数 $num$，然后乘起来就行了。注意，对于 $b[1]$，在 $a[\ ]$ 中有 $num$ 种选择，对于 $b[i],i>1$，选择个数需要减去前面已经用到的 $i-1$ 个。考虑用树状数组来统计 $a[\ ]$ 中 $\le b[i]$ 的数的个数，需要离散化。（看完题解我好像又做麻烦了）

 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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
const int N = 200010, mod = 1e9 + 7;
 
int n;
int a[N], b[N];
int c[N];
vector<int> alls;
 
int lowbit(int x) {
    return x & -x;
}
 
void add(int x, int y) {
    for (int i = x; i <= alls.size(); i += lowbit(i)) c[i] += y;
}
 
int sum(int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}
 
int find(int x) {
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        alls.push_back(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        alls.push_back(b[i]);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    for (int i = 1; i <= n; i++) {
        int t = find(a[i]);
        add(t, 1);
    }
    LL res = 1; // 从小到大枚举b[i]，找到 <= b[i]的个数
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        int num = sum(find(b[i]));
        if (i == 1) res *= num;
        else res *= max(0, (num - i + 1));
        res %= mod;
    }
    cout << res << endl;
    return 0;
}

E. 立方数（待补）

题目链接：https://ac.nowcoder.com/acm/contest/3007/E

分析：

F. 十字阵列

题目链接：https://ac.nowcoder.com/acm/contest/3007/F

分析：简单二维差分。（一开始看不懂输出要求...）

 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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2010, mod = 1e9 + 7;

int n, m, q;
LL b[N][N];

void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    cin >> n >> m >> q;
    while (q--) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        insert(x, 1, x, m, z);
        insert(1, y, n, y, z);
        insert(x, y, x, y, -z);
    }
    LL res = 0;
    for (int i = 1; i <= n; i++) {    
        for (int j = 1; j <= m; j++) {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            b[i][j] %= mod;
            (res += b[i][j] * (i + j)) %= mod;
        }
    }
    cout << res << endl;   
    return 0;
}

G. 括号序列

题目链接：https://ac.nowcoder.com/acm/contest/3007/G

分析：堆栈搞一下。

 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
#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int T, n;
char stk[N];
char op[N];

int main() {
    cin >> T;
    while (T--) {
        scanf("%d", &n);
        int res = 0, tt = 0;
        scanf("%s", op);
        for (int i = 0; op[i]; i++) {
            if (op[i] == '(') stk[++tt] = ')';
            else {
                if (!tt) res++;
                else if (stk[tt--] != ')') res++;
            }
        }
        res += tt;
        printf("%d\n", res);
    }
    return 0;
}

H. 云（待补）

题目链接：https://ac.nowcoder.com/acm/contest/3007/H

分析：

I. 导航系统（待补）

题目链接：https://ac.nowcoder.com/acm/contest/3007/I

分析：

J. 签到题

题目链接：https://ac.nowcoder.com/acm/contest/3007/J

分析：列一下半径和边长的方程即可。（一开始看是个签到题，直接猜等腰，结果浪费好长时间）

 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 <bits/stdc++.h>

using namespace std;

int a[3];
double res[3];

int main() {
    for (int i = 0; i < 3; i++) cin >> a[i];
    sort(a, a + 3);
    if (a[0] + a[1] <= a[2]) puts("wtnl");
    else {
        double r1, r2, r3;
        r1 = (a[1] + a[2] - a[0]) / 2.0;
        r2 = (a[0] + a[2] - a[1]) / 2.0;
        r3 = (a[0] + a[1] - a[2]) / 2.0;
        if (r1 < 0 || r2 < 0 || r3 < 0) puts("No");
        else {
            puts("Yes");
            res[0] = r1, res[1] = r2, res[2] = r3;
            sort(res, res + 3);
            for (int i = 0; i < 3; i++) printf("%.2f ", res[i]);
            puts("");
        }
    }
    return 0;
}

总结

本来开局做掉 $B$ 体验很好，结果卡 $J$，最后 $D$ 看错题目，没 $AC$ 可惜了。

第六场官方说明考点：贪心，图论，构造，二分，计数，数论，思维