Kyooma's Blog

2022-09-18周赛

  • ~5.50K 字

题目来自: 2021 ICPC Southeastern Europe Regional Contest

C - Werewolves

给出$n(n \le 3000)$个点的一棵树, 以及每个点的颜色, 求满足拥有一半以上同种颜色的连通块的个数, 对$998244353$取模

SOLUTION

首先对一种特定颜色$c$考虑, 如果一个点的颜色是$c$就$+1$, 不是就$-1$, 那么最后只要这个连通块的权值大于$0$, 就可以记入答案中.

那么我们可以考虑树上背包, 用$dp[u][j]$表示$u$点必取时连通块权值为$j$的数量.

然后就可以推出转移式是: $dp[u][k] = dp[u][k - j] * dp[v][j]$

由于可能出现负的权值, 可以给第二维整体加上一个值来避免出现负值

众所周知，一棵$n$点的树, 背包容量为$m$, 进行树上背包时如果上下界都卡紧了复杂度会是$O(nm)$ 具体证明可以看这个

那么在这个问题里, 对特定颜色考虑时, 背包容量最大是$c_i$(颜色为$c$的点的个数), 所以单次背包的时间复杂度是$O(nc_i)$

所以对每种颜色都跑一遍的复杂度就是$O(n\sum c_i)$, 由于$\sum c_i = n$, 所以总复杂度为$O(n ^ 2)$

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 3000 + 10, P = 3000, mod = 998244353;

int dp[N][N << 1], pd[N][N << 1], c[N], cnt[N];
vector<int> e[N];

int ans;

int dfs(int u, int fa, int color){
    if(c[u] == color){
        dp[u][1 + P] = 1;
    }else{
        dp[u][-1 + P] = 1;
    }
    int sz = 1;
    for(int i : e[u]){
        if(i == fa) continue;
        int p = dfs(i, u, color);
        for(int j = -min(cnt[color], sz); j <= min(cnt[color], sz); j++){
            pd[u][j + P] = dp[u][j + P];
        }
        int l = min(cnt[color], min(cnt[color], p) + min(cnt[color], sz)), r = min(cnt[color], sz);
        for(int j = -min(cnt[color], p); j <= min(cnt[color], p); j++){
            for(int k = max(-r + j, -l); k <= min(l, r + j); k++){
                dp[u][k + P] = dp[u][k + P] + 1ll * pd[u][k - j + P] * dp[i][j + P] % mod;
                if(dp[u][k + P] >= mod) dp[u][k + P] -= mod;
            }
        }
        sz += p;
    }
    for(int j = 1; j <= min(cnt[color], sz); j++){
        ans += dp[u][j + P];
        if(ans >= mod) ans -= mod;
    }
    return sz;
}

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> c[i], cnt[c[i]]++;
    for(int i = 0, u, v; i < n - 1; i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        if(!cnt[i]) continue;
        for(int j = 1; j <= n; j++){
            for(int k = -cnt[i]; k <= cnt[i]; k++){
                dp[j][k + P] = 0;
            }
        }
        dfs(1, 0, i);
    }
    cout << ans << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    while (T--) solve();
    return 0;
}

K - Amazing Tree

给出一棵树, 让你选择一个根使以这个根节点开始的先序遍历的字典序是最小的

SOLUTION

无论选哪个点为根, 先序遍历的第一个值肯定是某一个叶子结点.

那么第一个值肯定是所有叶子结点中最小的那一个, 然后考虑与它相连的$v$点, 如果除去最小的叶子结点外与$v$结点直接相连的还有两个及以上的点, 那么根据先序遍历的顺序, 之后还会往$v$结点的儿子结点遍历. 这个时候可以考虑贪心, 优先向有更小编号的叶子结点的点方向遍历. 当与$v$结点相连的点只剩一个的时候, 此时$v$点有两种可能, $v$是根节点或不是, 若它不是根节点, 那么下一个遍历的点就是它自己. 如果$v$是根节点, 那么就会先向它最后一个儿子结点处先遍历, 然后最后才遍历$v$.

于是只需要贪心的选择小的就行了, 如果$v$比最后一个儿子结点处的叶子结点编号小, 那么$v$就不是根节点, 继续往下$dfs$找根, 反之根节点就确定了, 停止$dfs$直接输出答案

CODE
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10, Log = 20, inf = 0x3f3f3f3f;

vector<int> e[N], ans;
int vis[N], d[N], dp[N];

void dfs0(int u, int fa){
    for(int i : e[u]){
        if(i == fa || vis[i]) continue;
        dfs0(i, u);
        dp[u] = min(dp[u], dp[i]);
    }
    if(d[u] == 1) dp[u] = u;
}

void run(int u, int fa){
    vis[u] = 1;
    vector<pii> v;
    for(int i : e[u]){
        if(i == fa || vis[i]) continue;
        v.push_back({dp[i], i});
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < (int)v.size(); i++){
        run(v[i].second, u);
    }
    ans.push_back(u);
}

void dfs(int u, int fa){
    vector<pii> v;
    for(int i : e[u]){
        if(i == fa || vis[i]) continue;
        v.push_back({dp[i], i});
    }
    if(v.empty()){
        vis[u] = 1;
        ans.push_back(u);
        return;
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < (int)v.size() - 1; i++){
        run(v[i].second, u);
    }
    if(v.back().first > u){
        vis[u] = 1;
        ans.push_back(u);
        dfs(v.back().second, 0);
    }else{
        run(v.back().second, u);
        vis[u] = 1;
        ans.push_back(u);
        return;
    }
}

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        vis[i] = d[i] = 0;
        dp[i] = inf;
        e[i].clear();
    }
    ans.clear();
    for(int i = 0, u, v; i < n - 1; i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        d[u]++;d[v]++;
    }
    int root = n;
    for(int i = 1; i <= n; i++){
        if(d[i] == 1) root = min(root, i);
    }
    ans.push_back(root);
    vis[root] = 1;
    root = e[root][0];
    dfs0(root, 0);
    dfs(root, 0);
    for(int i : ans) cout << i << ' ';cout << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) solve();
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可