Co2017-2018 ACM-ICPC, Asia Daejeon Regional Contest
A: 树形dp,f(i,j,0)=i子树内j深度没有被覆盖的最小花费,f(i,j,1)=i子树内覆盖部分可以延伸出j长度的最小花费
B: 4*4棋盘四子棋给定初始状态和白方最后一步,求白胜所有状态总数————暴力搜即可。
C:拓扑排序
D:记忆化搜索
E:枚举+最小割 例题:bzoj2561
F:暴力
G:暴力扫一遍
H:分类+法法塔 类似题目:bzoj5217
I:把串反过来+kmp
J:不知道怎么得出的结论:对任意点,取其相邻点集为S ( S = x | N(x)) , 然后找到邻边包含在S中的所有点T。充要条件是:|S| – min(n / 2,|T|) >= n / 2
K:构造,每次走到比边界多一格
L:3个人在3张图上走,每次可以走一条边或留在原处,求在同一时刻到达各自终点的最小花费。————对每张图设dp[i][j]为i时刻到j点的最小花费,枚举时刻相加即可,可以证j<=n3,总复杂度O((n+m)*n3)。