CodeForces 1237H Balanced Reversals

2s,512MB

长度为偶数 \(n\) 的01串 \(a,b\) .

问是否可以通过至多 \(n+1\) 次如下操作将 \(a\) 变成 \(b\) .

• 选择一个偶数 \(p \le n\) ,将 \(a\) 变成 \(a_pa_{p-1}\cdots a_1a_{p+1} a_{p+2}\cdots a_n\)

若存在,输出方案.

\(T\) 组数据.

\(1 \le T \le 2000\) ,所有数据 \(n\) 的和不超过 \(4000\)

Tutorial

思考 \(a,b\) 中按形如 \(a_1a_2,a_3a_4...\) 的方式分割时,如果我们可以如下操作

• 假如当前 \(a[1\cdots i]=b[n-i+1\cdots n]\)
• 找到 \(x\) 满足 \(x \equiv 1 \mod 2\) 且 \(a_x=b_{n-i},a_{x+1}=b_{n-i-1}\)
• 翻转 \(x-1,x+1\)
• 现在 \(a[1 \cdots i+2]=b[n-i-1\cdots n]\)

总操作次数为 \(2 \cdot \dfrac n2=n\) .

发现需要00=00,01=10,10=01,11=11

如果00!=00或11!=11,那么一定无解

否则就需要额外一步将01与10转化的操作

考虑能否用1步完成所有的转化,发现总是可以通过翻转 \(a\) 或 \(b\) 的一个前缀来完成(翻转 \(b\) 的一个前缀相当于在最后翻转 \(a\) 的对应前缀).

复杂度 \(O(n^2)\)