CSG-CPC
Home Page

HNCPC2022简要题解

Update Time: 2023-04-02 16:19:52     Recent Editor: CSGrandeur     Create Time: 2023-04-02 12:46:01     Creator: CSGrandeur    


点击打开题目列表

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可累加避免每次迭代.