题解洛谷 P8023【[ONTAK2015] Tasowanie】

后缀数组。

我们对 \(A+B\) 求出 \(rk\) 数组,然后进行二路归并,取 \(rk\) 更小的那个位置即可。

等下,\(A+B\) 里面 \(A\) 的后面多了一整个 \(B\) 当后缀,为啥不会影响结果呢?

如果当前位置 \(A_i\ne B_j\),显然在 \(rk\) 数组里面没有影响。如果 \(A_i=B_j\) 了,但存在第一个 \(A_{i+k}\ne B_{j+k}\) 的位置,是同理的。那么下面考虑如果 \(A_{i\dots}=B_{j\dots}\),直到一个串结束。此时一个串是另一个串的前缀,这些都是相同的,先取哪个数列中的数没有关系。这时候按照 \(rk\) 数组排序,默认会先取 \(B\) 中的数,也就不会出问题。

于是这题就做完了,总复杂度就是 SA 的复杂度,这里我写的是倍增算法,就是 \(\mathcal{O}(n\log{n})\)

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 4e5+5; 

int n1, n2, a[N], b[N], sa[N], rk[N], lst[N<<1], id[N], cnt[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
	scanf("%d", &n1);
	rep(i, 1, n1) scanf("%d", &a[i]);
	scanf("%d", &n2);
	rep(i, 1, n2) scanf("%d", &a[n1+i]);
	int n = n1 + n2, m = 1000;
	rep(i, 1, n) ++cnt[rk[i] = a[i]];
	rep(i, 1, m) cnt[i] += cnt[i-1];
	per(i, n, 1) sa[cnt[rk[i]]--] = i;
	for(int w=1,p=0;;w<<=1,m=p) {
		p = 0;
		per(i, n, n-w+1) id[++p] = i;
		rep(i, 1, n) if(sa[i] > w) id[++p] = sa[i] - w;
		memset(cnt, 0, sizeof(cnt));
		rep(i, 1, n) ++cnt[rk[id[i]]];
		rep(i, 1, m) cnt[i] += cnt[i-1];
		per(i, n, 1) sa[cnt[rk[id[i]]]--] = id[i];
		memcpy(lst, rk, sizeof(rk));
		p = 0;
		rep(i, 1, n) {
			if(lst[sa[i]] == lst[sa[i-1]] && lst[sa[i]+w] == lst[sa[i-1]+w]) rk[sa[i]] = p;
			else rk[sa[i]] = ++p;
		}
		if(p == n) {
			rep(i, 1, n) sa[rk[i]] = i;
			break;
		}
	}
	for(int l=1,r=n1+1,i=1;i<=n;i++) {
		if(l > n1) b[i] = a[r++];
		else if(r > n) b[i] = a[l++];
		else b[i] = (rk[l] < rk[r]) ? a[l++] : a[r++];
	}
	rep(i, 1, n) printf("%d%c", b[i], " \n"[i==n]);
	return 0;
}

本文来自博客园,作者:rui_er,转载请与作者联系并注明原文链接:https://www.cnblogs.com/ruierqwq/p/LG-P8023.html

推荐这些文章:

题解洛谷 P2691【逃离】

最大流。
题目中的起始点肯定是要被超级源连上的。考虑到要求这 \(m\) 个点能通过 \(m\) 条不在格点相交的路径连到边界上,流的方法大致就是沿着网格线,然后边界点连超级汇,权值都是 \(1\)。另外,每个点只能在不超过一条路径上,只是这样会被重复流过,需要搞一遍拆点的套路。
这题的网络流建模挺经典的。
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--...

[题解]一氧化二氢

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\
\begin{array}{|}
\hline
\color{pink}{\text{The principal is really a god}} \\
\color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\
\color{pink}{\text{holding a sharp pen to pierce the truth}} \\
\color{pink}{\text{Wh...

并查集模板 (洛谷p3367题解)

 
 
#include<bits/stdc++.h>using namespace std;const int maxn = 10005;int s[maxn];void init(){ // 初始化使初始的每个结点都是自己的根结点 for(int i = 1 ; i <= maxn ; i++){ s[i]=i; } }int find_set(int x){ // 找到每个元素的根结点,并且压缩路径使得每个元素直接接在根节点上 return x==s[x]?x:s[x]=find_set(s[x]);}void union_set(int...

[题解]高级监狱Ⅲ

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\
\begin{array}{|}
\hline
\color{pink}{\text{The principal is really a god}} \\
\color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\
\color{pink}{\text{holding a sharp pen to pierce the truth}} \\
\color{pink}{\text{Wh...

[题解]高级监狱

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\
\begin{array}{|}
\hline
\color{pink}{\text{The principal is really a god}} \\
\color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\
\color{pink}{\text{holding a sharp pen to pierce the truth}} \\
\color{pink}{\text{Wh...

[题解]高级监狱Ⅱ

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\
\begin{array}{|}
\hline
\color{pink}{\text{The principal is really a god}} \\
\color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\
\color{pink}{\text{holding a sharp pen to pierce the truth}} \\
\color{pink}{\text{Wh...

[题解]退钱!

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\
\begin{array}{|}
\hline
\color{pink}{\text{The principal is really a god}} \\
\color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\
\color{pink}{\text{holding a sharp pen to pierce the truth}} \\
\color{pink}{\text{Wh...

[题解]血战狗熊岭

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\
\begin{array}{|}
\hline
\color{pink}{\text{The principal is really a god}} \\
\color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\
\color{pink}{\text{holding a sharp pen to pierce the truth}} \\
\color{pink}{\text{Wh...

洛谷P2121 拆地毯

题目链接:https://www.luogu.com.cn/problem/P2121
最大生成树
Talk is cheap. Show me the code.

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int num=1e5+10;
struct edge
{
int u;
int v;
int w;
}e[num];
int ans;
int cnt;
int k;
int s[num];
bool cmp(edge a,edge b)
{
return a.w...

题解 CF917B【MADMAX】

一道比较简单的 DP。
我们开一个三维数组 \(dp_{i,j,w}\) 表示一个人在 \(i\),另一个人在 \(j\),且另一个人上一步走棋走的边权值为 \(w\) 的胜负情况。转移时枚举 \(i\) 的所有权值不小于 \(w\) 的出边,如果可以走到“必败状态”则当前点为“必胜状态”,如果无法走到则为“必败状态”。
由于初始状态和转移的顺序不太好处理(也许可以拓扑排序,但我懒),所以我们采用记忆化搜索来求答案。
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y...

文章标题:题解洛谷 P8023【[ONTAK2015] Tasowanie】
文章链接:https://www.dianjilingqu.com/51290.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>