Chgtaxihe's blog

训练补题-牛客训练赛10

# 牛客训练赛10补题记录

# C: Decrement on the Tree

将边的问题转化为点的问题：若最少需要xx条边来完全覆盖，意味着需要2x2x个端点。

可以贪心的做：

  • 如果该节点为叶子节点，其与父节点连接的边边权为ww，显然该节点应该作为端点次数ans=wans=w

  • 该节点不是叶子节点，若要使得端点数最少：

    令连接到该节点的边权最大值为maxemaxe，边权和为sumesume

    • 若sume−maxe<maxesume - maxe<maxe，说明最大的边权过大，无法与其他边配对，此时ans=maxe−(sume−maxe)ans=maxe-(sume-maxe)
    • 否则，根据奇偶性，ans=sume%2ans = sume\%2

上述两类情况可以合并

在做的时候，只需要维护各个点的maxemaxe与sumesume即可（使用multiset）

注意multiset.erase的用法！

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<ll, ll>
#define sqr(x) ((x)*(x))
using namespace std;

const int maxn = 1e5 + 100;

ll u[maxn], v[maxn], w[maxn];
ll sum[maxn];
multiset<ll> edges[maxn];

ll calc(int x){
    ll maxe = edges[x].empty()?0:*prev(edges[x].end());
    return max(2 * maxe - sum[x], sum[x] & 1);
}

void solve(){
    int n, q;
    cin >> n >> q;
    for(int i=1; i<n; i++){
        cin >> u[i] >> v[i] >> w[i];
        edges[u[i]].insert(w[i]);
        edges[v[i]].insert(w[i]);
        sum[u[i]] += w[i];
        sum[v[i]] += w[i];
    }

    ll ans = 0;
    for(int i=1; i<=n; i++) ans += calc(i);
    cout << ans / 2 << '\n';

    for(ll i=0, p, dw; i<q; i++){
        cin >> p >> dw;
        ans -= calc(u[p]) + calc(v[p]);
        sum[u[p]] = sum[u[p]] + dw - w[p];
        sum[v[p]] = sum[v[p]] + dw - w[p];
        edges[u[p]].erase(edges[u[p]].find(w[p])), edges[u[p]].insert(dw);
        edges[v[p]].erase(edges[v[p]].find(w[p])), edges[v[p]].insert(dw);
        w[p] = dw;
        ans += calc(u[p]) + calc(v[p]);
        cout << ans / 2 << '\n';
    }
}

signed main(){
    Android;
    solve();
}
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

# J: Identical Trees

首先，为了判断两棵子树结构是否相同，需要两棵树的各个节点计算Hash（Hash的设计很重要，出题人似乎特意出数据卡了Hash(如样例29)）。

dp[x][y]dp[x][y]代表树11的xx节点对应树22的yy节点时，最小的修改次数；特别的，若x,yx,y不同构，则dp[x][y]=infdp[x][y]=inf。

若x,yx,y同构，那么dp[x][y]=(x!=y)+ansxydp[x][y]=(x!=y)+ans_{xy}，其中ansxyans_{xy}为x,yx,y的子节点两两配对时，最少的修改次数（可通过网络流或KM算法求解）。

一个可行的Hash函数如下

const static ull prime = 13131;
void getHash(int u){
    Hash[u] = 31;
    vector<ull> child_h = vector<ull>(cnt_child[u]);
    for(int e = head[u], cnt = 0; ~e; e = nxt[e], cnt++){
        getHash(dest[e]);
        child_h[cnt] = Hash[dest[e]];
    }
    sort(child_h.begin(), child_h.end());
    for(ull h : child_h){
        h = ((1ll << __builtin_popcountll(h)) - 1) ^ h; // 若不进行异或，会发生Hash冲突
        Hash[u] = Hash[u] * prime + h;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

AC代码如下

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_inputlarge freopen("./input_large.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<ll, int>
#define sqr(x) ((x)*(x))
using namespace std;

struct Kuhn_Munkres{
    const static int max_node = 500 + 10;
    const static ll inf = 0x3f3f3f3f3f3f3f3f;
    int n, match_y[max_node], pre[max_node];
    ll G[max_node][max_node], slack[max_node];
    ll cx[max_node], cy[max_node]; // 顶标
    bool vis_y[max_node];

    void init(int node_cnt){
        for(int i=0; i<=n; i++) cx[i] = cy[i] = match_y[i] = 0;
        n = node_cnt;
    }

    void bfs(int u){
        int x, y = 0, next_y;
        ll min_delta;
        for(int i=0; i<=n; i++) pre[i] = 0, slack[i] = inf;
        match_y[y] = u;
        do{
            x = match_y[y], min_delta = inf, vis_y[y] = true;
            for(int i=1; i<=n; i++){
                if(vis_y[i]) continue;
                if(slack[i] > cx[x] + cy[i] - G[x][i]){
                    slack[i] = cx[x] + cy[i] - G[x][i];
                    pre[i] = y;
                }
                if(slack[i] < min_delta) next_y = i, min_delta = slack[i];
            }

            if(min_delta != 0){
                for(int i=0; i<=n; i++){
                    if(vis_y[i]) cx[match_y[i]] -= min_delta, cy[i] += min_delta;
                    else slack[i] -= min_delta;
                }
            }
            y = next_y;
        }while(match_y[y] != 0);
        while(y) match_y[y] = match_y[pre[y]], y = pre[y];
    }

    ll km(){
        for(int u=1; u<=n; u++){
            for(int i=0; i<=n; i++) vis_y[i] = false;
            bfs(u);
        }
        ll ans = 0;
        for(int i=1; i<=n; i++) ans += G[match_y[i]][i];
        return ans;
    }
    
}km;

struct _tree{
    const static int maxn = 500 + 100;
    const static ull prime = 13131, prime2 = 233;
    int head[maxn], dest[maxn], nxt[maxn], cnt_child[maxn], edge_cnt, root;
    ull Hash[maxn];

    _tree(){
        edge_cnt = 0; 
        memset(head, -1, sizeof head);
        memset(cnt_child, 0, sizeof cnt_child);
    }

    void add_edge(int u, int v){
        cnt_child[u]++;
        nxt[edge_cnt] = head[u], dest[edge_cnt] = v;
        head[u] = edge_cnt++;
    }

    void getHash(int u){
        Hash[u] = 31;
        vector<ull> child_h = vector<ull>(cnt_child[u]);
        for(int e = head[u], cnt = 0; ~e; e = nxt[e], cnt++){
            getHash(dest[e]);
            child_h[cnt] = Hash[dest[e]];
        }
        sort(child_h.begin(), child_h.end());
        for(ull h : child_h){
            h = ((1ll << __builtin_popcountll(h)) - 1) ^ h;
            Hash[u] = Hash[u] * prime + h;
        }
    }

}tree[2];

const int inf = 0x3f3f3f3f;

ll dp[510][510];

ll dfs(int x, int y){

    _tree & t1 = tree[0], & t2 = tree[1];

    assert(t1.cnt_child[x] == t2.cnt_child[y]);

    ll ans = x != y;
    if(t1.cnt_child[x] == 0) return ans;

    int u, v;
    for(int e1 = t1.head[x]; ~e1; e1 = t1.nxt[e1]){
        u = t1.dest[e1];
        for(int e2 = t2.head[y]; ~e2; e2 = t2.nxt[e2]){
            v = t2.dest[e2];
            if(t1.Hash[u] != t2.Hash[v]){
                dp[u][v] = inf;
            }else{
                dp[u][v] = dfs(u, v);
            }
        }
    }

    km.init(t1.cnt_child[x]);
    for(int e1 = t1.head[x], cnt_1 = 1; ~e1; e1 = t1.nxt[e1], cnt_1++){
        u = t1.dest[e1];
        for(int e2 = t2.head[y], cnt_2 = 1; ~e2; e2 = t2.nxt[e2], cnt_2++){
            v = t2.dest[e2];
            km.G[cnt_1][cnt_2] = -dp[u][v];
        }
    }
    ll r = km.km();
    return ans - r;
}

void solve(){
    int n; cin >> n;
    for(int i=0; i<2; i++){
        for(int j=1, v; j<=n; j++){
            cin >> v;
            if(v == 0) {
                tree[i].root = j;
            }else{
                tree[i].add_edge(v, j);
            }
        }
        tree[i].getHash(tree[i].root);
    }
    cout << dfs(tree[0].root, tree[1].root) << '\n';
}

signed main(){
    Android;
    solve();
}
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

# I: Tournament

https://blog.csdn.net/qq_45458915/article/details/107924613

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_inputlarge freopen("./input_large.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<ll, int>
#define sqr(x) ((x)*(x))
using namespace std;

void solve(){
    int n; cin >> n;
    vector<pii> v;
    
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            if((i - 1) - (n - j) < 0) v.push_back({i, j});
        }
    }

    sort(v.begin(), v.end(), [](pii a, pii b){
        if(a.second == b.second) return a.first < b.first;
        return a.second < b.second;
    });

    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            if((i - 1) - (n - j) >= 0) v.push_back({i, j});
        }
    }

    for(pii p:v) cout << p.first << " " << p.second << '\n';
}

signed main(){
    Android;
    int t; cin >> t;
    while(t--)
        solve();
}
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

另一种做法：

https://blog.csdn.net/zjllll123/article/details/107951043

最优解中，每个队伍待的时间（几乎）相同。

首先让前1→n21\to\frac{n}{2}队两两比赛，且后面的队伍尽可能晚入场

接着，让1→n21\to\frac{n}{2}与n2+1→n\frac{n}{2}+1\to n队两两比赛，且尽量保证1→n21\to \frac{n}{2}队离场时，所待的天数相同。

最后，让n2+1→n\frac{n}{2}+1\to n队两两比赛，且早入场的队伍尽早离场

# D: Hearthstone Battlegrounds

上次更新: 2021/02/24, 03:37:30
训练补题-牛客训练赛1
训练补题-牛客训练赛2

← 训练补题-牛客训练赛2→

最近更新
01
深入理解Java虚拟机
 03-04
02
DNS工作原理
 02-27
03
改用VuePress啦
 02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2021