联合省选 2020 题解

P6619 [省选联考 2020 A/B 卷] 冰火战士

随着温度变化,冰系能量增加,火系能量减少,考虑二分答案。

二分的答案为 (mathrm {mid}),如果冰系在温度 (= mathrm{mid}) 时的能量大于火系在温度 (= mathrm{mid} + 1) 时的能量,那么说明答案位置要比 (mathrm {mid}) 大,否则比 (mathrm {mid}) 小。

在线段树上二分就可以做到 (mathcal O(n log n))

P6620 [省选联考 2020 A 卷] 组合数问题

https://www.cnblogs.com/cj-xxz/p/13198301.html

P6621 [省选联考 2020 A 卷] 魔法商店

论文题。

如果序列 (A) 中的数 (x) 可以被 (y) 替换,则 (x)(y) 连边表示 (x preceq y)

然后按照论文方法跑 (L_2) 问题即可。

P6622 [省选联考 2020 A/B 卷] 信号传递

状压 dp。

(f_S) 表示确定了前 (|S|) 个数且编号在 (S) 中的答案。

(h_{i, S}) 表示当前在点 (i)(S) 内的点都在 (i) 之后的贡献次数。

(g_S) 表示 (S)(U - S) 之间的贡献。

可以很容易地列出转移方程。

P6623 [省选联考 2020 A 卷] 树

tire 树合并。

P6624 [省选联考 2020 A 卷] 作业题

反演,然后问题变为了求 (sum_{T} sum_{w in T} w)

将边权设为 (w_i x + 1),矩阵树求出 ([x^1]) 项即可。

原文地址:https://www.cnblogs.com/cj-xxz/p/13216453.html