21icpc-ec - Star's Blog

如果代码是我写的或者是后来补的，我会贴一下我这儿留着的代码，如果是我参与的我会写一下思路。

过了 A, B, I, L 五道题，罚时 494，找不到奖牌数量了，不过肯定有有铜牌。

A. DFS Order#

签到题，树形 DP，深度是最小 DFS 序，n - 子树大小 + 1是最大 DFS 序。

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 100010;
7
int head[N], ver[N], ne[N], tot;
8
int f[N][2], cnt[N];
9
int n;
10

11
void add(int x, int y) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
}
16

17
void dfs(int x) {
18
    cnt[x] = 1;
19
    for (int i = head[x]; i; i = ne[i]) {
20
        int y = ver[i];
21
        f[y][0] = f[x][0] + 1;
22
        dfs(y);
23
        cnt[x] += cnt[y];
24
        f[y][1] = n - cnt[y] + 1;
25
    }
26
}
27

28
void solve() {
29
    cin >> n;
30
    tot = 0;
31
    memset(head, 0, sizeof(int) * (n + 1));
32
    for (int i = 1; i < n; ++i) {
33
        int x, y;
34
        cin >> x >> y;
35
        add(x, y);
36
    }
37
    f[1][0] = f[1][1] = 1;
38
    dfs(1);
39
    for (int i = 1; i <= n; ++i) {
40
        cout << f[i][0] << ' ' << f[i][1] << endl;
41
    }
42
}
43

44
int main() {
45
    ios::sync_with_stdio(0);
46
    cin.tie(0), cout.tie(0);
47
    int T;
48
    cin >> T;
49
    while (T--) {
50
        solve();
51
    }
52
    return 0;
53
}

I. Future Coder#

签到题，我把合法的数对归位了三类。

不大于 0 的数 - 大于 0 的数
1 和 1
1 和其他正数

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    int T;
9
    cin >> T;
10
    while (T--) {
11
        int n;
12
        cin >> n;
13
        long long npos = 0, one = 0, pos = 0;
14
        for (int i = 1; i <= n; ++i) {
15
            int t;
16
            cin >> t;
17
            if (t <= 0) npos++;
18
            else if (t == 1) one++;
19
            else pos++;
20
        }
21
        cout << npos * (one + pos) + (one * (one - 1)) / 2 + one * pos << endl;
22
    }
23
    return 0;
24
}

L. Fenwick Tree#

参与了，但是最后一版代码不是我的。思路是在树状数组上自底向上做树形 DP（不用真的建出来树），从当前不进行操作完全不可能满足的点开始往后传一个标记，如果一个位置有两个以上的标记，能直接通过改前面加的数来满足要求，现在前面成了一个整体，标记重置成 1 次，继续往后做。

B. Beautiful String#

$n^2$ 枚举 $s_2 s_3$ 枚举分界点，找前面的这个组合的前缀和后面的这个组合出现的次数。但是常数卡的很严重，我们的哈希 + unordered_map 开 o2 优化极限的过了。