专栏文章

题解：P10360 [PA 2024] Desant 3

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

文章操作

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

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

[PA 2024] Desant 3

好怪的数数，不过这种套路好像挺常见（？
和 P9393 的想法有点像，可以看一下。
首先可以发现这个题的数据范围及其古怪，不是超级 dp 就应该是一些胡乱的复杂度的做法。但这题完全没有可以 dp 的拓扑序，所以考虑状压，然后用一些奇怪手法把复杂度降下来。
枚举每个位置是 00 还是 11 显然没有什么前途，考虑按照顺序根据 mm 个操作把状态填出来。对于每一位，我们设其有 00，11，−1-1 三种状态，其中 00 表示没有准备好，11 表示已经准备好，−1-1 表示还没有确定。最终统计答案时由于一个初状态对应的末状态是唯一的，所以直接枚举为 11 的答案区间的左右端点，如果为 11 的位置全部在这个区间中并且区间中没有 00 就直接计入答案。
考虑对这个状态进行转移，设当前操作为 (x,y)\left(x,y\right)，xx 和 yy 的位置的权值分别为 a,ba,b。
  1. min⁡(a,b)≥0\min(a,b)\ge 0。
    直接模拟操作向后转移即可，这样是从 11 个状态转移到 11 个状态，不影响答案。
  2. a=−1,b=0a=-1,b=0 或 a=1,b=−1a=1,b=-1。
    考虑 a=−1,b=0a=-1,b=0 的情况。那么可以发现如果确定后的状态中这两个数全为 00 那么这一次交换还是不交换不影响答案数量与状态正确性，而一个为 11 一个为 00 时需要交换，所以直接视作交换即可，将其变为 a′=0,b′=−1a'=0,b'=-1。
    a=1,b=−1a=1,b=-1 同理。
    这时状态数不会增加。
  3. a=−1,b=1a=-1,b=1 或 a=0,b=−1a=0,b=-1
    此时无论为 −1-1 的数实际上指代的是什么都无需交换，这时状态不变，状态数不增加。
  4. a=−1,b=−1a=-1,b=-1
    这时分类讨论其真实对应的值的四种情况即可，这时状态数会变为原来的 44 倍。
考虑这样转移的复杂度，前 33 种转移显然不影响复杂度，而第 44 种转移会让状态数乘 44，−1-1 的个数减少两个。所以总时间复杂度是 O⁡(2n(m+n2))\operatorname{O}(2^n(m+n^2)) 无法通过。
考虑优化。仔细读题发现有一个非常重要的东西我们没有用上，即输出种类数对 22 取模的结果。考虑现在的复杂度瓶颈处，不难发现在转移 44 中真实数值为 a=0,b=1a=0,b=1 和 a=1,b=0a=1,b=0 两种情况在转移后的状态是相同的，可以一一对应，所以说这两种情况可以不考虑，这样就只会转移到两个状态。时间复杂度为 O⁡(2n2(m+n2))\operatorname{O}(2^{\frac{n}{2}}(m+n^2))。

评论

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

正在加载评论...