期望dp

2017-ICPC-jakarta

 2020.06.27 22:51  2023.09.01 18:14  ACM  multiset  期望dp  状态压缩  容斥原理 󰈭 3734字

B 动态维护两个序列之间的最小差值尝试将图二分染色。如果不能二分染色，那么两人无论初始处于什么位置一定都有某种策略走到同一个节点；如果能够二分染色，题目则等价转化求$min{|u - v|}, u∈A, v∈B$，并且支持在线修改，这种情况是我们要着重处理的问题。为此，利用multiset作为一个有序容器来实现这个功能。 ...