[eJOI2018] AB Strings 题解

FFTotoro · 2024-08-30 09:59:27 · 题解

考虑到一个简单的性质：如果一个串中有连续的两个相同的字符，那么可以将它们视为一个字符；于是最后两个串都形如 \texttt{abab}\ldots\texttt{abab}，我们的目标是让两个串变为一个 \texttt{a} 一个 \texttt{b}。

接着分类讨论，对于两个字符串首字母相同的情况（不妨设为 \texttt{a}），最优的做法是选择一个串的 \texttt{ab} 与另一个串的 \texttt{a} 交换；这样可以让总长度减少 2；由此可得应在其中一个字符串中选择长度为奇数的前缀，另一个字符串中选择长度为偶数的前缀；类似的，如果首字母不同，那么应选择两个长度为奇数的前缀。

对于边界情况：其中一个字符串长度为 1，直接暴力做，此时每次只能减少一个字符；两个字符串长度均为 2，此时也是每次只能减少一个字符。对于这些情况，字符串的长度可能都很小——于是在上面的操作中可以尽量让两个字符串的长度平均。

参考代码（GNU C++17）：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> q[2],r;
inline void add(int p,pii x){
  if(!q[p].empty()&&q[p].back().first==x.first)
    q[p].back().second+=x.second;
  else q[p].emplace_back(x);
}
inline void op(int x){
  pii a=q[0].back(); q[0].pop_back();
  int c=0;
  for(int i=x;i;i--){
    pii y=q[1][q[1].size()-i];
    add(0,y),c+=y.second;
  }
  r.emplace_back(a.second,c);
  while(x--)q[1].pop_back();
  add(1,a);
}
int main(){
  ios::sync_with_stdio(false);
  string s,t; bool f=false; cin>>s>>t;
  for(int i=s.length()-1;~i;i--)
    add(0,make_pair(s[i]&1,1));
  for(int i=t.length()-1;~i;i--)
    add(1,make_pair(t[i]&1,1));
  if(q[0].size()>q[1].size())
    swap(q[0],q[1]),f=true;
  if(q[0].back().first==q[1].back().first){
    if((q[1].size()-q[0].size()&3)==3)
      op(q[1].size()-q[0].size()+1>>1);
    add(0,make_pair(!q[0].back().first,0));
    op(q[1].size()-q[0].size()+1>>2<<1|1);
  }
  else if(q[1].size()-q[0].size()>2)
    op(q[1].size()-q[0].size()+1>>2<<1|1);
  while(q[0].size()>1||q[1].size()>1)op(1);
  if(f)for(auto &[x,y]:r)swap(x,y);
  cout<<r.size()<<endl;
  for(auto [x,y]:r)cout<<x<<' '<<y<<'\n';
  return 0;
}