mengbierr

一个蒟蒻的博客

7月23

Codeforces gym 102007 2018 Benelux Algorithm Programming Contest (BAPC 18)

A:略

B:略

C:略

D:记忆化搜索,注意无法区分具有传递性,所以搜索时两个点同时出现就把它们放到同一个并查集里,如果两个点在同一个并查集里就不要继续搜索

E:先考虑所有元素都不同,f[i]表示考虑前i小的位置上合法序列的方案数,每次用总排列数-不合法的排列数,枚举第一个不合法的位置转移,发现有相同的稍加修改就行了。(赛时那个做法可能是没救了…)

F:略

G:略

H:做变形的dijkstra,每个点两个状态存从这个点到终点是第一步想尽可能小/大(1/0)的距离,将边反向,从终点到起点,从0到1时可以随意转移,从1到0必须与当前点相连的所有点都转移后才能转移。(道理可能与博弈问题类似?)

I:二分+网络流,一侧点数只有10个,等价状态可以合并,压缩成1024个点

J:略

K:ans=n/2上取整,dfs一遍,按叶子节点访问顺序排序,将v_iv_{i+n/2}配对。

L:无

M:无

发表评论

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