mengbierr

一个蒟蒻的博客

7月23

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)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注