csp-s模拟109

　　这场考试状态是极差，也因而无畏地打下了三个乱搞。然而这场确实挺乱搞。T1状压但我没优化而选择循环展开，T2打$bitset$随机化（考场上打的有问题不是随机但也能A），T3贪心骗分。但是因为状态实在太差，T1的滚动数组忘了清空就WA0了。不过也算是一次乱搞的有意义的实践。

T1：

　　对每一层的点到终点的路径奇偶状态压缩，按层转移。理论复杂度$O(M*2^K*K^2)$。可以把边也状压一下，转移时直接相与原状态和某一点的边，然后$lowbit$计数出这一点的奇偶情况。

T2：

　　并不会证。

T3：

　　这题其实感觉有点熟悉，因为之前有类似问题，只不过没有$S$的限制。同样是贪心问题。

　　考虑如何发挥一个灭火器的最大效用。一定是让一个灭火器恰好覆盖在没有被覆盖的点的边界处，也就是距离没有被覆盖的点恰好$K$。对于深度大于$K$的点一定是由其祖先覆盖，深度小于等于$K$的点由根覆盖。记录距离点$i$恰好$j$的没有被覆盖的点的数量$f[i][j]$，以及距离点$i$恰好$j$的还未利用的灭火器的次数（灭火器剩下的）$g[i][j]$。合并子树便可以维护这两个数组。在每一个节点，首先处理子树内多余的灭火器与未覆盖的点，只让距离恰好为$K$和$K-1$的灭火器与点配对。这样做贪心最优。考虑会有灭火器与点在同一棵子树内，若其距离小于$K-1$，那么在父亲（祖先）处处理是不影响的（重叠2的距离仍旧小于等于$K$），但距离为$K-1$时就得在子树内处理。子树内处理完了，需要检查距离这个点$x$恰好$K$的未覆盖的点，需要$x$为之覆盖。最终根节点特殊处理，把距离小于等于$K$的灭火器和点配对，并在根加灭火器覆盖掉剩余的点。

巴特西

csp-s模拟109

T1：

T2：

T3：

最新文章

热门文章