Nowcoder National Day 4

Posted on | In

牛客国庆集训派对Day4

题目链接

Solved : A、D、G、H、I、J

unsolve : B、C、E、F

A.深度学习

Solution of A

大胆猜测，答案为$n$。然后感觉没什么问题，就交了，就过了。 显然，最优情况下是$n$组各选中一次，故答案为$n$。

Code of A

1
2
3
4
5
6
7
#include <stdio.h>
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        printf("%d\n", n);
    }
}

D.最小生成树

Solution of D

因为边权为$a_u + a_v$，所以最小生成树即将点权最小的点与其他所有点直接相连得到的树，故答案为$(n - 2) min(a_i) + \sum_{i = 1}^{n} a_i$。

Code of D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int n, a[100005];
int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        int mn = *min_element(a + 1, a + 1 + n);
        long long sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += a[i];
        }
        sum += 1ll * (n - 2) * mn;
        printf("%lld\n", sum);
    }
}

G.区间权值

Solution of G

将$f(l, r)$展开，然后化简，得到式子：$\sum_{i = 1}^{n} w_i \cdot (c_n - c_{n - i} - c_{i - 1})$， 其中$c_i = \sum_{j = 1}^{i} b_j$、$b_i = \sum_{j = 1}^{i} a_j$，即b为a的前缀和，c为a的前缀和的前缀和。

Code of 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 MOD = 1e9 + 7;

int n;
long long a[300005], w[300005];

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            (a[i] += a[i - 1]) %= MOD;
        }
        for (int i = 1; i <= n; i++) {
            (a[i] += a[i - 1]) %= MOD;
        }
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &w[i]);
        }
        long long res = 0;
        for (int i = 1; i <= n; i++) {
            res += w[i] * (a[n] - a[n - i] - a[i - 1]) % MOD;
            res %= MOD;
        }
        printf("%lld\n", (res + MOD) % MOD);
    }
}

H.树链博弈

Solution of H

队友说只要存在树上某层的黑色结点数为单数，便是先手必胜，otherwise。

Code of H

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

const int maxn = 1e3 + 5;

int n, dep;
int color[maxn], cnt[maxn];
vector<int> G[maxn];

void DFS(int u, int fa, int d) {
    dep = max(dep, d);
    cnt[d] += (color[u] == 1);
    for (const int& v : G[u]) {
        if (v != fa) {
            DFS(v, u, d + 1);
        }
    }
}

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &color[i]);
            G[i].clear(), cnt[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            int u, v; scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dep = 0;
        DFS(1, -1, 1);
        bool flag = false;
        for (int i = 1; i <= dep; i++) {
            flag |= (cnt[i] & 1);
        }
        if (flag) printf("First\n");
        else printf("Second\n");
    }
}

I.连通块计数

Solution of I

包含根结点的方案数为：$\prod_{i = 1}^{n} (a_i + 1)$

不包含根结点的方案数为：$\sum_{i = 1}^{n} a_i \cdot (a_i + 1) / 2$

Code of I

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

const int MOD = 998244353;

const long long inv2 = 499122177ll;

int n, a[100005];

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        long long res = 0, mul = 1;
        for (int i = 1; i <= n; i++) {
            res += 1ll * a[i] * (a[i] + 1) % MOD * inv2 % MOD;
            mul = mul * (a[i] + 1) % MOD;
        }
        printf("%lld\n", (res + mul) % MOD);
    }
}

J.寻找复读机

Solution of J

模拟即可，注意不说话的人也可能是复读机。

Code of 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
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int who[1005];
char s[1005][105];
bool is[1005];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= m; i++) {
            scanf("%d%s", &who[i], s[i]);
        }
        for (int i = 1; i <= n; i++) is[i] = true;
        is[who[1]] = false;
        for (int i = 2; i <= m; i++) {
            if (!strcmp(s[i], s[i - 1])) {
                continue;
            }
            is[who[i]] = false;
        }
        vector<int> ans;
        for (int i = 1; i <= n; i++) {
            if (is[i]) {
                ans.push_back(i);
            }
        }
        for (int i = 0; i < (int)ans.size(); i++) {
            printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
        }
    }
}