2018-2019 ICPC, CERC

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

$$\text{dp}_i$$表示覆盖前$$i$$个位置最少需要的单词数,显然其满足单调性.

我们枚举位置$$i$$进行DP,那么需要知道能匹配的最长单词到哪,然后将区间DP值与匹配位置前一个的转移取一个较小值.

B

按权值分成$$10$$层,维护$$10$$个动态图

分治线段树+并查集

C

爆搜$$O(40^6)$$

发现最后一层不用搜,$$O(40^5)$$

D

E

题意感觉很绕,实际上是对二维平面上的点重新编号并连边,形成一个满足连边条件的树

先按照横坐标排序,一开始选左下点,然后每次对于一棵子树,都递归地做极角排序,给他们分配对应大小的点

F

读懂题意就做完了的题目。。。难点完全在于读题

第一问:观察发现所有点在凸包上时最大团是$$3$$,否则是$$4$$

第二问:所有点在凸包上时最大团个数是$$n-2$$,否则是$$n-m$$($$m$$是凸包上的点)

第三问:按输入顺序排个序,以凸包上利润最大的点为原点极角排序,然后扫一遍就结束了

G

连通性可以用并查集维护

现在考虑怎么保证每个格子只被更新常数次

对于每行我们用一个并查集来缩点,然后每次就可以快速跳过已经更新过的区域

相邻两行的合并只发生在某一行的一段连续段的某个端点处

这样就可以保证复杂度了

H

I

观察发现满足答案的三元组只有$$N\log N$$个,所以预处理全部枚举做前缀和即可.

J

四种直角三角形统计一种,然后转四下即可.

对于一种直角三角形的统计,预处理每个字符向右相同字符的个数,然后做一些DP或者计数即可.

K

L