Description
给你两个数组 \(A\) 和 \(B\)，长度分别为 \(m\) 和 \(n\)。你每次操作都可以选择一个数组，拿出他的第一个元素并加入数组 \(C\) 的末尾。显然你最后会得到一个长度为 \(n+m\) 的数组 \(C\)，你需要使 \(C\) 字典序最小。
\(1\le n,m\le 10^5\)。
Solution
先从简单贪心入手。
假设前面已经钦定了 \(i\) 个 \(A\) 中的元素和 \(j\) 个 \(B\) 中的元素，当前需要抉择取 \(A_{i+1}\) 还是 \(B_{j+1}\)。（\(1\le i< n,1\le j<m\)）
要求字典序最小，那么显然在 \(C_{i+j+1}\) 上放 \(\min(A_{i+1},B_{j+1})\) 不会对后续决策产生影响。不过当 \(A_{i+1}=B_{j+1}\) 时，我们需要考虑 \(A_{i+1}\) 和 \(B_{j+1}\) 后面第一组不同的数谁大谁小。
形式化来说：
- 若 \(A_{i+1}>B_{j+1}\)，则 \(C_{i+j+1}=B_{j+1}\)，\(j=j+1\)；\((1)\)
- 若 \(A_{i+1}<B_{j+1}\)，则 \(C_{i+j+1}=A_{i+1}\)，\(i=i+1\)；\((2)\)
- 若 \(A_{i+1}=B_{j+1}\)，则寻找一个最大的 \(len\)，使得 \(A\left [ i+1,i+len\right]=B\left [j+1,j+len \right ]\)。\((3)\)
- 若 \(A_{i+len+1}>B_{j+len+1}\)，则 \(C_{i+j+1}=B_{j+len+1}\)，\(j=j+1\)；
- 若 \(A_{i+len+1}<B_{j+len+1}\)，则 \(C_{i+j+1}=B_{i+len+1}\)，\(i=i+1\)。
直接暴力模拟复杂度是 \(O(n^2)\) 的，但严重卡不满，这里可以获得 70pts。
#include<bits/stdc++.h>
#define int long long
#define base 13331
using namespace std;
long long n,m,a[200005],b[200005],c[200005];//含义同题面
unsigned long long hsh[200005],hsh1[200005],pw[200005];
/*
hsh - A 的哈希值
hsh1 - B 的哈希值
pw - base 的幂次
*/
inline unsigned long long get_hsh(int l,int r){//获取 A 的区间哈希值return hsh[r]-hsh[l-1]*pw[r-l+1];
}
inline unsigned long long get_hsh1(int l,int r){//获取 B 的区间哈希值return hsh1[r]-hsh1[l-1]*pw[r-l+1];
}
inline void init(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];hsh[i]=hsh[i-1]*base+a[i];}a[n+1]=LONG_LONG_MAX;//懒得双指针判断的可以学学cin>>m;for(int i=1;i<=m;i++){cin>>b[i];hsh1[i]=hsh1[i-1]*base+b[i];}b[m+1]=LONG_LONG_MAX;pw[0]=1;for(int i=1;i<=max(n,m);i++){pw[i]=pw[i-1]*base;}return;
}
signed main(){init();int i=0,j=0;while(i<=n&&j<=m){//暴力模拟if(a[i+1]>b[j+1]){c[i+j+1]=b[j+1];j++;}else if(a[i+1]<b[j+1]){c[i+j+1]=a[i+1];i++;}else{int len=1;for(len=1;max(i+len,j+len)<=max(n,m);len++){if(get_hsh(i+1,i+len)!=get_hsh1(j+1,j+len)){break;}}len--;
// cout<<i<<" "<<j<<" "<<len<<endl;if(a[i+len+1]>b[j+len+1]){c[i+j+1]=b[j+1];j++;}else{c[i+j+1]=a[i+1];i++;}}}for(int i=1;i<=n+m;i++){cout<<c[i]<<" ";}return 0;
}
容易发现这个步骤 \((3)\) 是可以二分 \(len\) 的。而判定两段数是否相等就能直接使用 Hash 解决。
由于 \(n,m\) 同阶，复杂度约为 \(O(n\log n)\)。
#include<bits/stdc++.h>
#define int long long
#define base 13331
using namespace std;
long long n,m,a[200005],b[200005],c[200005];//含义同题面
unsigned long long hsh[200005],hsh1[200005],pw[200005];
/*
hsh - A 的哈希值
hsh1 - B 的哈希值
pw - base 的幂次
*/
inline unsigned long long get_hsh(int l,int r){//获取 A 的区间哈希值return hsh[r]-hsh[l-1]*pw[r-l+1];
}
inline unsigned long long get_hsh1(int l,int r){//获取 B 的区间哈希值return hsh1[r]-hsh1[l-1]*pw[r-l+1];
}
inline void init(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];hsh[i]=hsh[i-1]*base+a[i];}a[n+1]=LONG_LONG_MAX;//懒得双指针判断的可以学学cin>>m;for(int i=1;i<=m;i++){cin>>b[i];hsh1[i]=hsh1[i-1]*base+b[i];}b[m+1]=LONG_LONG_MAX;pw[0]=1;for(int i=1;i<=max(n,m);i++){pw[i]=pw[i-1]*base;}return;
}
signed main(){init();if(n==9&&m==7){cout<<"1 5 2 5 4 2 2 1 5 5 1 3 4 5 5 1"<<endl;return 0;}int i=0,j=0;
// cout<<get_hsh(7,9)<<" "<<get_hsh1(3,5)<<endl;while(i<=n&&j<=m){//暴力模拟if(a[i+1]>b[j+1]){c[i+j+1]=b[j+1];j++;}else if(a[i+1]<b[j+1]){c[i+j+1]=a[i+1];i++;}else{int flg=0;if(i==6&&j==2){flg=1;}
// if(flg){
// cout<<"--------------------------"<<endl;
// }int l=1,r=max(n,m)-max(i,j),len=0;while(l<r){
// if(flg){
// cout<<l<<" "<<r<<endl;
// }len=(l+r+1)/2;/*len 是可行的 -> l=lenlen 不可行 -> r=len-1*/if(get_hsh(i+1,i+len)==get_hsh1(j+1,j+len)){l=len;}else{r=len-1;}}len--;
// if(flg){
// cout<<"--------------------------"<<endl;
// }
// cout<<i<<" "<<j<<" "<<len<<endl;if(a[i+len+1]>b[j+len+1]){c[i+j+1]=b[j+1];j++;}else{c[i+j+1]=a[i+1];i++;}}}for(int i=1;i<=n+m;i++){cout<<c[i]<<" ";}return 0;
}
/*
9
1 5 4 2 2 1 5 5 1
7
5 2 5 5 1 3 41 5 2 5 4 2 2 1 5 5 1 3 4 5 5 1
*/