2018 ACM-ICPC Xuzhou Regional Onsite
Replay
zerol: 来了
ultmaster:
- 只做了半道题是怎么回事啊?
- 赛后发现傻逼题还不如不要发现呢。难受 QAQ~
- WF 顺位 3,岌岌可危。(然而已经没救了
- 食堂又远又不好吃。
- 出租车坑。
- 要不是这个比赛我有可能永远都不会听说矿大这个学校。
- 回想了一下这好像是第二次有教练跟来的比赛。上一次是 16 年北京。
Problem A
Solved by kblack. 00:50 (+3)
此处省略一万字。
Problem F
Unsolved. (-11)
题意:求一个字符串 S 中的非空子串 T 的数量,满足不存在 TP 是 S 的子串且 TP 和 PT 完全一致。
题解(伪):如果 P 的长度小于 T,那么 P 的最小循环节是 T 的循环节,否则 T 是 P 的循环节。后缀树上启发式合并得到出现位置集同时维护相邻两个位置的差 d。一个长度为 $l$ 的子串不计当且仅当存在 $d \le \frac l2$ 或 $l=d$,用 pb_ds 和 set 随便维护一下就能 T 到生活不能自理了。
Problem G
Solved by zerol. 01:14 (+)
题意:从给定的若干条路径中选取 k 条,使得路径交至少为 1 个点。
题解:枚举路径交的 LCA,设为 u。设有 s 条路径经过了 u,有 c 条路径的 LCA 恰好是 u,那么这个点上的计数是 $\binom{s}{k} - \binom{c}{k}$。LCA + 差分前缀和 + 预处理组合数就好了。
Problem H
Solved by kblack. 03:05 (+2)
题意:$n$ 个区间,$k$ 染色使得有 $k$ 种颜色的区间最长。
题解:扫描线,贪心,set 里扔缺的颜色和可用线段,每当颜色不够 $k$ 的时候才延迟区间染色。
Problem M
Solved by kblack & ultmaster. 02:17 (+1)
题意:$n$ 个点的凸包,在 $m$ 个点中选最小个数个,使得凸包能被照亮。
题解:求出每个灯能照亮的区间,然后就是求最小个区间能覆盖整个凸包。据说是个经典问题。数据范围很小,暴力就行。
计算几何签到,乱换上机间不仅丢了一血,还 WA 了一发。