4278: [ONTAK2015]Tasowanie
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 75 Solved: 30
[Submit][Status][Discuss]
Description
给定两个数字串A和B，通过将A和B进行二路归并得到一个新的数字串T，请找到字典序最小的T。
Input
第一行包含一个正整数n(1<=n<=200000)，表示A串的长度。
第二行包含n个正整数，其中第i个数表示A[i](1<=A[i]<=1000)。
第三行包含一个正整数m(1<=m<=200000)，表示B串的长度。
第四行包含m个正整数，其中第i个数表示B[i](1<=B[i]<=1000)。
Output
输出一行，包含n+m个正整数，即字典序最小的T串。
Sample Input
6
1 2 3 1 2 4
7
1 2 2 1 3 4 3
1 2 3 1 2 4
7
1 2 2 1 3 4 3
Sample Output
1 1 2 2 1 2 3 1 2 3 4 3 4
HINT
Source
据说标算是后缀数组。。。但是我这种蒟蒻并不会。。于是向神犇请教了二分加哈希的做法。。
对于两个串如果当前位置上的数不同。。那显然应该输出比较小的一个。。如果相同就要比较他们之后第一个不同的位置的大小。。自己想想应该可以明白。。
然后对于这个位置我们可以二分。。然后哈希比较。。复杂度是\(O(n log(n))\)的
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll mod = 1e9+7;
const ll base = 1000;
const ll N = 200010;
long long a[N],b[N],c[N],d[N],pow[N],x,y,n,m,c1[N],d1[N],pow1[N];
ll read(){
ll x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
ll OK(ll x,ll y,ll l){
ll T1 = ((c[x+l]-c[x]*pow[l]+mod)%mod);
ll T2 = ((d[y+l]-d[y]*pow[l]+mod)%mod);
return ((T1==T2));
}
ll Query(ll x,ll y){
ll l = 0,r = min(n-x,m-y),ans = 0;
while (l<=r){
ll mid = (l+r)>>1;
if (OK(x,y,mid)) {ans = mid;l = mid+1;}
else r = mid-1;
}
return ans;
}
int main(){
n = read();
for (ll i=1;i<=n;i++) a[i] = read()-1;
m = read();
for (ll i=1;i<=m;i++) b[i] = read()-1;
pow[0] = 1;
for (ll i=1;i<=max(n,m);i++) pow[i] = pow[i-1]*base%mod;
for (ll i=1;i<=n;i++) c[i] = (c[i-1]*base+a[i])%mod;
for (ll i=1;i<=m;i++) d[i] = (d[i-1]*base+b[i])%mod;
x = 1,y = 1;
while (x<=n && y<=m){
if (a[x]!=b[y]){
if (a[x]<b[y]) printf("%d ",a[x++]+1);
else printf("%d ",b[y++]+1);
}
else {
ll l = Query(x,y);
if (x+l+1>n) printf("%d ",a[x++]+1);
else if (y+l+1>m) printf("%d ",b[y++]+1);
else if (a[x+l+1]<=b[y+l+1]) printf("%d ",a[x++]+1);
else printf("%d ",b[y++]+1);
}
}
while (x<=n) printf("%d ",a[x++]+1);
while (y<=m) printf("%d ",b[y++]+1);
}
评论 (0)
