A. 一起坐火车
树链剖分处理瓶颈和更新.
B. Complex Maze
所有点两两连线,判断与简单多边形的相交关系建图,求最短路。
C. Phalanx Dance
Splay 做区间更新和子树拆除与合并
D. Big Matrix
推算一下可O(1)
计算
E. 走,做核酸去!
一天只有1440分钟,枚举每个核酸点的每一分钟按题意计算时间.
F. 黑白跳棋
搜索,预处理出所有棋局的必胜、必败状态。
G. 华容道
首先为了棋子能够移动,空格至少先移动到棋子的周边位置,然后根据棋子的相对位置分情况枚举可能的最优路线,最后取最小值.
可通过镜像、旋转等方式把数据初始化为固定情况减少分类讨论.
H. 好吃的甜品
用状态记录每个甜品店是否到访过,对每个状态都能够计算出最短路径,逐一检查不同的方案下甜品的数量是否满足要求。
O(n2logn) 也能过。
I. 共现的数
二进制记录每个整数出现的集合,暴力枚举所有的数是否和x、y共现。
J. Fibonacci Cane
前缀和
K. Substrings Same as Prefix
基于KMP的next数组可得每个位置为结尾的所有与前缀相等的后缀,加一个dp可累加避免每次迭代.