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

解题报告（ACDFGH/10）

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

A. 牛牛的DRB迷宫I

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

分析：简单DP

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 55, mod = 1e9 + 7;
 
int n, m;
long long f[N][N];
char g[N][N];
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
    f[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i - 1][j] == 'B' || g[i - 1][j] == 'D') (f[i][j] += f[i - 1][j]) %= mod;
            if (g[i][j - 1] == 'B' || g[i][j - 1] == 'R') (f[i][j] += f[i][j - 1]) %= mod;
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

B. 牛牛的DRB迷宫II（待补）

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

分析：

C. 牛牛的数组越位

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

分析：签到题

 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
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1010;
 
int n, m, T, p;
int g[N][N];
 
int main() {
    cin >> T;
    while (T--) {
        memset(g, 0, sizeof g);
        scanf("%d%d%d", &n, &m, &p);
        bool yuewei = false, feifa = false;
        while (p--) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            if (feifa) continue;
            if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
                yuewei = true;
                int t = x * m + y;
                if (t < 0 || t >= n * m) feifa = true;
                else g[t / m][t % m] = z;
            } else {
                g[x][y] = z;
            }
        }
        if (feifa) {
            puts("Runtime error");
        } else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    printf("%d", g[i][j]);
                    if (j != m - 1) printf(" ");
                }
                puts("");
            }
            if (yuewei) puts("Undefined Behaviour");
            else puts("Accepted");
        }
    }
    return 0;
}

D. 牛牛与二叉树的数组存储

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

分析：签到题

 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
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200010;
 
int n;
int a[N], p[N];
int sz;
 
int main() {
    cin >> n;
    memset(a, -1, sizeof a);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sz = max(sz, a[i]);
        p[a[i]] = i;
    }
    printf("The size of the tree is %d\n", sz);
    printf("Node %d is the root node of the tree\n", a[1]);
    for (int i = 1; i <= sz; i++) {
        printf("The father of node %d is %d, the left child is %d, and the right child is %d\n", i, a[p[i] / 2], a[p[i] * 2], a[p[i] * 2 + 1]);
    }
    return 0;
}

E. 牛牛的随机数（待补）

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

分析：

F. 牛牛的Link Power I

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

分析：我们从前往后扫描，对于每个 $1$，我们统计它与前面所有 $1$ 的距离之和，累加到答案中即可，即可不重不漏地算出答案。

如何统计每个 $1$（假设下标为 $y$ ）与其前面所有 $1$（假设下标为 $x_i$，共有 $cnt$ 个）的距离呢？对于一组 {$y,x_i$}，距离即 $y-x_i$，求和即为：

$$ cnt \times y - \sum_{i=1}^{c} x_i $$

因此我们可以定义 $x_i$ 的前缀和 $sum$，并记录 $1$ 的数量 $cnt$，那么对于每一个 $1$ 都可以 $O(1)$ 得到其贡献 $cnt \times y-sum$，累加到答案中。总时间复杂度 $O(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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
const int N = 100010, mod = 1e9 + 7;
 
int n;
char str[N];
int s[N];
LL res;
LL sum;
int cnt;
 
int main() {
    cin >> n;
    scanf("%s", str + 1);
    for (int i = 1; str[i]; i++) {
        if (str[i] == '1') {
            (res += 1ll * i * cnt - sum) %= mod;
            sum += i;
            cnt++;
        }
    }
    cout << res << endl;
    return 0;
}

G. 牛牛的Link Power II

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

分析：思路同上，但本题有动态修改、动态查询操作，这时候就可以考虑用两个树状数组，分别维护 $cnt$ 和 $sum$。之后的每次操作都可以在初次得到的答案 $res$ 基础上进行调整。代码体现在 45 ~ 46 行，$plus$ 表示当前的这位 $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
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;
 
typedef long long LL;
 
const int N = 100010, mod = 1e9 + 7;
 
int n, m, p, q;
char str[N];
int c1[N], c2[N]; // c1维护cnt，c2维护sum
 
inline int lowbit(int x) {
    return x & -x;
}
 
inline LL sum(int c[], int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}
 
inline void add(int c[], int x, int y) {
    for (int i = x; i <= n; i += lowbit(i)) (c[i] += y) %= mod; // 惨痛教训：没取模
}
 
int main() {
    cin >> n;
    scanf("%s", str + 1);
    LL res = 0, cnt = 0, s = 0;
    for (int i = 1; str[i]; i++) {
        if (str[i] == '1') {
            res +=  i * cnt - s;
            s += i;
            cnt++;
            add(c1, i, 1);
            add(c2, i, i);
        }
    }
    printf("%lld\n", res % mod);
    scanf("%d", &m);
    LL ans = 0;
    while (m--) {
        scanf("%d%d", &q, &p);
        LL plus = sum(c2, n) - sum(c2, p) - (sum(c1, n) - sum(c1, p)) * p;;
        plus += sum(c1, p - 1) * p - sum(c2, p - 1);
        if (q == 1) {
            add(c1, p, 1);
            add(c2, p, p);
            res += plus;
            ans = res % mod;
        } else {
            add(c1, p, -1);
            add(c2, p, -p);
            res -= plus;
            ans = (res % mod + mod) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

H. 牛牛的k合因子数

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

分析：线性筛质数的时候，统计每个合数的质因子个数num，然后res[num]++，每次直接查询即可。

 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>
 
using namespace std;
 
typedef long long LL;
 
const int N = 100010;
 
int n, m, k;
int primes[N], cnt;
bool st[N];
int res[N];
 
void euler(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        else {
            int num = 1;
            for (int j = 2; j <= i / j; j++) {
                if (i % j == 0) {
                    if (j * j != i) num += st[i / j] + st[j];
                    else num += st[j];
                }
            }
            res[num]++;
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
 
int main() {
    cin >> n >> m;
    euler(n);
    while (m--) {
        scanf("%d", &k);
        printf("%d\n", res[k]);
    }
    return 0;
}

I.牛牛的汉诺塔（待补）

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

分析：

J. 牛牛的宝可梦Go（待补）