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 填满的情况进行状态转移,处理最后一列时需要上方也填满。