https://www.cometoj.com/contest/14/problems

D. 精简改良

 

题意:给定一张无向连通图,要求删除一些边,使得新图仍联通,且任意两点的距离之和最长,求这个距离和。

斯坦纳树

数据范围很小,明显是要状压dp。

如果存在环,一定可以有更好的答案。所以最后的结果一定是一棵生成树。

dp[S][u]dp[S] [u] 表示在点集 SS 上,以 uu 为根的生成树的最优解,此时的点集 SS 中的答案必定是已经确定的了,即这个生成树上的所有边都不会再在其他地方有任何改变

枚举 SS 的子集 TT ,同时得到 STS-T,设为 KK,则 S=T+KS=T+K 。接下来试着把 TTKK 合并,以得到 SS :枚举 KK 中的点 uu ,作为合并后的根节点,则从 uuTT 中点 vv 连边,同时加入边 (u,v)(u,v) 的贡献,注意,由于上面说的生成树中的边不会再有改变了,所以此时计算贡献应该把全局的贡献都算上,而不仅仅是在点集 SS 上的贡献。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const ll inf = 1e18;
int n, m;
ll G[20][20];
ll dp[maxn][20];
vector<int>vc[maxn];
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
ll w;
scanf("%d%d%lld", &u, &v, &w);
G[u][v] = G[v][u] = w;
}
memset(dp, -1, sizeof(dp));
for (int s = 1; s < (1 << n); s++) {
for (int i = 1; i <= n; i++) {
if (s&(1 << (i - 1)))vc[s].push_back(i);
}
if ((int)vc[s].size() == 1)dp[s][vc[s][0]] = 0;
}
for (int s = 1; s < (1 << n); s++) {
for (int t = (s - 1)&s; t; t = (t - 1)&s) {
if (dp[t][vc[t][0]] == -1 || dp[s^t][vc[s^t][0]] == -1)continue;
for (int u : vc[s^t]) {
for (int v : vc[t]) {
if (G[u][v] == 0)continue;
dp[s][u] = max(dp[s][u], dp[t][v] + dp[s^t][u] + G[u][v] * (int)vc[t].size()*(n - (int)vc[t].size()));
}
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)ans = max(ans, dp[(1 << n) - 1][i]);
cout << ans << endl;
return 0;
}

 

E. 最大独立集

 

题意:初始给出一棵树,每次操作给定一个点,画成原树以这个点作根的形式,再把上一次操作得到的树都挂在这个树的每个节点上,求每次操作后的新树的最大独立集。

最大独立集求必选点

如果前一次得到的树的根节点必选,则这次的树主树上的点一定都不能选,因为如果选了,挂着的树的独立集至少减少 1 ,即使能够和不选一样,对以后的操作也不划算,最终得不偿失。

如果前一次得到的树的根节点不是必选,则再看主树,这次的树的根节点是否必选取决于主树的根节点是否必选,仅当必选时,选择根节点。

则这次的树永远只和主树有关,主树又是初始的树换根,所以只要对初始的树预处理每个点是否必选。

f[u]f[u] 表示只考虑 uu 的子树,uu 是否必选,则当且仅当节点的子节点都不是必选时,节点必选。

g[u]g[u] 表示不考虑 uu 的子树,uu 是否必选,则当且仅当节点的父节点必选,且节点的所有兄弟节点的 f[u]f[u] 都为 0 时,节点不是必选。因为如果存在兄弟节点向下考虑必选,那么放弃选父节点,而选兄弟节点一定是更赚的。而只向上考虑的话,不选父节点,就一定要选子节点。

仅当 f[u]&&g[u]f[u]\&\&g[u] 时,uu 必选。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const ll mod = 998244353;
int n, m;
vector<int>G[maxn];
int T;
int f[maxn], g[maxn], cnt[maxn];
void dfs1(int u, int _fa) {
for (int v : G[u]) {
if (v == _fa)continue;
dfs1(v, u);
cnt[u] += f[v];
}
if (!cnt[u])f[u] = 1, T++;
else f[u] = 0;
}
void dfs2(int u, int _fa) {
if (u != 1 && g[_fa] && cnt[_fa] == f[u])g[u] = 0;
else g[u] = 1;
for (int v : G[u])if (v != _fa)dfs2(v, u);
}
int must[maxn], B[maxn];
ll dp[maxn];
int main() {
scanf("%d%d", &n, &m);
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);
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++)if (f[i] && g[i])must[i] = 1;
dp[0] = T;
printf("%d\n", T);
B[0] = must[1];
for (int i = 1; i <= m; i++) {
int k;
scanf("%d", &k);
if (B[i - 1])dp[i] = dp[i - 1] * n%mod , B[i] = 0;
else {
dp[i] = (dp[i - 1] * n%mod + T) % mod;
B[i] = must[k];
}
printf("%lld\n", dp[i]);
}
return 0;
}

 

I. 石头剪刀布

 

题意:n个选手,每名选手有一张石头/剪刀/布的牌,两种操作,第一种:撤去第y个座位,原先y上的人挑战x上的人,仅当y赢了x,y才能代替x,x被淘汰,否则y被淘汰。第二种:查询初始时第x个人至今存活的初始发牌情况有几种。

带权并查集

被挑战的人存活的概率是 23\frac{2}{3},挑战的人存活的概率是 13\frac{1}{3} ,其他人与这两人无关,所以可以得到被挑战的人存活的情况有 3n233^n\cdot \frac{2}{3},挑战的人存活情况有 3n133^n\cdot \frac{1}{3} 种。

那么假设 x 被挑战了 aa 次挑战别人 bb 次,则 x 的存活情况有 3n(23)a(13)b3^n\cdot (\frac{2}{3})^a\cdot (\frac{1}{3})^b 种。

并且 y 座位上的人挑战了 x 座位上的人之后,再有其他人挑战 x 座位上的人,此前所有挑战过 x 座位上的选手被挑战的次数都要+1,因为如果他存活至今,x 座位上的人一定是他。

带权并查集,若两人交手,则合并两人。查询时一定是要找到根,不能直接用某人的数据,而是要加上x到根的路径上的所有人的数据。所以合并时,要把不作为根的那个人的数据中减去作为根的那人的数据,这样查询时根的数据才不会被算两次。

因为有路径要求,所以不能路径压缩,但按秩合并还是有的。

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
	#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
const ll mod = 998244353;
int n, m;
ll qpow(ll a, ll b) {
ll res = 1;
a %= mod;
while (b) {
if (b & 1)res = (res * a) % mod;
a = (a*a) % mod;
b >>= 1;
}
return res % mod;
}
int par[maxn], rk[maxn];
ll p[maxn], tot[maxn];
int find(int x, ll& a, ll& b) {
if (par[x] == x) {
a = p[x], b = tot[x];
return x;
}
int fa = find(par[x], a, b);
a += p[x], b += tot[x];
return fa;
}
void unite(int x, int y) {
ll a, b;
x = find(x, a, b);
y = find(y, a, b);
if (x == y)return;
p[x]++;
tot[x]++; tot[y]++;
if (rk[x] > rk[y]) {
par[y] = x;
p[y] -= p[x];
tot[y] -= tot[x];
}
else {
par[x] = y;
p[x] -= p[y];
tot[x] -= tot[y];
if (rk[x] == rk[y])rk[y]++;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)par[i] = i;
for (int i = 0; i < m; i++) {
int op;
scanf("%d", &op);
if (op == 1) {
int x, y;
scanf("%d%d", &x, &y);
unite(x, y);
}
else {
int x;
scanf("%d", &x);
ll a, b;
find(x, a, b);
b -= a;
ll ans = (qpow(3, n)*qpow(2, a) % mod*qpow(qpow(3, a), mod - 2)) % mod;
ans = ans * qpow(qpow(3, b), mod - 2) % mod;
printf("%lld\n", ans);
}
}
return 0;
}