Hobo Chen

NWERC 2015 题解

这篇博客是2015年NWERC的题解。

这套题比较简单。以及我这套题的部分标程代码无法在UVALive中得到AC,即使能在本地运行中通过全部数据。但是在cf gym中可以得到ac。

A

DFS即可,简单题。

B

2-SAT问题,首先枚举那三张牌;然后对每张牌在A/B手中视为0/1建图。

C

用类似于合并石子那样的做法,区间DP。

D

简单题。

E

也是一个DP。

F

网络流求最小割。

对于任何相邻的节点连双向边,流量为A;从源连接容量为B的单向边到所有低地;从所有高地连接容量为B的单向边到汇。

注意点在于初始不知道哪些点是要改变的,所有任何相邻节点都要连流量为A的边。

G

博弈论求SG函数。

H

数位DP。

I

比较难的一个后缀树/后缀自动机。目前还没有做出来。

J

判断点在凸包内。

值得一提的是点在多边形内的判断需要O(n),而点在凸包内的判断只需要O(log(n))。