解题报告(ACDFGH/10)

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

A. 牛牛的DRB迷宫I

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

分析:简单DP​

#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

分析:签到题

#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

分析:签到题

#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

分析:


题目链接: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)$。

#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;
}

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

分析:思路同上,但本题有动态修改、动态查询操作,这时候就可以考虑用两个树状数组,分别维护 $cnt$ 和 $sum$。之后的每次操作都可以在初次得到的答案 $res$ 基础上进行调整。代码体现在 45 ~ 46 行,$plus$ 表示当前的这位 $1$,对答案的贡献,根据具体操作来进行正负向偏移。

#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]++,每次直接查询即可。

#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(待补)

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

分析:


总结

第三场官方说明考点:$DP$,记忆化搜索,埃式筛,构造,二进制,贪心,模拟,前缀和,线段树,容斥原理,最短路