2/3考试总结

7:50–8:10
读题T1估计是个数据结构T2是个 dp T3 第一眼看上去像是个 剪枝 dfs 。
8:10–9:00
T2, n^3 是好做的暴力 dp 即可。考虑怎么拓展考虑有什么高级的形式可以简化 max 的形式好像没有那就先看看 dp 有没有什么性质。感觉是有决策单调性的打一下表发现没有但是显然数据没这么强数据分布整体几乎是凸的。暂时没有其他想法但是利用凸性估计能骗不少分数至少能过随机。
在 n ^ 3 基础上使用整体二分就是 n ^ 2 log 然后再加上 wqs 二分直接二分权值就可以去掉一维 R 做到 n log ^ 2 。
9:00–9:50
T1,先写暴力。然后考虑怎么拓展。对于 Q=1 貌似可以扫描线之类的这里我忽略了一个条件导致遇到了困难不知道怎么做。
9:50–10:50
T3,对于 10 分可以暴力 dfs 但是直接枚举权值显然没有优化空间。考虑 dp 考虑能否枚举点的权值 dp ,这样复杂度是爆炸的。然后突然发现答案关于每种质因子是独立的而整除的限制可以转化为因子指数的大小关系只需要枚举指数就可以了这是 log 的于是一下子可写了 nlog^4 暴力 dp 然后 Vlog 处理答案配合特殊点可以拿到 60 分。
10:50–11:30
T3考虑 V 特别大怎么做发现大质数是没用的那么只要考虑小于根号的答案就可以了问题在于如何计算有大质数的答案不会做。
11:30–12:20 回看 T1,T2 没什么想法。

回顾反思

T1
这一题是比较可惜的考试的时候忽略了一个条件导致非常不可做不然起码能拿一些莫队的分的。
对于正解要求若干区间询问的答案由于相关答案具有可加性可以考虑扫描线枚举右端点 r,线段树上下标 l 处维护 l 到 r 的答案每次考虑 r 加进来新的贡献维护。这道题要求一个区间询问内所有子区间的答案和本是个 n ^ 2 级别的问题放到扫描线上可以在线段树上维护1.答案的历史累加值即把之前所有 r 的贡献累加起来。2.当前 r 新增的贡献枚举到下一个 r 时将该贡献复制到历史累加里去。也就是当前线段树维护的要新增的贡献以及之前所有 r 的时刻线段树维护的要新增的贡献的历史累加。那么每次询问查询历史累加值就可以了。又因为强制在线那么把原本离线的扫描线改成主席树存下所有 r 的时刻对应线段树的信息就可以了。
T2:
主要是分析性质。
对相邻一大一小两数策略的优劣性讨论发现直接将原数组做前缀 max 后再做 dp 不影响答案。那么原来变化的 max 就变成了常量可以直接斜率优化。
二是考虑分 R 组的上界列出合并其中相邻两段减少段数后会变劣的条件发现要使满足条件总段数不超过 log 级别。于是复杂度直接降下来暴力 dp 就行了。

T3:
基本的思路差不多。
一个点是要知道 Powerful Numbers 其为不存在指数为 1 的质因子的数。对于原题大于 sqrt V 的质因子指数最多为 1 ,而 Powerful Numbers 的答案通过一些计算计算又可以包含所有值域内的数那么就可以转而只考虑 Powerful Numbers从而避开大质数的问题可以直接枚举小因子了。
有结论直接暴力枚举质因子指数得到 Powerful Numbers 复杂度是 $\sqrt{V}$ 的。
那么我们枚举 Powerful Numbers设某个数为 S,钦定原题中 $a_1=lcm(a_2,a_3...a_n)$ 那么对于这道题来说得到的 a 的乘积必然是 Powerful Numbers 且任何一个 Powerful Numbers 都对应原树的一些方案且任何 Powerful Numbers 的方案不重任何 Powerful Numbers的任何倍数对应的方案也不重且能覆盖所有值域内的数那么对于每个 S 得到其贡献再由一定倍数关系就可以得到所有数的答案了。