题解 P2630 【图像变换】
liuguangzhe · · 题解
这里是来自出题人liuguangzhe的题解。。。
“引理”：只要有解，那么必存在长度不超过4的可行解。
证明：首先显然操作之间的相对顺序是不会影响结果的，那么对于一个序列我们把
相同操作放到一起分析。不难发现执行两次C或D等价于不操作，因此若操作k次，
实际效果等价于操作k%2次，那么执行C、D的次数均不超过1。而对于A、B，由于
相反性所以至多出现一种（除了根本没变的情况），而且AAA等价于B，BBB等价于
A，故A与B加起来出现不超2次。因此，最短序列总长度不超过4。
因此本题其实是吓人的Pure Water。。。