CF1254
CF1254
A
贪心，显然蛇形填数最优。注意特判最后要填完。
B
贪心，最后的 \gcd 一定是个质数，不妨直接枚举，只有 \omega(\sqrt n) 种。
考虑第 i 条边的贡献至少为 \min{\sum {j=1}^i a_j,\sum{j=i+1}^na_j}，不难发现充分性显然。
所以记个前缀和扫一遍即可。
C
随意钦定一起点 s 以及另一点，用 n 次叉积可以求得第二个点 p。
n 次求面积，可得出所有 (s,p,i) 的面积，其中面积最大的点一定为 s 的对立点 g。
而同一边的面积一定是有序的。
再用 n 次询问求出每个点在线段 (s,g) 的哪边。
D
对于点 v 的修改，假定 v 是树根，如果 r 和 u 在同一个子树内，则 v 不在路径上，不会加 d；否则会加上 d。
随机选择一个点，它被加上 d 的概率是 P=\frac{n-sz(u)}n，因此，某个点的权值期望增加量为 P\times d。
很显然可以差分一下。
- 对于重儿子，直接在 BIT 上修改。
- 对于轻儿子，打个标记在父节点上。
查询时加上重链顶的贡献即可。
时间复杂度：O(n\log ^2n)。
E
如果没有任何限制，答案即为 \prod deg_i!（不同相对顺序）。
限制即为若干条不重叠的路径，故其总长为 O(n)，直接暴力爬树。
对于同一个点可能有若干路径于此交汇，每个点单独考虑则有三种情况：
- 为起始
- 为末尾
- 删 A 后必立刻删 B
设从该点连出的符合条件的链数为 F_i，则答案即为 \prod F_i!。
不合法的情况有：
- 路径重叠
- 路径成环
- 该点需连出的链数超过 1
时间复杂度：O(n)。
本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-04
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录