标题鉴定为二游玩多了. 这是施工现场, 感觉工程量比较大就同步更新了.
省略编号 \(\overline{xy}_{(9+7)}\) 即第 \(x\) 篇 (国赛训练的) sol set 的第 \(y\) 道题, 链接只指到 sol set, 麻烦自己翻一下.
应该会有一个前言.
Motivations
动机, 大概就是 "为什么想到这样思考" 的原因. 感性所能及的范围其实远于理性, 做一些元思考工作是重要的.
- 注意树上路径信息能否转化成到根的路径的差分信息, 自由度直接砍掉一个 \(n\) 岂不美哉? [00]
- 构造题, 尝试构造 "强化操作", 处理 "原操作组合出强化操作" 和 "强化操作完成构造" 两部分. [01]
- 算合法需要去重, 算非法也需要去重, 但两个问题的去重难度可能是不一样的, 都值得考虑. [08]
- 对形如 "能迭代到边界" 的对象计数, "能迭代" 是一个动态的限制, 但 "不能迭代" 是一个静态的限制, 可能更好算. [08] [17]
- \(\sum a_ib_i\overset{?}{=}0\), 有没有可能是在判断向量共线? [09]
- 随机序列上的询问可能有很简单的支配对, 而且数量级不大, 注意观察. [0A]
- 最短路询问 "到底要不要建图跑最短路算法" 其实是很关键的问题, 尝试一些归约. [0B]
- 长剖/重剖本质上是找到 "若有一个儿子满足某个性质, 则必然是这个特殊儿子", 这个 "特殊性质" 可以拿来保证复杂度, 也可能单纯就是题目需要. [0E]
- 两种对象互相匹配的问题, "\(A\) 去找 \(B\)" 和 "\(B\) 去找 \(A\)" 同样值得尝试, 尽管可能反直觉. [16]
- 贪心结论可能让元素的动态贡献变为静态, 如果动态贡献没办法维护也可以反过来想想贪心结论. [18]
- 数轴上双向不碰撞运动, 可以写成序列 DP (是个线性变换), 引入碰撞时间之类的就可以上 DDP. [1A]
- 近似解, 兄弟! [1B]
- \(01\) 矩阵, 要求一个 "\(0\) 的一个角方向上不能有 \(1\)" 之类的东西, 最后的合法矩阵可能存在值的轮廓线. [1C]
- 操作序列和计数对象建立双射, 然后就能数操作序列了. [1D]
- 再相信一次出题人的特殊性质吧! [29]
- 匹配判定记得 Hall, Hall 的时候注意观察能否只做区间判断. [2C]
- "在一个集合中允许任意换走几个, 最小化代价", 如果换入的东西很容易贪心 (例如一定用未入选的代价最少的物品), 是否可以直接钦定贪心结果 (一段最优前缀必选)? [31]
- 多限制计数, 能否在最外层手动构造容斥关系, 内层只对容斥后限制较少的对象计数? [34]
- 多变量关系建议在图上讨论. 没有为什么, 有股劲儿. [3F]
Tricks
技巧, 让 motivation \(\to\) solution 这段路不完全需要自己走.
- \(k\) 维偏序, 去他妈的 \(\text{polylog}\), 不如用
std::bitset做 \(\mathcal O(n^2k/\omega)\). 还可以配合四毛子分块做高维偏序上的信息查询. [07] - 经典永流传: 树形拓扑限制, 贪心向爹合并. (用的时候不太自信是怎么回事?) [13]
- 若提供 "集合合法性" 类的交互接口, 可以通过前缀询问求出第一个合法位置. [16]
- 有根树点分治, 分治中心到根的高代价信息可以跳上层分治中心合并. [1F]
- 计算几何, 一些相交判定问题可以通过网格划分减小检查次数, 网格宽度阈值可以倍增. [21]
- \(a_i=\min\{a_{i-1}+A(i),B(i)\}\) 这种形式的递推可以枚举前面最后一个取常量 \(B(i)\) 的位置转移. [2D]
Conclusions
普适结论, 你还记得 NOI 2021 做不起 D1T2 的伤痛吗?
- 置换自复合, 奇环内部元素不变, 偶环裂成两个等大小环. (可能在倍增中有用.) [02]
- [Monster Hunting Problem] 先按消耗值升序挑战消耗 \(\le\) 回复的怪兽, 再按回复值降序挑战其余怪兽 [07]
- 二分图中, 最大独立集 \(=\) 最小点覆盖 \(=\) \(n-{}\)最大匹配 \(=\) \(n-{}\)最大流 (最小割). [1C]
Algorithms
背诵任务建议在早读时完成. (?
long double模乘
还不会写? 非常量模数时这玩意儿比 __int128 硬算快.
inline LL mul(const LL u, const LL v) {
return LL(((ULL)u * v - ULL((LD)u / MOD * v) * MOD + MOD) % MOD);
}
- 杨表
.