[AGC052A] Long Common Subsequence 题解

FFTotoro · 2022-10-24 17:34:10 · 题解

设本题构造出的字符串为 T，那么

• T=\begin{matrix}\underbrace{00\cdots0}\\N\cdot0\end{matrix}+\begin{matrix}\underbrace{11\cdots1}\\N\cdot1\end{matrix}+0

这里的 + 表示将两个字符串头尾相连接。

证明构造的字符串是合法的：

令 a_1,a_2,\ldots,a_N 表示字符串 S 中 0 的位置，那么 S+S 中 0 的位置就是 a_1,a_2,\ldots,a_N,a_1+2N,a_2+2N,\ldots,a_N+2N。

可以得出，S+S 中第 N 个 0 与第 2N 个 0 的距离为 2N，即它们中间有 N 个 1，故我们的方法是正确的。

放代码：

#include<iostream>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n; cin>>n; string s[3];
    for(int i=0;i<3;i++)cin>>s[i];
    for(int i=1;i<=n;i++)cout<<0;
    for(int i=1;i<=n;i++)cout<<1;
    cout<<0<<endl;
  }
  return 0;
}