A. 12强赛
C语言基础
B. 方格填数
判断左上方和右下方可填数都不低于格子数，就能够构造一个解。
C. Average of Two Numbers
因为给出的数据有序，那么枚举数字，左右往中间异步可以 O(n2) 得解。
O(n2logn) 也能过。
D. Sum Them
除法要用逆元。
方法1：整数裂项
例：
f(98,3) = 1 × 2 × 3 + 2 × 3 × 4 + ... + 98 × 99 × 100
其可以转换表达为：
- 1 × 2 × 3 = (1×2×3×4−0×1×2×3)/4
- 2 × 3 × 4 = (1×2×3×5−1×2×3×4)/4
- …
- 98 × 99 × 100 = (98×99×100×101−97×98×99×100)/4
相加之后，相邻项抵消，最终得到
f(98,3) = 98 × 99 × 100 × 101/4
方法2：预处理 n!与逆元 ，直接计算
初始化第一项为 fact(m)，之后每一项乘后一个数，除最前一个数（乘逆元），累加求和。
E. Not the Only Tree
- 一棵二叉查找树任意子树的树根结点一定比其子孙结点更先插入
- 在左子树结点、右子树结点分别保持正确顺序的前提下，左子树任意结点在右子树任意节点之前或之后没有影响。
设 n 个结点构建一棵二叉查找树的排列个数为 f(n)，其左子树结点个数为 x， 右子树结点个数为 y，则左、右子树结点互相穿插的情况数是 x + y 中选 x 或 y 个的组合数。
$f(n) = f(x) * f(y) * C_{x+y} ^ {x} $
递归可求解。
F. 最大的数
从左往右，每个数优先交换d距离内最大值，让高位尽可能大。对于多个数交换多个相同的最大值，较大的交换较靠前的最大值。
如 213997 ，2和1都可与9交换，通过以上方式实现把2与前面的9交换，1与后面的9交换。
对每个数，将后面距离d内的数放入0~9的栈，从9开始找不为空的栈，即找该数后面 d 范围内还有没被预定的最大的数，标记预定，出栈。
第二遍从右往左，每个被预定的数，往左 d 范围内预定该值的数入优先队列，队列优先更小的值出队与当前位置交换。
G. 洞穴探宝
把“X”与“@”当作结点建图，边为通过“.”能够直接连通的结点。以“当前结点”+“遇到过的结点状态压缩”为状态DP。
H. Circle Intersection
三维向量计算，可以得到四个交点，处理交点内外关系求出交线长度。
I. 戴森球计划
KD-Tree 范围和，传统方形区域换成球形，写法类似，要处理下球与立方体是否相交的判断。
对每个位置二分枚举半径，更新答案。剪枝：当前最优值得到的质量不足的话则跳过该恒星计算。
数据随机，适当剪枝也可以用其他奇技淫巧水过去。
J. String Set
后缀自动机，每个字符串插入之前重置结束位置，字符串插入之后对字符串所在DAG的节点+1，查询时直接遍历DAG输出结束位置记录的数量即可。
对于删除操作，考虑到操作次数比较少，一种比较容易实现的方式是直接在后缀自动机的DAG上记录下来能够到达当前节点的字符串都包括哪些，找到这些字符串后在对应的DAG节点上-1。
K. 双排积木
轮廓线DP。
首先可以预处理 2 × 2 × 2 的所有不同的摆放（不一定填满）情况：
- 枚举每种单个块在 2 × 2 × 2 的摆放方式，对每种摆放方式编号;
- 利用枚举得到的所有单个块摆放方法，回溯枚举所有组合，对摆放方式的编号组合排序作为最小表示去重。
进行DP时，要排除处理上方1 × 2 和 左方 1 × 2 时能够覆盖到的情况以避免重复计数，可以在预处理第一步只保留同时覆盖了左与上，或覆盖了右下1 × 2 的积木方位。
对每个问题，考虑当前 2 × 2 × 2 区域，枚举所有预处理的摆放组合，只对左上的 1 × 2 填满的情况进行状态转移，处理最后一列时需要上方也填满。