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_i和v_{i+n/2}配对。
L:无
M:无