2020.5.9 2018-2019 ACM-ICPC, Asia Xuzhou Regional Contest

没有专题

没有比赛

都是补比赛的题

2018-2019ACM-ICPC，Asia Xuzhou Regional Contest L.Rikka with grid graphs 分类：轮廓线dp、传递闭包

题意： 六十组数据 一个大小不超过6*6的网格图（$n \times m$ 个点，不超过$2n \times m - n - m$条边），每条边都可以没有。定义定向操作是给网格图的每一条边定一个方向，问有多少种不同的定向方法使定向后图中不存在有向环

题解：

网格图、连通性两个关键词提示轮廓线dp，观察一下性质发现没法用括号表示法，只能用传递闭包记录状态，跑一下可以发现单步有效状态数极限在1万左右，复杂度O(49*4*10000*36)如果是60组极限数据时间非常卡，但是好像默认多组数据的话不会都出极限数据？

2018-2019ACM-ICPC，Asia Xuzhou Regional Contest M.Rikka with Illuminations

题意：一个凸n边形，外面有m个灯塔，问最少需要多少个灯塔使多边形每条边都能被覆盖

题解：n m都是1000，1000组数据，可以暴力过。暴力即通过叉积判断每条边和每个灯塔的照射关系，确定每个灯塔的范围，然后$m^2$dp一下。O(nlogn)做法：求凸多边形重心，然后得出边的极角范围，然后每个灯塔可以O(logn)求出和重心连线所经过的两条边，以这两条边为边界二分即可。后面dp部分先对每个点倍增一下，dp就可以O(nlogn)

没有专题

没有比赛

没有专题

没有比赛

推荐插头dp，可以直接看cdq的ppt