网站首页下拉广告,wordpress网店插件,农家院做宣传应该在哪个网站,胶州市网站建设Description 给定两个数字串A和B#xff0c;通过将A和B进行二路归并得到一个新的数字串T#xff0c;请找到字典序最小的T。Input 第一行包含一个正整数n(1n200000)#xff0c;表示A串的长度。第二行包含n个正整数#xff0c;其中第i个数表示A[i](1A[i]1000…Description 给定两个数字串A和B通过将A和B进行二路归并得到一个新的数字串T请找到字典序最小的T。 Input 第一行包含一个正整数n(1n200000)表示A串的长度。 第二行包含n个正整数其中第i个数表示A[i](1A[i]1000)。 第三行包含一个正整数m(1m200000)表示B串的长度。 第四行包含m个正整数其中第i个数表示B[i](1B[i]1000)。 Output 输出一行包含nm个正整数即字典序最小的T串。 题解利用后缀数组比较字典序大小同 BZOJ 1692 #include bits/stdc.h
#define setIO(s) freopen(s.in, r, stdin)
#define maxn 4000000
using namespace std;
int n, m, tot;
int arr[maxn], height[maxn], A[maxn];
namespace SA
{int rk[maxn], tp[maxn], sa[maxn], tax[maxn]; void qsort(){for(int i 0; i m ; i) tax[i] 0;for(int i 1; i n ; i) tax[rk[i]]; for(int i 1; i m ; i) tax[i] tax[i - 1];for(int i n; i 1 ; --i) sa[tax[rk[tp[i]]]--] tp[i]; }void build(){for(int i 1; i n ; i) rk[i] arr[i], tp[i] i;qsort(); for(int k 1; k n ; k 1){int p 0;for(int i n - k 1; i n ; i) tp[p] i; for(int i 1; i n ; i) if(sa[i] k) tp[p] sa[i] - k;qsort(), swap(rk, tp), rk[sa[1]] p 1;for(int i 2; i n ; i){rk[sa[i]] (tp[sa[i - 1]] tp[sa[i]] tp[sa[i - 1] k] tp[sa[i] k]) ? p : p; }if(n p) break; m p; }int k 0;for(int i 1; i n ; i) rk[sa[i]] i;for(int i 1; i n ; i){if(k) --k;int j sa[rk[i] - 1]; while(arr[i k] arr[j k]) k;height[rk[i]] k; } }
};
int main()
{// setIO(input); int a, b; scanf(%d,a); for(int i 1 ; i a; i) scanf(%d,arr[n]); arr[n] 2000;scanf(%d,b);for(int i 1 ; i b; i) scanf(%d,arr[n]); m 3000; SA::build(); int l 1, r a 2; for(int i 1; i a b ; i){ if(l a) printf(%d , arr[r]); else if(r n) printf(%d ,arr[l]); else if(SA::rk[l] SA::rk[r]) printf(%d ,arr[l]); else printf(%d ,arr[r]); }return 0;
}转载于:https://www.cnblogs.com/guangheli/p/10994647.html
