【训练记录】6.4 训练笔记

由于奇奇怪怪的原因(其实是因为太困+vp CF),于是就又摸了好久…

A

看上去就是一个组合游戏,于是考虑先分类出局面来。发现确定的必败态必然是只剩两个点,这时后手必胜。那么接着考虑中间的某些必败必胜态都是怎么互相转移的。

然后大概就是靠什么先验直觉来观察了。考虑只剩两个点的时候不存在偶度点,同时这个博弈长得就跟度数十分有关。那么就可以猜一波度数。具体的,将局面分成两类,「全都是奇度点 $P$」和「至少存在一个偶度点 $Q$」。发现局面 $Q$ 至少可以专用到一个 $P$ ,而局面 $P$ 转移到的一定都是局面 $Q$ ,再加上 $P$ 一定包含至少一个必败态(即终态),所以不难知道这种分类这符合组合游戏对于必败态和必胜态的定义。

于是就瞎判一下就好了。

B

给出一棵二叉树。问能否给所有点黑白染色,使得在将这棵树的所有叶子用空节点补全之后满足:

1、任意两个白点不相邻。

2、从根节点到任意一个空节点经过的黑点个数一样多。

$1\leq n\leq 5000$ 。

一开时觉得为了使之尽量合法,所以应该让最长的那条链上黑点个数恰好是一半…反正就是推了几个类似的睿智结论,然后就当场去世了QAQ。

Sol 1

考虑直接用 dp 确定合法性。设 $f_{i,j,0/1}$ 表示以 $i$ 为根的子树,每条根到空节点路径上的黑点个数为 $j$ ,当前点涂成黑/白是否可以。那么转移就是枚举一个左子树转移。

然后初值的话,考虑如果某个叶子没有兄弟的话就必须涂白色。

于是就可以直接对着 $\{f\}$ 构造了。复杂度 $O(n^2)$ 。

「My-Code」
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
int n ;
int rt ;
vint E[N] ;
int dep[N] ;
bool foc[N] ;
char ans[N] ;
int f[N][N][2] ;//0r1b

void dfs(int x){
bool r = 0 ;
for (auto y : E[x]){
if (E[x].size() == 1) foc[y] = 1 ;
dep[y] = dep[x] + 1 ;
dfs(y) ; r = 1 ;
}
if (!r){
if (foc[x])
f[x][0][0] = 1 ;
else{
f[x][0][0] = 1 ;
f[x][1][1] = 1 ;
}
}
}
void solve(int x){
if (E[x].size()){
for (int j = 1 ; j <= n ; ++ j)
f[x][j][0] = f[x][j][1] = 1 ;
}
for (auto y : E[x]){
solve(y) ;
for (int j = 1 ; j <= n ; ++ j){
f[x][j][0] &= f[y][j][1] ;
f[x][j][1] &= f[y][j - 1][1] | f[y][j - 1][0] ;
}
}
}
void out_p(int x, int cnt_b, int col){
ans[x] = "RB"[col] ;
// cout << x << " " << cnt_b << " " << col << '\n' ;
for (auto y : E[x]){
if (!col || !f[y][cnt_b - 1][0])
out_p(y, cnt_b - col, 1) ;
else out_p(y, cnt_b - col, 0) ;
}
}
int main(){
cin >> n ; int x ;
for (int y = 1 ; y <= n ; ++ y)
x = qr(), E[x].push_back(y) ;
rt = E[0][0] ; dfs(rt) ; solve(rt) ;
for (int i = 0 ; i <= n ; ++ i){
// cout << f[rt][i][0] << " " << f[rt][i][1] << '\n' ;
if (f[rt][i][0]) return out_p(rt, i, 0), !puts(ans + 1) ;
if (f[rt][i][1]) return out_p(rt, i, 1), !puts(ans + 1) ;
}
return !puts("Impossible") ;
}

Sol 2

上面那个做法是胃疼做法,胃疼在没有深刻发现性质。

首先设整棵树里所有叶子和只有一个孩子的点为关键点。那么如果关键点中深度极差 $\geqslant 2$ 可以知道必然不存在解,因为这样必然会多一个黑点。之后考虑这是一定可以黑白染色的,因为红黑树本质上比这个限制要多但依然可以红黑染色。具体的可以考虑让所有和最小深度关键点深度的奇偶性相同的点都染成黑色,否则染成红色。不难知道这是合法的。

C

对于任意 $1≤k≤n$, 求有多少个左右区分的恰有 $k$ 个叶子节点的二叉树, 满足对于每个节点要么没有叶子节点要么有两个节点, 同时不存在一个叶子节点, 使得根到它的路径上有不少于 $m$ 条向左的边。

你只需要求出答案对 $998244353$ 取模的结果。

$1\leq n\leq 5000$ 。

比较考察基础的一道经典 DP?虽然不是很难。

Sol 1

比较暴力的想法就是设计一个 $f_{i,j}$ 表示当前有了 $i$ 个叶子节点,到每个叶子左边个数最多为 $j$ 的方案数。转移的话考虑枚举叶子数,拆左子树

即考虑拆出来的那条左边对答案的贡献。复杂度 $O(n^3)$ 。

然后发现这是个卷积的形式,可以信仰一波优化到 $O(n^2\log n)$ 通过此题。

Sol 2

考虑上面那个做法属实胃疼。观察转移可以发现每次转移左子树和右子树的 $j$ 的差为 $1$ 且固定。于是可以把第二维换一下。设 $f_{i,k}$ 表示以 $i$ 为根,左右子树的左边个数之差为 $k$ 的方案数。那么考虑每次按照 $dfs$ 序的顺序,即先左后右,插入一个新的叶子,会得到

即分类讨论插入的是左叶子还是右叶子。复杂度 $O(n^2)$ 。

Sol 3 (by duye)

考虑一个跑得更快的做法。大概说设限制为 $m$ 时的这种树的 OGF 是 $F_m(x)$,其中 $[x^n]F_m(x)$ 表示有 $n$ 个叶子的结果。那么有转移

感觉还是挺显然的?本质上就是在拼插一棵二叉树。写成递推形式就是

发现可以分别维护分子分母,最后求逆一次就好了。复杂度 $O(n^2+n\log n)$ 。但因为前面维护分子分母只用 $\deg(F)$ 次运算,所以最后带一个 $\dfrac{1}{2}$ 的常数。实际效率优秀。

D

比较简单的题目,但是感觉 trick 挺新颖。

考虑首先「最小」一定是对每一趟航班从大到小排序来做,同时不同的航班之间彼此没有影响。之后考虑如何算期望。由于算期望时终态固定,所以考虑倒着做。设 $\mathbb{E}_i$ 表示考虑 $i\sim n$ 的航班的期望最小步数,发现有转移

其中 $\zeta(i)$ 是这趟航班检查完了一个坏掉的都没有的期望,转移跟后面差不多但是边界比较奇怪就单列出来了。

那么考虑答案本质上就是在求这个东西的最小值。考虑这相当于是一系列一次函数的嵌套,于是考虑按照什么顺序去嵌套这 $n$ 个函数。考虑如下偏序关系:

移项可以得到

于是按照这个排序就好了。复杂度 $O(\sum k_i+n\log n)$ 。

「My-Code」
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
int n, k ;

db ans ;
db base[N] ;
pdb func[N] ;

int main(){
scanf("%d", &n) ; db res, t ;
for (int i = 1 ; i <= n ; ++ i){
scanf("%d", &k) ; res = 1.0 ;
for (int j = 1 ; j <= k ; ++ j) scanf("%lf", &base[j]) ;
sort(base + 1, base + k + 1, [](db x, db y){ return x > y ; }) ;
while (k && base[k] <= eps) k -- ;
if (base[1] >= 1.0 - eps) { n --, i -- ; continue ; }
for (int j = 1 ; j <= k ; ++ j){
t = res * base[j], res *= (1.0 - base[j]) ;
func[i].fr += t , func[i].sc += t * j ;
}
func[i].sc += res * k ;
}
sort(func + 1, func + n + 1, [](pdb a, pdb b){ return a.fr * b.sc + a.sc < b.sc + b.fr * a.sc ; }) ;
for (int i = n ; i >= 1 ; -- i)
ans = func[i].fr * ans + func[i].sc ;
printf("%.10lf", ans) ; return 0 ;
}

E

$1\leq m\leq 10^6,1\leq n\leq 30$ 。

首先先看这个诡异操作,不难发现就是左移,如果 $2^{n-1}$ 位是 $1$,那么就把第一位或成 $1$,再 $\rm and$ 上 $2^{n}-1$ …结果发现这就是一个循环左移的操作。

然后不难看出初值有限。但是因为初值的选取和小 Y 的决策都是变量,所以考虑定住一边。发现让 $x$ 循环左移之后再异或,由于位运算的交换律,本质上可以等价于让第 $1\sim i$ 的前缀整体循环左移一位然后再异或上 $x << 1$ ,即

然后就可以预处理处一个 $\{b_n\}$ 表示

然后考虑对于一个固定的 $x$ ,小 Y 的策略就会是找到对于一个固定的 $x$ 的最小的 $b_i$,而小 D 的策略则是选择最优的初值达到最大的结果。

于是考虑按位分治。先对 $\{b_n\}$ 排个序,这样对于每一位为 $1$ 或是为 $0$ 就是一个连续的区间。那么如果整个区间中的所有 $b_i$ 第 $p$ 位均为 $1$ ,那么这一位就必须要选 $1$ ,否则小 Y 可以在小 D 选 $0$ 的时候也选 $0$,选 $1$ 的时候也选 $1$ 使得答案最小。

注意,本质上是不需要体现出 $x$ 也要 $<<1$ 这一点来,因为每个 $x$ 对应着唯一的 $x<<1$ ,而我们只关心最后的最小答案和方案数,并不关心具体选了什么 $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
int T ;
int ans ;
int cnt ;
int n, m ;
int a[N] ;
int b[N] ;
int pre[N] ;
int suf[N] ;

void solve(int l, int r, int p, int res){
// cout << l << " " << r << " " << p << " " << res << '\n' ;
if (p < 0){
if (res > ans)
ans = res, cnt = 1 ;
else if (res == ans) ++ cnt ;
return void() ;
}
int mid = l, now = 1 << p ;
while (mid <= r && !(b[mid] & now)) ++ mid ;
if (mid == l || mid > r)
return solve(l, r, p - 1, res | now) ;
solve(l, mid - 1, p - 1, res) ;
solve(mid, r, p - 1, res) ;
}
int main(){
cin >> n >> m >> T ;
for (int i = 1 ; i <= m ; ++ i) a[i] = qr() ;
for (int i = 1 ; i <= m ; ++ i) pre[i] = pre[i - 1] ^ a[i] ;
for (int i = m ; i >= 1 ; -- i) b[i - 1] = suf[i] = suf[i + 1] ^ a[i] ;
for (int i = 0 ; i <= m ; ++ i)
b[i] ^= ((pre[i] >> (n - 1) | (pre[i] << 1)) & ((1 << n) - 1)) ;
sort(b, b + m + 1) ; solve(0, m, n - 1, 0) ;
cout << ans << "\n" ; if (T) cout << cnt << '\n' ;
return 0 ;
}