http://acm.hdu.edu.cn/contests/contest_show.php?cid=883

1012 - Set1

 

题意：给定奇数 n，从包含 1 到 n 的集合中每次先删去最小值，再随即删去一个数，对每个 i 问最终剩下 i 的概率。

显然如果 i<n−12i<\frac{n-1}{2} 则必定为 00.

后面 n−in-i 个数要在前面某几轮手动删去，所以要对应前 i−1i-1 个中的 n−in-i 个，被对应到的表示是被作为最小值删去的。则有 Pi−1n−iP_{i-1}^{n-i}.

前面还剩下 i−1−(n−i)i-1-(n-i) 个，这些两两配对，每一对中小的那个作为最小值删去，大的手动删去。也就是不断从 i−1−n+ii-1-n+i 中选 22 个删去，就是 C2i−n−12⋅C2i−n−32⋯C22/P2i−n−122i−n−12C_{2i-n-1}^2\cdot C_{2i-n-3}^2\cdots C_2^2/P_{\frac{2i-n-1}{2}}^{\frac{2i-n-1}{2}}，最后除的那个全排列是因为选的顺序没有关系，即只要配好对，它们出现的顺序就是确定的。把前面的几个 C 化简后最终得到 (2i−n−1)!2(2i−n−1)/2/(2i−n−12)!\frac{(2i-n-1)!}{2^{(2i-n-1)/2}}/(\frac{2i-n-1}{2})!.

把两个乘起来得到最终结果，Pi−1n−i⋅(2i−n−1)!2(2i−n−1)/2/(2i−n−12)!P_{i-1}^{n-i}\cdot \frac{(2i-n-1)!}{2^{(2i-n-1)/2}}/ (\frac{2i-n-1}{2})!.

总的方案数就是每轮的可选数乘积 (n−1)⋅(n−3)⋯2(n-1)\cdot(n-3)\cdots 2.

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e6 + 10;
const ll mod = 998244353;
int T;
ll n;
ll fac[N], inv[N];
ll power(ll a, ll x) {
	ll ans = 1;
	while (x) {
		if (x & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		x >>= 1;
	}
	return ans;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i %mod;
	}
	inv[N - 1] = power(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
ll P(ll n, ll k) {
	return fac[n] * inv[n - k] % mod;
}
ll inv2[N];
int main() {
	init();
	inv2[0] = 1ll;
	inv2[1] = (mod + 1) / 2;
	for (int i = 2; i < N; i++)inv2[i] = inv2[i - 1] * inv2[1] % mod;
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		ll all = 1ll;
		for (int i = 2; i < n; i += 2)all = all * i%mod;
		all = power(all, mod - 2);
		for (int i = 1; i <= n; i++) {
			if (i < (n + 1) / 2)printf("0 ");
			else {
				ll ans = P(i - 1, n - i)*fac[2 * i - n - 1] % mod*inv2[(2 * i - n - 1) / 2] % mod*inv[(2 * i - n - 1) / 2] % mod;
				printf("%lld%s", ans*all%mod, i == n ? "\n" : " ");
			}
		}
	}
	return 0;
}

 

1007 - Tree

 

题意：给定一棵树，有边权，要选出一个连通子图，最多有一个点的度大于 k，问子图最大边权和。

树上dp+贪心

dp[u][0]dp[u][0] 表示点 u 的子树中选中的所有点的度都小于等于 k−1k-1。

dp[u][1]dp[u][1] 表示点 u 的子树中选中的点中有一个的度大于 k−1k-1。

之所以是 k−1k-1 是因为这里默认一定连着父亲。断开父亲的情况下面会做另外处理。

则 dp[u][0]dp[u][0] 可以从所有儿子中贪心选出最大的 k−1k-1 个。

dp[u][1]dp[u][1] 可能从之前选出的 k−1k-1 个中挑一个成为那个特殊的点，也可能从后面没被选到的挑一个换掉前面最小的点。也可能让 u 自己成为那个特殊点，这时就是选中所有儿子。

再考虑断开父亲，则可以选中 kk 个儿子，其他的和上面情况类似。

要注意如果 k=1k=1，这时 k−1=0k-1=0，选中了 0 个，就不能在后面没选中的里选出来替换选中的了。

主要就是dp+贪心，但是实现的细节还是比较多的。

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;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int T;
int n, k;
struct E
{
	int v;
	ll w;
};
ll dp[N][2], w[N], ans;
vector<E>G[N];
vector<int>vc[N];
bool cmp(int i, int j) { return dp[i][0] + w[i] > dp[j][0] + w[j]; }
void dfs(int u, int _fa) {
	dp[u][0] = dp[u][1] = 0;
	vc[u].clear();
	for (E& e : G[u]) {
		if (e.v == _fa)continue;
		vc[u].push_back(e.v);
		w[e.v] = e.w;
		dfs(e.v, u);
	}
	if (vc[u].empty())return;
	sort(vc[u].begin(), vc[u].end(), cmp);
	int m = (int)vc[u].size();
	vc[u].insert(vc[u].begin(), 0);
	ll sum = 0;
	for (int i = 1; i <= m; i++)sum += dp[vc[u][i]][0] + w[vc[u][i]];
	if (m >= k - 1) {
		for (int i = 1; i <= k - 1; i++) {
			int v = vc[u][i];
			dp[u][0] += dp[v][0] + w[v];
		}
		for (int i = 1; i <= k - 1; i++) {
			int v = vc[u][i];
			dp[u][1] = max(dp[u][1], dp[u][0] - dp[v][0] + dp[v][1]);
		}
		if (k > 1) {
			int vd = vc[u][k - 1];
			for (int i = k; i <= m; i++) {
				int v = vc[u][i];
				dp[u][1] = max(dp[u][1], dp[u][0] - dp[vd][0] - w[vd] + dp[v][1] + w[v]);
			}
		}
		dp[u][1] = max(dp[u][1], sum);
	}
	else {
		for (int i = 1; i <= m; i++) {
			dp[u][0] += dp[vc[u][i]][0] + w[vc[u][i]];
		}
		for (int i = 1; i <= m; i++) {
			int v = vc[u][i];
			dp[u][1] = max(dp[u][1], dp[u][0] - dp[v][0] + dp[v][1]);
		}
	}
	ans = max(ans, max(dp[u][0], dp[u][1]));
	if (m >= k) {
		ll tmp0 = 0, tmp1 = 0;
		int vk = vc[u][k];
		tmp0 = dp[u][0] + dp[vk][0] + w[vk];
		for (int i = 1; i <= k; i++) {
			int v = vc[u][i];
			tmp1 = max(tmp1, tmp0 - dp[v][0] + dp[v][1]);
		}
		for (int i = k + 1; i <= m; i++) {
			int v = vc[u][i];
			tmp1 = max(tmp1, tmp0 - dp[vk][0] - w[vk] + dp[v][1] + w[v]);
		}
		tmp1 = max(tmp1, sum);
		ans = max(ans, max(tmp0, tmp1));
	}
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; i++)G[i].clear();
		for (int i = 1; i < n; i++) {
			int u, v; ll w;
			scanf("%d%d%lld", &u, &v, &w);
			G[u].push_back(E{ v,w });
			G[v].push_back(E{ u,w });
		}
		if (k == 0) { puts("0"); continue; }
		ans = 0ll;
		dfs(1, 0);
		printf("%lld\n", ans);
	}
	return 0;
}