A. Puzzles
B. Routine Problem
- 考虑\(\frac{a}{b}\)和\(\frac{c}{d}\)的大小关系，适配后就是分数的运算。
C. Quiz
- 按\(k\)将\(n\)个问题分段，那么在没有分数翻倍的情况下最大题数为\[(k-1)\lfloor\frac{n}{k}\rfloor+n\%k\]
- 若\(m\le (k-1)\lfloor\frac{n}{k}\rfloor+n\%k\)，则最大分数就为\(m\)，否则翻倍的机会放到前面的若干段上。
D. Book of Evil
- 问题转化为计算每个点到\(p_i\)的最大距离，若距离大于\(d\)，显然不会是问题要的点。
- 最大距离两遍\(dfs\)即可。
E. Divisor Tree
- 每个\(a_i\)的点的父节点只会是根节点或者其他\(a_j>a_i\)的点上。
- 所以将\(a[]\)从大到小排序后，暴力建树，时间复杂度\(O(n!)\)。
F. GCD Table
- 模线性方程合并。
- 在合并过程中，需要注意过程变量会超\(long\ long\)，一种解决办法是快速乘，一种是利用题目解的范围在\(10^{12}\)内，合并时使用较小的模数。
G. Optimize!
- 问题相当于对于\(a\)每个长为\(len\)的连续子序列，判断是否存在\(b\)一种排列，使得对应位置\(a_i+b_i\ge h\)。
- 如果将\(b[]\)从小到大排序，每个\(a\)的连续子序列从大到小排序，此时就是最优匹配。
- 考虑单个\(a_i\)，每个\(a_i\)都存在一个最小的\(b_j\)使得和大于等于\(h\)，也就是比\(a_i\)大值至少有\(j-1\)，否则\(a_i\)会导致当前的子序列不合法。
- 最后就是线段树用值(排名)建树，维护长为\(len\)的区间，区间覆盖，查询全局最小值。
