CF1906B Button Pressing 题解

FFTotoro · 2023-12-07 21:40:22 · 题解

前言

很水的 \color{Red}{^*2600}，赛时没做可惜了。

解法

将灯的 01 状态转换到异或前缀和序列 s 的角度上进行观察，考虑一次操作的意义：即交换 s 中一对相邻的元素，具体地，设进行操作的灯是 i\color{Red}(i>1)，那么异或前缀和序列中要么 s_{i-1}=0,s_i=1，要么 s_{i-1}=1,s_i=0；而进行完操作后，很显然 s_{i-1},s_i 会交换，其他元素都不会变。

又根据冒泡排序的经典结论，即在进行上述操作的情况下，能将一个上面那样的异或前缀和序列任意重排——也就是说如果 a 的异或前缀和序列与 b 的异或前缀和序列中 0 的个数相等（此时 1 个数也相等），那么 a 就可以转换为 b（即我们不需考虑元素的顺序）。

现在在考虑操作 i=1 的情况。注意到此时没有 p_{i-1} 与其进行交换，所以它直接变为 0，容易得知此时整个异或前缀和序列除了 p_1 所有元素都翻转了（即 0 变 1，1 变 0）！用这个方法可以将异或前缀和序列中 1 的个数 c 变为 n-c+1。

最终结论容易得到。

放代码（全场 Shortest）：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n; string a,b; cin>>n>>a>>b;
    auto f=[&](string s){
      int c=0,p=0;
      for(char i:s)c+=p^=i&1;
      // 异或前缀和
      return min(c,n-c+1);
      // 实际上只需考虑两者中较小值
    };
    cout<<(f(a)==f(b)?"YES\n":"NO\n");
  }
  return 0;
}