P8023 [ONTAK2015] Tasowanie

· · 题解

Description

给你两个数组 A 和 B，长度分别为 m 和 n。你每次操作都可以选择一个数组，拿出他的第一个元素并加入数组 C 的末尾。显然你最后会得到一个长度为 n+m 的数组 C，你需要使 C 字典序最小。

### 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)

直接暴力模拟复杂度是 O(n^2) 的，这里可以获得 70pts。

::::info[Code1]

#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)。

::::info[Code2]

#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;
//  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=len
                len 不可行   -> 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 4

1 5 2 5 4 2 2 1 5 5 1 3 4 5 5 1
*/

::::