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

没有专题

没有比赛

都是补比赛的题

题目链接

分类：轮廓线dp、传递闭包

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

题解：

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

题目链接

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

分类：计算几何、dp

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

没有专题

没有比赛

没有专题

没有比赛

题意：在0-n上的整数坐标上,有n+1个点在高度$a_0,..,a_n$形成折线，有两人分别从(0,0),(n,0)出发，保持相同高度沿这些折线移动，最终到达(n,0),(0,0)，求这个过程需要走的最小长度。500组数据，$n,a_i≤50$
分类：dp
思路：dp，记x,y,h表示从0出发的人位于区间[x,x+1],从n出发的人位于区间[y,y+1],高度为h的状态，转移时考虑相邻的x,y和高度差为1的状态转移,复杂度O($hn^2$)
题目链接

题意：n个点形成的环，两只队伍从$s1,s2$到$e1,e2$,路径长度为路径边权和（两支队伍共同走的边长度视为原来的3倍）。求纳什均衡时两队各走的路径长度（如果存在混合纳什均衡优先输出混合纳什均衡结果），5000组数据，n和边权≤50
分类：博弈-纳什均衡
题解：大概是纳什均衡的裸题。算一下两队两种选择形成的4个结果，再用来检查是否存在混合纳什均衡后，输出题目要求的解，复杂度O(n)。
题目链接

推荐插头dp，以便遇到问题可以及时跳过

可以插头dp建议直接看看cdq的ppt

链接

CF1299D 线性基题目链接