前言
困了一下午, 仅仅只搞懂了个大概, 我们赶紧把这些题补了, 冷静一点
思路
观察大样例可以发现, 答案好像都不大
容易证明的是先用最多 \(n\) 次关闭所有开关, 然后在 \(2n\) 次打开每个灯, 这样一定不超过 \(3n\) 次就可以成功的打开所有灯
那么我们考虑以这个为突破口, 枚举操作次数解决问题
那么考虑对于一种操作次数 \(m\) , 怎样判断其是否可行
首先你需要知道操作的小转化 : 对于每个 \(2\) 操作, 我们发现其相当于一个 \(\oplus\) , 那么我们可以利用 \(\oplus\) 的交换律和自反律, 得出 \(a\) 的初始状态和 \(b\) 的变换是互相不影响的两个部分, 下面我们只考虑 \(b\) 变换的异或积
稍微观察一下第 \(i\) 次操作的性质, 你发现最终第 \(i\) 次操作会覆盖到 \(m - i + 1\) 大小的区间, \(\rm{belike}\) :
那么对于 \(m\) 次操作, 相当于一串长度为 \(1, 2, 3 \cdots m\) 的区间取反
这个时候问题就更加符合中国宝宝的体质, 每次操作次数 \(m \gets m + 1\) , 转化过来仅仅是多了一个长为 \(m + 1\) 的区间取反
这个时候看似没法处理了, 但是你发现即使是多组测试数据, 但是 \(n\) 都是相通的, 进一步思考可以发现, 我们可以考虑来一个全局的预处理
考虑令 \(f_{i, S}\) 表示第 \(i\) 次操作能否转化到 \(S\) , 其中 \(f_{i, S} \in \{0, 1\}\)
容易发现每次其实就是从 \(f_{i - 1, S^{\prime}}\) 通过新增加一个长为 \(i\) 的区间取反变换而来的
我们可以容易的列出柿子
\[f_{i, S} \gets f_{i - 1, S^{\prime} }, \lvert S^{\prime} \rvert = i \]即可
感觉有点混乱, 我们再理一遍思路
首先你观察操作, 发现 \(a\) 的初始状态和 \(b\) 的变换是两个部分, 可以分开讨论
观察大样例发现答案很小, 我们考虑证明出答案 \(\leq 3n\) , 然后枚举答案(及操作次数)
假设操作次数为 \(m\)
稍微观察一下第 \(i\) 次操作的性质, 你发现最终第 \(i\) 次操作会覆盖到 \(m - i + 1\) 大小的区间, \(\rm{belike}\) :
那么对于 \(m\) 次操作, 相当于一串长度为 \(1, 2, 3 \cdots m\) 的区间取反
这个时候问题就更加符合中国宝宝的体质, 每次操作次数 \(m \gets m + 1\) , 转化过来仅仅是多了一个长为 \(m + 1\) 的区间取反
然后我们考虑全局预处理
结束
实现
难点不在实现
总结
对于 \(01\) 串的操作, 我们考虑用数学语言表示
善于利用运算律简化问题
当观察到答案较小时, 考虑
- 分讨答案
- 枚举答案检查
玩样例可以找到一些有用的性质
如果多组测试数据有相通之处, 也许你可以全局的处理?
感觉这个题到紫了, 很难, 跨段做题其实是很影响心态的, 因为连我自己都不知道为什么可以这样想
标签：P9017,次数,取反,Lights,USACO23JAN,答案,区间,操作,考虑 From： https://www.cnblogs.com/YzaCsp/p/18628625