跃迁引擎启动

CCPC-Wannafly Winter Camp Day3

发表于 更新于 分类于 ， 阅读次数：
rank solved A B C D E F G H I J
9/55 5/10 . . . O Ø O O . O .

D 精简改良

Solved by Grunt and XLor.

求出图 $G=(V,E)$ 的一棵生成树，满足路径总长度最大。

生成树状压 $dp$，考虑 $dp[S][i]$ 表示选出了点集 $S$ 后，以 $i$ 为根的生成树的最大权值。

转移方式，枚举子集 $S_1$ ，再枚举子集的子集 $S_2$，将子集 $S_2$ 的生成树与 $S_2$ 在 $S_1$ 内补集的生成树合并。

枚举子集复杂度 $O(3^n)$（注意写法，防止复杂度退化），因为每个元素的归属有 $3$ 种。

时间复杂度：$O(3^nn)$。

E 最大独立集

Upsolved by XLor.

给一棵树，有 $m$ 次操作，每次将在树上选一个根，然后将上一次操作得到的树接到这棵树上的每一个顶点，得到一颗新树，求这 $m+1$ 棵树的各个最大独立集大小。

第一次最大独立集可以用树形 $dp​$ 容易求解。

之后每次生成新树的时候，应该将每个前一棵树的最大独立集都选出来，这样显然是最优的。也就是当前树上的节点都不能选取，然后选取了 $n$ 次前一棵树的最大独立集。

然后继续考虑这样做的正确性，显然如果前一棵树的根节点被选上了，那么新树的每一个点一定不能选。如果选出来了，可能导致答案不优。

我们继续考虑一种情况，如果一棵树的根节点选不选对这棵树的最大独立集大小没有影响，那么我们不选这个根节点。考虑下一棵树，因为前一棵树的根节点没有选，所以新树中本来的点还可以再可以选出一个最大独立集，这样这棵树的答案一定比选前一棵树根时的答案优。

最后，我们得到了一个贪心的做法：如果上一棵树的树根可以不选（比较选不选时的答案），那么就不选，那么当前答案为当前树的最大独立集 + $n$ 倍的前一棵树的最大独立集大小；如果上一棵树的树根必选，也就是不选时上一棵答案不优，那么当前答案为 $n$ 倍的前一棵树的最大独立集大小。

至此，我们需要一趟树形 $dp$ 得到每棵子树的最大独立集，第二趟 $dp$ 得到以每个点为根时的最大独立集大小，然后递推即可。

F 小清新数论

Solved by wb.

杜教筛。

H 排列

Solved by Grunt.

I 石头剪刀布

Solved by Grunt and XLor.

首先，我们从概率的角度理解问题，而不是计数。

初始状态下，任何一个人的存活概率为 $1$。

对于每次比赛，连一条从客场作战者到主场作战者的边。

进行一次比赛后，主场作战者的存活概率为 $2\over3$，客场作战者的存活概率为 $1 \over 3$。而主场作战者可能不是原位置上的人，而是这个位置所属于的块内的某一个人，这个块内的每个人存活概率都变成了原来的 $2 \over 3$，客场作战者同理。

因此，我们需要维护的是一个联通块，联通块的合并以及每个点到这个块内根节点的权值乘积，带权并查集启发式合并即可。

代码

D

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define assert(x) do{int a=1,b=0;if(!(x))printf("%d",a/b);}while(0)
#ifdef XLor
  #define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
  #define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

int n, m, g[20][20], ones[1 << 15], tmp0[30], tmp1[30];
ll dp[1 << 15][20];

int main(){
    for (int i = 1; i < (1 << 15); i++) {
        int cnt = 0, x = i;
        while (x) {
            if (x & 1) cnt++;
            x >>= 1;
        }
        ones[i] = cnt;
    }
    ms(dp, -1);
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        u--; v--;
        g[u][v] = g[v][u] = w;
    }
    int ss = 1 << n;
    for (int i = 0; i < n; i++) dp[1 << i][i] = 0;
    for (int s = 1; s < ss; s++) {
        for (int s0 = s; s0; s0 = (s0 - 1) & s) {
            int s1 = s ^ s0;
            int l0 = 0, l1 = 0;
            for (int i = 0; i < n; i++) if (s0 & (1 << i)) tmp0[l0++] = i;
            for (int i = 0; i < n; i++) if (s1 & (1 << i)) tmp1[l1++] = i;
            // for (int i = 0; i < n; i++) {
            for (int k0 = 0; k0 < l0; k0++) {
                int i = tmp0[k0];
                if ((s0 & (1 << i)) == 0 || dp[s0][i] == -1) continue;
                // for (int j = 0; j < n; j++) {
                for (int k1 = 0; k1 < l1; k1++) {
                    int j = tmp1[k1];
                    if ((s1 & (1 << j)) == 0 || g[i][j] == 0 || dp[s1][j] == -1) continue;
                    // ll tot = dp[s0][i] + dp[s1][j] + 1ll * g[i][j] * max();
                    dp[s][i] = max(dp[s][i], dp[s0][i] + dp[s1][j] + 1ll * g[i][j] * ones[s1] * (n - ones[s1]));
                    dp[s][j] = max(dp[s][j], dp[s0][i] + dp[s1][j] + 1ll * g[i][j] * ones[s0] * (n - ones[s0]));
                }
            }
        }
    }
    // for (int i = 1; i < ss; i++) {
    //     dbg(i, dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4]);
    // }
    ll ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, dp[ss - 1][i]);
    cout << ans;
    return 0;
}

E

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 100000 + 5;

vector<int> edge[maxn];
int n, m, k[maxn];

int dp[maxn][2];
void dfs(int u, int f) {
    int s1 = 0, s2 = 1;
    for (int& v: edge[u]) {
        if (v == f) continue;
        dfs(v, u);
        s1 += max(dp[v][0], dp[v][1]);
        s2 += dp[v][0];
    }
    dp[u][0] = s1; dp[u][1] = s2;
}

int dp2[maxn][2];// greedy, rebuild greedy
void dfs2(int u, int f, int k1, int k2) {
    int s1 = max(k1, k2), s2 = k1 + 1;
    for (int& v: edge[u]) {
        if (v == f) continue;
        s1 += max(dp[v][0], dp[v][1]);
        s2 += dp[v][0];
    }
    dp2[u][0] = s1; dp2[u][1] = s2;
    for (int& v: edge[u]) {
        if (v == f) continue;
        dfs2(v, u, s1 - max(dp[v][0], dp[v][1]), s2 - dp[v][0]);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 2, u, v; i <= n; i++) {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for (int i = 1; i <= m; i++) scanf("%d", k + i);
    dfs(1, 0); 
    dfs2(1, 0, 0, 0);
    int ans = max(dp[1][0], dp[1][1]), last = 0; // 0: not choose
    if (dp[1][1] > dp[1][0]) last = 1;
    printf("%d\n", ans);
    for (int i = 1; i <= m; i++) {
        ans = 1ll * ans * n % mod;
        if (last == 0) {
            ans = (ans + max(dp2[k[i]][0], dp2[k[i]][1])) % mod;
            if (dp2[k[i]][1] > dp2[k[i]][0]) last = 1;
        } else last = 0;
        printf("%d\n", ans);
    }
    return 0;
}

I

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 200000 + 5;

ll qpow(ll x, ll n = mod - 2) {
    ll r = 1;
    while (n) {
        if (n & 1) r = r * x % mod;
        n >>= 1; x = x * x % mod;
    }
    return r;
}

int n, q, pre[maxn], siz[maxn], val[maxn];

int find(int x) { return x == pre[x] ? x : find(pre[x]); }

int main(){
    scanf("%d%d", &n, &q);
    int sum = 1; for (int i = 1; i <= n; i++) sum = 1ll * sum * 3 % mod;
    for (int i = 1; i <= n; i++) pre[i] = i, siz[i] = 1, val[i] = 1;
    ll k1 = qpow(3), k2 = qpow(2);
    int op, x, y;
    while (q--) {
        scanf("%d%d", &op, &x);
        if (op == 1) {
            scanf("%d", &y);
            x = find(x); y = find(y);
            if (siz[y] < siz[x]) {
                val[y] = 1ll * val[y] * qpow(val[x]) % mod * k2 % mod;
                val[x] = 2ll * val[x] % mod * k1 % mod;
                pre[y] = x; siz[x] += siz[y];
            } else {
                val[x] = 2ll * val[x] % mod * qpow(val[y]) % mod;
                val[y] = 1ll * val[y] * k1 % mod;
                pre[x] = y; siz[y] += siz[x];
            }
        } else if (op == 2) {
            int ans = sum;
            while (x != pre[x]) {
                ans = 1ll * ans * val[x] % mod;
                x = pre[x];
            }
            printf("%d\n", 1ll * ans * val[x] % mod);
        }
    }
    return 0;
}