被虐了.
A 核酸检测
$n$ 为偶数和奇数时可以分别进行如下的构造.
B 齐心抗疫
比较粗暴的方法是将所有点按照 $a$ 从小到大排序,依次激活,对每个点求出已激活的点到它的最大距离,更新答案.
用点分树实现,时间复杂度 $O(n\log^2 n)$ ,需要优秀的卡常才能通过.
注意观察性质,要求的是 $\max_{a_x\le a_y} \lbrace a_y\cdot dis(x,y)\rbrace$ ,如果我们将 $ a_x\cdot dis(x,y)$ 也统计上,并不会影响答案.
于是可以直接忽略掉 $a_x\le a_y$ 的限制,只需要对每个点求出其他点到它的最大距离.
先找出树的一条直径 $u\to v$ ,根据相关性质,点 $x$ 到所有点的最大距离即为 $\max(dis(x,u),dis(x,v))$ .
时间复杂度 $O(n)$ .
C 病毒研究
首先可以对 $m$ 种操作做一个完全背包,得到 $dp(i)$ 表示将活性恰好降低 $i$ 点所需要的最小花费.
只能确定活性在某一个区间内,可以设 $f(l,r)$ 表示确定活性在 $[l,r]$ 内,期望代价乘上 $r-l+1$ 的值.
要求的答案即为 $f(1,a_n)$ .
转移时分几种情况讨论:
- 若 $l,r$ 在属于不同状态,就将 $[l,r]$ 按照所在状态分成若干小区间, $f(l,r)$ 为这些小区间 $f$ 值之和.
- 否则,若 $l,r$ 都在状态 $1$ ,可得 $f(l,r)=0$ .
- 否则,$l,r$ 在同一不为 $1$ 的状态,枚举操作,得到 $f(l,r)=\min_{1\le i< l}\lbrace f(l-i,r-i)+(r-l+1)\cdot dp(i) \rbrace$ .
如果直接 dp, 状态数为 $O(a_n^2)$ ,每次转移代价为 $O(a_n)$ ,无法通过.
考虑剪枝,计算 $f(l,r)$ 时,只用 $l-i,r-i$ 不在同一状态的 $f(l-i,r-i)$ 来更新,或者 $l-i,r-i$ 都在状态 $1$.
否则,若 $l-i,r-i$ 依然在同一不为 $1$ 的状态,就需要继续进行操作,而完全背包已经考虑了合并这两次操作的方案.
经过这样一个剪枝后,我们需要计算的 $f(l,r)$ 一定满足 $[l,r]$ 是某个状态的一段前缀或后缀,状态数降到了 $O(a_n)$ .
D 抗疫斗争
首先考虑对于一个给定的 $m$ ,如何计算 $h_m$ .
若 $m$ 不是 $2$ 的倍数,先手只需要取 $1$ ,这样后面双方都只能取 $1$ ,最后先手一定胜利,即,此时 $h_m=1$ .
若 $m$ 是 $2$ 的倍数,容易证明双方都不会在某一步取奇数个,否则游戏一定未结束,另一方下一步取 $1$ 即可保证必胜.
那么我们不断将 $m$ 变为 $\frac m 2$ , $h_m$ 也会变成原来的 $\frac 1 2 $ ,直到当 $m$ 为奇数时, $h_m=1$ .
于是可以得出 $h_m={\rm lowbit} (m)$ .
那么我们要求的答案就是
$$
ans=\sum_{i=1}^n {\rm lowbit}(i) \lfloor \frac n i\rfloor
$$
可以对 $\lfloor\frac n i \rfloor$ 整除分块,每次 $O(\log n)$ 计算 $\rm lowbit$ 的前缀和,时间复杂度 $O(\sqrt n\log n)$ .
进一步优化,可以把 ${\rm lowbit}(x)$ 拆成 $1+\sum_{k\ge 1} [2^k|x]2^{k-1}$ ,就可以枚举 $k$ 来计算每个 $k$ 的贡献.
记 $g(x)=\sum_{i=1}^n \lfloor \frac x i\rfloor$ ,由于 $\lfloor \frac n {ab}\rfloor=\lfloor \frac{\lfloor\frac n a\rfloor}{b}\rfloor$ ,可以得到
$$
ans=g(n)+\sum_{k\ge 1} 2^{k-1}g(\lfloor\frac{n}{2^k}\rfloor)
$$
计算一个 $g(x)$ 的时间复杂度为 $\sqrt x$ ,由等比数列的求和可知总时间复杂度为 $O(\sqrt n)$ .
E 名垂青史
鸽了.