今日继续垫底系列

T1题意理解错误暴力写挂

T2怒敲 $n \le 4$ 求根公式然后发现答案还得排序。。

$\text{score：0 + 10 + 0 = 10 rk：27/27}$

Problem A：游戏

题目描述

ysgh是一名Herthstone大师。现在他遇到了一个很严峻的问题：

场上总共有 $n+m$ 个随从，其中ysgh控制着 $n$ 个，对手控制着 $m$ 个。每个随从有自己的血量。

如果ysgh在这一回合成功解掉了对手的所有随从，则ysgh获胜。否则下一回合对手直接骑脸，ysgh就会输掉。

ysgh现在手里仅有一场牌，属性如下：

进行 $d$ 次，每一次等概率随机一个在场上的未死亡随从（包括自己和对手的）并且对其造成一点伤害。若不存在未死亡随从，则不进行此次攻击。一个随从未死亡当且仅当其血量严格大于 $0$。每一次攻击后，所有血量小于等于 $0$ 的随从立即死亡。

ysgh想要知道，他有多大概率可以取胜，也就是多大的概率使得在使用这张牌后，对手的随从全部死亡。

特别提醒：由于描述与实际游戏规则有出入，一切以实际题面描述为准。

数据范围

对于所有测试数据，满足 $1 \le n, m \le 6, ~ 1 \le d \le 400$

保证所有随从血量均为 $1 \sim 12$ 之间的正整数

题解

我没玩过炉石还真是对不起哦。。原来假如这一个技能结束全场都没了的话是算我方胜利而不是平手。。

将 $n + m$ 个随从一起考虑，设第 $i$ 个随从血量 $a_i$

很容易可以想到设 $f_{i, state}$ 表示前 $i$ 轮，死亡状态为为 $state$ 的概率

显然一个随从死亡后会分一段，就是你接下来要乘的概率分母要减一

多加一个死亡随从很好转移，但是当时我就卡在如何计算该随从的血量分配在前面几段需要乘上的概率

实际上很简单，只要在转移该轮攻击后无新人死亡的时候“预支”一下这个概率就好了，$\text{dp}$ 式子如下，其中，令 $|state|$ 表示 $state$ 二进制表示 $1$ 的个数，$s (state)$ 表示 $state$ 表示出的死亡随从的总血量
$$
\begin{aligned}
攻击后无新人死亡：&f_{i, state} \times \frac1{n + m - |state|} \rightarrow f_{i + 1, state} \\
攻击后存在新随从k(k \not\in state)死亡：&f_{i, state} \times \frac{\dbinom{i - s (state)}{a_k - 1}}{n + m - |state|} \rightarrow f_{i, state | (1 << (k - 1))}
\end{aligned}
$$
“预支”过后在死亡随从转移时就只要直接在前面预留下的位置中选几个就好了

当然现在还需要将剩下的未死亡的随从的血量分配（即他们可能被攻击但未死亡），一个多重背包就好了

时间复杂度 $O (2^{n + m}144^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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define MOD 998244353

using namespace std;

typedef long long LL;

const int MAX = 1 << 12;
const int MAXN = 12 + 5;
const int MAXD = 144 + 10;

inline LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD, p >>= 1;
	}
	return cnt;
}

int T, N, M, D;
int a[MAXN]= {0};

LL inv[MAXD]= {0};
LL fact[MAXD]= {0}, ifact[MAXD]= {0};
inline LL C (int n, int m) {
	if (m > n) return 0;
	return fact[n] * ifact[m] % MOD * ifact[n - m] % MOD;
}

LL f[MAXD][MAX]= {0}, g[MAXN][MAXD]= {0};
inline int lowbit (int x) { return x & (- x); }
inline int calc (int state) {
	int cnt = 0;
	while (state > 0) {
		cnt ++; state ^= lowbit (state);
	}
	return cnt;
}

int b[MAXN]= {0};

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), M = getnum (), D = getnum (); T = N + M;
	fact[0] = ifact[0] = 1;
	fact[1] = ifact[1] = inv[1] = 1;
	for (int i = 2; i <= max (T, D); i ++) {
		fact[i] = fact[i - 1] * i % MOD;
		inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
		ifact[i] = ifact[i - 1] * inv[i] % MOD;
	}
	int tot = 0;
	for (int i = 1; i <= N + M; i ++) { a[i] = getnum (); tot += a[i]; }
	D = min (D, tot);
	int limit = (1 << T) - 1;
	f[0][0] = 1;
	for (int i = 0; i < D; i ++)
		for (int state = 0; state <= limit; state ++) {
			int s = calc (state), sum = 0;
			for (int j = 1; j <= T; j ++)
				if (state & (1 << (j - 1)))
					sum += a[j];
			if (i < sum) continue;
			f[i + 1][state] = (f[i + 1][state] + f[i][state] * inv[T - s] % MOD) % MOD;
			for (int k = 1; k <= T; k ++)
				if (! (state & (1 << (k - 1)))) {
					LL mul = C (i - sum, a[k] - 1) % MOD * inv[T - s] % MOD;
					f[i + 1][state | (1 << (k - 1))] = (f[i + 1][state | (1 << (k - 1))] + f[i][state] * mul % MOD) % MOD;
				}
		}
	int stan = 0;
	LL ans = 0;
	for (int j = N + 1; j <= T; j ++) stan |= (1 << (j - 1));
	for (int state = 0; state <= limit; state ++)
		if ((state & stan) == stan) {
			int sum = 0, m = 0;
			g[0][0] = 1;
			for (int j = 1; j <= T; j ++) {
				if (state & (1 << (j - 1))) sum += a[j];
				else b[++ m] = a[j];
			}
			int V = D - sum;
			for (int j = 1; j <= m; j ++)
				for (int k = 0; k <= V; k ++) {
					g[j][k] = 0;
					for (int l = 0; l <= min (k, b[j] - 1); l ++)
						g[j][k] = (g[j][k] + g[j - 1][k - l] * C (V - (k - l), l) % MOD) % MOD;
				}
			ans = (ans + f[D][state] * g[m][V] % MOD) % MOD;
		}
	cout << ans << endl;

	return 0;
}

Problem B：方程

题面描述

求解一元 $n$ 次方程 $f(x) = \sum a_ix^i = 0$ 的所有实数根

有 $T$ 组数据

注意输出的实数根要按从大到小排序

数据范围

$1 \le n \le 6$

题解

（百度长的跟什么一样的求根公式的卑微的我）

对 $f(x)$，考虑其导数 $f’(x)$，对于 $f’(x)$ 的相邻两实数根 $x_1, x_2$ 显然有 $f(x)$ 在 $(x_1, x_2)$ 单调

那么求出 $f’(x)$ 实数根后在上述单调区间二分答案即可

递归处理

时间复杂度 $O (Tn^3)$

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long double Ld;

const int MAXN = 6 + 5;

const Ld eps = 1e-12;
const Ld INF = 1e20;

inline int dcmp (Ld p) {
	if (fabs (p) < eps) return 0;
	return p < 0 ? - 1 : 1;
}

int T;
int t[MAXN][MAXN]= {0};
int cnt[MAXN]= {0};
Ld zero[MAXN][MAXN]= {0};
Ld value (int n, Ld val) {
	Ld x = 1, ret = 0;
	for (int i = 0; i <= n; i ++, x = x * val)
		ret += t[n][i] * x;
	return ret;
}
bool find (int n, Ld L, Ld R, Ld& ze) {
	int d1 = dcmp (value (n, L));
	int d2 = dcmp (value (n, R));
	if (d1 * d2 > 0) return false;
	if (d1 * d2 == 0) { ze = d1 == 0 ? L : R; return true; }
	if (d1 < 0) {
		Ld left = L, right = R;
		while (dcmp (right - left) > 0) {
			Ld mid = (left + right) / 2.0;
			if (dcmp (value (n, mid)) <= 0) left = mid;
			else right = mid;
		}
		ze = left;
	}
	else {
		Ld left = L, right = R;
		while (dcmp (right - left) > 0) {
			Ld mid = (left + right) / 2.0;
			if (dcmp (value (n, mid)) >= 0) left = mid;
			else right = mid;
		}
		ze = left;
	}
	return true;
}
void work (int n) {
	if (n == 1) {
		Ld a = t[n][1], b = t[n][0];
		zero[n][++ cnt[n]] = - b / a;
		return ;
	}
	if (n == 2) {
		Ld a = t[n][2], b = t[n][1], c = t[n][0];
		Ld delta = b * b - 4 * a * c;
		if (dcmp (delta) < 0) return ;
		else if (dcmp (delta) >= 0) {
			if (dcmp (delta) == 0) delta = 0;
			Ld x1, x2;
			if (dcmp (a) > 0) {
				x1 = (- b - sqrt (delta)) / (2.0 * a);
				x2 = (- b + sqrt (delta)) / (2.0 * a);
			}
			else {
				x1 = (- b + sqrt (delta)) / (2.0 * a);
				x2 = (- b - sqrt (delta)) / (2.0 * a);
			}
			if (dcmp (delta) == 0) zero[n][++ cnt[n]] = x1;
			else {
				zero[n][++ cnt[n]] = x1;
				zero[n][++ cnt[n]] = x2;
			}
		}
		return ;
	}
	work (n - 1);
	if (! cnt[n - 1]) {
		Ld posi;
		if (find (n, - INF, INF, posi))
			zero[n][++ cnt[n]] = posi;
		return ;
	}
	zero[n - 1][0] = - INF, zero[n - 1][cnt[n - 1] + 1] = INF;
	for (int i = 0; i <= cnt[n - 1]; i ++) {
		Ld posi;
		if (find (n, zero[n - 1][i], zero[n - 1][i + 1], posi))
			zero[n][++ cnt[n]] = posi;
	}
}
void solve (int n) {
	for (int i = n - 1; i >= 0; i --)
		for (int j = 0; j <= i; j ++)
			t[i][j] = t[i + 1][j + 1] * (j + 1);
	work (n);
	printf ("%d\n", cnt[n]);
	for (int i = 1; i <= cnt[n]; i ++)
		printf ("%.8Lf\n", zero[n][i]);
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	bool isneg = false;
	while (! isdigit (ch)) {
		if (ch == '-') isneg = true;
		ch = getchar ();
	}
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return isneg ? - num : num;
}

int main () {
	T = getnum ();
	for (int Case = 1; Case <= T; Case ++) {
		memset (t, 0, sizeof (t));
		memset (cnt, 0, sizeof (cnt));
		memset (zero, 0, sizeof (zero));
		int n = getnum ();
		for (int i = 0; i <= n; i ++) t[n][i] = getnum ();
		solve (n);
	}

	return 0;
}

Problem C：旅游

题目描述

ysgh是最优化大师

ysgh想去旅游，他所在的城市共有 $n$ 个景点，景点之间有 $m$ 条双向道路连接。保证 $n$ 个景点可以通过 $m$ 条道路互相到达。道路长度均为 $1$。

ysgh可以通过乘坐出租车完成旅行。具体的，第 $i$ 个景点的出租车最多可以将其载到距离 $i$ 不超过 $f_i$ 的地方。在第 $T$ 天，搭乘从第 $i$ 个景点出发的出租车需要花费 $c_i \times T + w_i$ 元。

ysgh的钱已经在小卖部中挥霍一空，因此他想要选择 $1$ 至 $T_{max}$ 中的一天，从景点 $1$ 出发，搭乘出租车到达景点$x$，同时花费尽量地小。

由于他没有定下来在那个城市游玩，因此他想要对所有的 $x \in [1, n]$ 求出答案。

数据范围

保证对所有 $1 \le T \le T_{max}, c_i \times T + w_i > 0$

题解

设 $v_i = c_i \times T + w_i$

考虑暴力，对每个点向它能到达的所有点连一个边权为 $v_i$ 的边，且容易发现，答案一定在 $T$ 取 $1$ 或 $T_{max}$ 中选，然后从 $1$ 开始跑最短路

由于每个点向外出边边权相同，所以考虑用数据结构优化建图过程

从 $m = n - 1$ 的情况开始说明，首先贪心思想，每个点只会被更新一次，每次使用堆中 $d$（已知最短路）最小的点来更新其它点

设 $dist(u, v)$ 表示 $u, v$ 的最短距离（此时即树上距离）建立点分树，假设现在最短路跑到从 $u$ 开始更新其它节点，那么枚举 $u$ 在点分树上的每个祖先，那么其每个祖先 $fa$ 包含的节点中，满足 $dist (u, fa) + dist (fa, v) \le f_u$ 的所有节点 $v$ 是 $u$ 应当去更新的，不难发现，这样的 $v$ 一定是按它到 $fa$ 的距离被顺序更新的，所以可以记录每个点 $p$ 在点分树上按到 $p$ 距离递增排列的子节点，并记录一个指针，即已经更新到哪个子节点，以后在点分树上枚举到 $p$ 只需从指针记录位置开始枚举即可，这样子每个节点被访问到 $log n$ 次，故总时间复杂度 $O (n \log n)$

对于 $m \ge n$ 的情况，用与上面类似的算法，由于它最多多出 $50$ 条边，不妨就以 $m = n + 50$ 来论

在图中随意抽出一棵生成树，那么那些不在生成树中的边 $(u, v)$ 我们将 $u$ 记作冗余节点，即这样的边为冗余边，很显然这样的节点最多 $50$ 个

那么从点 $u$ 到点 $v$ 的最短距离就有两种情况

  • 全部走树上路径
  • 交替走树上路径与冗余路径，那么它一定至少经过一个冗余节点 $x$，满足 $dist (u, x) + dist (x, v) \le f_u$

对第一种情况，在生成树中运行上面所述 $m = n - 1$ 同样的算法即可，问题在于第二种情况

实际上两种情况本质上是一样的，对每个冗余节点 $p$，将所有 $n$ 个节点按到 $p$ 的距离递增排序存在数组中，那么最短路运行到 $u$ 时同样也只要用指针在数组里走就好了，步骤和 $m = n - 1$ 的情况也是一样的

这样每个节点最多被访问 $50 + \log n$ 次，总时间复杂度 $O \left(n (50 + \log n)\right)$

代码

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 2e05 + 50 + 10;
const int MAXM = MAXN;

const int INF = 0x7fffffff;
const LL LINF = 0x3f3f3f3f3f3f3f3f;

struct LFS { int to, next; } ;
LFS Link[MAXM << 1];
int Head[MAXN]= {0}, size = 0;
void Insert  (int u, int v) {
	Link[++ size].to = v;
	Link[size].next = Head[u];

	Head[u] = size;
}

int N, M, E = 0, Tm;
int b[MAXN];
int f[MAXN], c[MAXN], w[MAXN];
vector<int> G[MAXN];
vector<int> pt[MAXN], ex[60];
int poi[MAXN]= {0}, pex[MAXN]= {0};
int ances[MAXN];
int find (int x) { return ances[x] == x ? x : ances[x] = find (ances[x]); }
pair<int, int> edge[MAXM];
void build () {
	for (int i = 1; i <= N; i ++) ances[i] = i;
	for (int i = 1; i <= M; i ++) {
		int x = edge[i].first, y = edge[i].second;
		int fx = find (x), fy = find (y);
		if (fx == fy) { b[++ E] = x; continue; }
		ances[fx] = fy; Insert (x, y), Insert (y, x);
	}
}

bool visit[MAXN]= {false};
int subsize[MAXN], g, mini;
void acsize (int root, int father, int n) {
	subsize[root] = 1; int maxpart = 0;
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (v == father || visit[v]) continue;
		acsize (v, root, n);
		subsize[root] += subsize[v];
		maxpart = max (maxpart, subsize[v]);
	}
	maxpart = max (maxpart, n - subsize[root]);
	if (maxpart < mini) g = root, mini = maxpart;
}
int lev[MAXN]= {0};
int depth[25][MAXN], d[MAXN], m = 0, mdep = 0;
void DFS (int root, int father, int l) {
	d[++ m] = root; mdep = max (mdep, depth[l][root]);
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (v == father || visit[v]) continue;
		depth[l][v] = depth[l][root] + 1;
		DFS (v, root, l);
	}
}
int father[MAXN]= {0};
int buck[MAXN]= {0}, topo[MAXN];
void divide (int u, int n, int l, int fa) {
	mini = INF, acsize (u, 0, n);
	father[g] = fa; visit[g] = true;
	mdep = m = 0, lev[g] = l, depth[l][g] = 0; DFS (g, 0, l);
	for (int i = 0; i <= mdep; i ++) buck[i] = 0;
	for (int i = 1; i <= m; i ++) buck[depth[l][d[i]]] ++, topo[i] = 0;
	for (int i = 1; i <= mdep; i ++) buck[i] += buck[i - 1];
	for (int i = 1; i <= m; i ++) topo[buck[depth[l][d[i]]] --] = d[i];
	for (int i = 1; i <= m; i ++) pt[g].push_back(topo[i]);
	acsize (g, 0, n); int fg = g;
	for (int i = Head[fg]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (visit[v]) continue;
		divide (v, subsize[v], l + 1, fg);
	}
}
bool vis[MAXN]= {false};
queue<int> que;
int deep[51][MAXN]= {0};
void linkit (int S, int id) {
	while (! que.empty()) que.pop();
	memset (vis, false, sizeof (vis));
	que.push(S), deep[id][S] = 0, vis[S] = true;
	while (! que.empty()) {
		int u = que.front(); que.pop();
		for (int i = 0; i < (int) G[u].size(); i ++) {
			int v = G[u][i];
			if (vis[v]) continue;
			deep[id][v] = deep[id][u] + 1;
			que.push(v); vis[v] = true;
		}
	}
	for (int i = 0; i <= N; i ++) buck[i] = topo[i] = 0;
	for (int i = 1; i <= N; i ++) buck[deep[id][i]] ++;
	for (int i = 1; i <= N; i ++) buck[i] += buck[i - 1];
	for (int i = 1; i <= N; i ++) topo[buck[deep[id][i]] --] = i;
	for (int i = 1; i <= N; i ++) ex[id].push_back(topo[i]);
}
LL value[MAXN], ans[MAXN]= {0}, dist[MAXN];
struct node {
	int id; LL d;
	node (int id = 0, LL d = 0) : id (id), d (d) {}
	bool operator < (const node& p) const { return d > p.d; }
} ;
priority_queue<node> heap;
void trans (int u, LL d) {
	for (int p = u; p; p = father[p]) {
		int l = lev[p];
		for ( ; poi[p] < (int) pt[p].size(); poi[p] ++) {
			int v = pt[p][poi[p]];
			if (depth[l][u] + depth[l][v] > f[u]) break;
			if (dist[v] < LINF) continue;
			dist[v] = dist[u] + value[v];
			heap.push(node (v, dist[v]));
		}
	}
	for (int i = 1; i <= E; i ++) {
		for ( ; pex[i] < (int) ex[i].size(); pex[i] ++) {
			int v = ex[i][pex[i]];
			if (deep[i][u] + deep[i][v] > f[u]) break;
			if (dist[v] < LINF) continue;
			dist[v] = dist[u] + value[v];
			heap.push(node (v, dist[v]));
		}
	}
}
void solve (int T) {
	for (int i = 1; i <= N; i ++) value[i] = 1ll * c[i] * T + w[i];
	memset (poi, 0, sizeof (poi)); memset (pex, 0, sizeof (pex));
	while (! heap.empty()) heap.pop();
	memset (dist, 0x3f, sizeof (dist));
	dist[1] = value[1], heap.push(node (1, dist[1]));
	while (! heap.empty()) {
		node top = heap.top(); heap.pop();
		int u = top.id; LL d = top.d;
		trans (u, d);
	}
	for (int i = 1; i <= N; i ++) ans[i] = min (ans[i], dist[i] - value[i]);
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	bool isneg = false;
	while (! isdigit (ch)) {
		if (ch == '-') isneg = true;
		ch = getchar ();
	}
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return isneg ? - num : num;
}
inline void write (LL x) {
	if (x >= 10) write (x / 10);
	putchar (x % 10 + '0');
}

int main () {
	N = getnum (), M = getnum (), Tm = getnum ();
	for (int i = 1; i <= N; i ++) f[i] = getnum (), c[i] = getnum (), w[i] = getnum ();
	for (int i = 1; i <= M; i ++) {
		int u = getnum (), v = getnum ();
		G[u].push_back(v), G[v].push_back(u);
		edge[i] = make_pair (u, v);
	}
	build ();
	sort (b + 1, b + E + 1);
	E = unique (b + 1, b + E + 1) - b - 1;
	divide (1, N, 1, 0); for (int i = 1; i <= E; i ++) linkit (b[i], i);
	memset (ans, 0x3f, sizeof (ans));
	solve (1), solve (Tm);
	for (int i = 1; i <= N; i ++) write (ans[i]), puts ("");

	return 0;
}