专栏文章

题解：P9393 紫丁香

FFstAutoMaton
P9393题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minwo0mo
此快照首次捕获于
2025/12/02 09:34
3 个月前
此快照最后确认于
2025/12/02 09:34
3 个月前
查看原文

P9393 紫丁香

一道每一步都很简单但拼在一起就较为困难的题。
首先观察询问发现是查询二进制下最大值，非常套路的可以从高到低枚举每一位是否选，加上之后 check 一遍是否合法。（其它题解这里说是二分但我感觉不太一样，毕竟这里直接二分是没有单调性的（？）
先考虑对于单个询问怎么做。观察枚举出来的答案，那些为 0 的位置可以随意处理，为 1 的位置就代表这个位置在最后的若干个操作中一定是一个 1 和若干个 -。这启示我们倒着考虑操作，从答案往初始状态推导。
假设当前我们要保证集合 SS 中的位置全部是 1，其他位置任意。枚举一个操作，分类讨论一个钦定为 11 的位置在经过这次还原之后的状态。
下文设这一轮选择的操作的字符串为 TT，考虑的位置编号为 xx。
  1. Tx=T_x= 1
    那么在之后的还原过程中这一位是什么其实已经不重要了，可以从 SS 中删除 xx。
  2. Tx=T_x= 0
    那么这个位置一定是 0，所以这种情况的 TT 一定不能选择。
  3. Tx=T_x=-
    这个操作不会对最终的这一位产生影响，所以不变化。
因此我们得到了一个较为暴力的做法，每一次暴力枚举操作，进行更改。由于这样操作到无法操作的状态是唯一的，最终合法的条件就是 SS 为询问串中为 1 的位置的集合的子集。实现较优秀的话或许是 O⁡(nmq)\operatorname{O}(nmq) 的。
我们考虑对上述算法进行优化。设 gSg_S 表示集合 SS 进行任意一个操作能将那些元素从 SS 中删除，hSh_S 表示集合 SS 中的位置不为 0 的那些操作中 1 的位置的并，可以发现 gg 就是 hh 的高位后缀或。
于是对于一个 SS，只需要每次将 gSg_S 从 SS 中删去即可。
接着考虑多组询问。可以预处理 fSf_S 表示 SS 能操作到的集合大小最小的集合是什么，转移直接删去 gSg_S 即可，时间复杂度 O⁡(nm+m×2m)\operatorname{O}(nm+m\times 2^m)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...