「琐记」NOIP 2020 考前
NOIP 考前听到的一些算法，如果 NOIP 失利，这些算法可能这辈子也学不到了……算是留下一点点纪念吧…
分治乘法
\((A \times 10^{base} + B) \times (C \times 10^{base} + D)\)
= $ A C 10^{base + base} + (AD + BC) 10^{base} + BD$
= $ A C 10^{base + base} + ((A + B)(C + D) - (AC + BD)) 10^{base} + BD$
复杂度为 \(\mathcal{T}(n) = 3 \times \mathcal{T}(\frac{n}{2}) + \mathcal{O}(n) = \mathcal{O}(n^{\log_2{3}}) \approx \mathcal{O}(n^{1.58})\)
分数规划例题
给出一张无向图，每个边两种权值 \((a, b)\) ，定义一棵树的权值为
\[\frac{\sum_{i \in T}\limits{a_i}}{\sum_{i \in T}\limits{b_i}}\]
求最大权值。
二分答案是什么，设二分的值为 \(L\)。
\(\frac{\sum_{i \in T}\limits{a_i}}{\sum_{i \in T}\limits{b_i}} \ge L\)
\(\sum_{i \in T}\limits{a_i} \ge L \times \sum_{i \in T}\limits{b_i}\)
\(\sum_{i \in T}\limits{(L \times b_i - a_i)} \le 0\)
将权值赋值为 \(L \times b_i - a_i\) 求最小生成树是否小于 \(0\)，即可。
[国家集训队]阿狸和桃子的游戏
https://www.luogu.com.cn/problem/P4643
《一道防AK的好题》 and 《卡常数》
强制在线，数据加密对解题有帮助
CDQ 分治例题
COGS 577 蝗灾
组合数取模
- 递推一行 / 一列 考虑展开组合数通项公式，线性递推一行 / 一列
- 预处理阶乘，阶乘逆。
- Lucas 定理
- 计算 \(n!\) 中素数 \(p\) 的次数 :
calc(n) = n / p + calc(n / p) - 非素数
CRT合并。
第 k 小子集和
给出一个大小为 \(n\) 的集合，定义子集权值为子集元素之和，求第 \(k\) 小子集和。 \(n \le 30\)，\(k < 2^{n}\) meet in the middle。暴力求出两边 \(2^{15}\) 个值，双指针合并。
BZOJ ISN
给出长度为 \(n\) 的序列 \(A\) ，如果 \(A\) 不是递增序列，需要删除一些数字，直到为递增序列，问方案数 \(98244353\)。 动态规划 + 树状数组 + 容斥原理
Pilling Up
NULL.