[十二省联考2019]D1T2字符串问题

嘟嘟嘟

省选Day1真是重大失误，T2连暴力都没时间写。

上周五重新答了遍Day1，竟然搞了187分吼吼吼吼。

T2按40分写的暴力，结果竟然得了60分。

稍微说一下暴力吧：预处理哈希，对于一组支配关系\(A_i\), \(B_i\)，用哈希判断\(B_i\)是哪些\(A\)串的前缀，是的话就连边\((A_i, A_j)\)。用哈希能做到单次\(O(n)\)，因此建图复杂度\(O(n ^ 2)\)。

然后就是判无环后拓扑排序了。

暴力代码我会在最下面放！

接着讲正解。

从暴力能看出来，瓶颈在于建图，一是挨个判前缀时间不够，二是挨个建边空间不够。

为了解决这些，我们需要强力的字符串数据结构，比如SAM（我不会SA）。

首先把原串反过来建SAM，并记录每一个位置在后缀树（我才知道到由link构成的树就是后缀树）上对应的节点。

然后对于每一个\(A\)，\(B\)串，倍增找到后缀树上的所属的节点，开一个vector存下来。

我们要做的，就是对于所有\(B_i\)，如果是\(A_j\)的后缀（因为反过来了），就向\(A_j\)连边，这样如果\(A_i\)支配\(B_i\)，只需从\(A_i\)向\(B_i\)连边，图就建好了。

支配的话直接连就好了，而\(B_i\)向所有\(A_j\)连边，其实就是\(B_i\)向他的子树里的所有\(A_j\)连边，但这样一条条连固然不行，观察到这些\(A_j\)的dfs序是连续的，所以可以线段树优化建图，这就是伟大的学姐写的。

其实也不用。只要每一个点向他的孩子连边就行了，这样虽然不是直接连边，但肯定能保证\(B_i\)能到\(A_j\)。

这个虽然解决了，但还有一件事没有解决。

就是后缀树上的每一个点可能有多个\(A\)，\(B\)串（不然开vector干嘛），因此上述连边会让编号弄混，分不清到底向哪一个串连边。

所以我们先把每一个vector按长度为第一关键字，是否为\(A\)类串为第二关键字排序，然后把后缀树上的点拆点，在一个节点内，如果有\(A_1, A_2, A_3, B_1, B_2\)这几个串，且长度上满足\(l_{B_1} > l_{A_1} > l_{A_2} > l_{B_2} > l _ {A_3}\)，那么我们就这么建图：

其中\(i\)表示后缀树上这个结点的编号，\(j\)是\(i\)的孩子结点。

然后我们就可以愉快的跑拓扑排序啦，注意到图上只有\(A\)类点是我们需要的，因此把别的点的权值清零，就不会干扰\(A\)类点统计答案了。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 2e5 + 5;

const int maxe = 2e6 + 5;

const int N = 18;

inline ll read()

{

  	ll ans = 0;

  	char ch = getchar(), last = ' ';

  	while(!isdigit(ch)) last = ch, ch = getchar();

  	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  	if(last == '-') ans = -ans;

  	return ans;

}

inline void write(ll x)

{

  	if(x < 0) x = -x, putchar('-');

  	if(x >= 10) write(x / 10);

  	putchar(x % 10 + '0');

}

char s[maxn];

int n, m, na, nb;

int fa[N + 2][maxn << 1];

int tra[maxn << 1][27], link[maxn << 1], len[maxn << 2], id[maxn], las = 1, cnt = 1;

In void insert(int c)

{

  	int now = ++cnt, p = las;

  	len[now] = len[las] + 1;

  	while(p && !tra[p][c]) tra[p][c] = now, p = link[p];

  	if(!p) link[now] = 1;

  	else

    {

      	int q = tra[p][c];

      	if(len[q] == len[p] + 1) link[now] = q;

      	else

		{

		  	int clo = ++cnt;

		  	memcpy(tra[clo], tra[q], sizeof(tra[q]));

		  	len[clo] = len[p] + 1;

		  	link[clo] = link[q]; link[q] = link[now] = clo;

		  	while(p && tra[p][c] == q) tra[p][c] = clo, p = link[p];

		}

    }

  	las = now;

}

int Siz = 0, isa[maxn << 2], lst[maxn << 2];

int a[maxn], b[maxn];

vector<int> v[maxn << 2];

In void solve(const int& flg)

{

  	int L = read(), R = read();

  	int Len = R - L + 1, x = id[L];

  	for(int i = N; i >= 0; --i)

    	if(fa[i][x] && len[fa[i][x]] >= Len) x = fa[i][x];

  	isa[++Siz] = flg, len[Siz] = Len, v[x].push_back(Siz);

}

In bool cmp(const int& a, const int& b)

{

  	return len[a] > len[b] || (len[a] == len[b] && isa[a] > isa[b]);

}

struct Edge

{

  	int nxt, to;

}e[maxe];

int head[maxn << 2], ecnt = -1, du[maxn << 2];

In void addEdge(const int& x, const int& y)

{

  	++du[y];

  	e[++ecnt] = (Edge){head[x], y};

  	head[x] = ecnt;

}

ll dp[maxn << 2];

In ll topo()

{

  	queue<int> q; ll ret = 0;

  	for(int i = 1; i <= Siz; ++i) if(!du[i]) q.push(i), dp[i] = len[i];

  	while(!q.empty())

    {

      	int now = q.front(); q.pop();

      	ret = max(ret, dp[now]);

      	for(int i = head[now], v; ~i; i = e[i].nxt)

		{

	  		v = e[i].to;

	  		dp[v] = max(dp[v], dp[now] + len[v]);

	  		if(!--du[v]) q.push(v);

		}

    }

  	for(int i = 1; i <= Siz; ++i) if(du[i]) return -1;

  	return ret;

}

In void clear()

{

  	for(int i = 1; i <= cnt; ++i) link[i] = 0, Mem(tra[i], 0);

  	ecnt = -1; las = cnt = 1;

  	for(int i = 1; i <= Siz; ++i)

    {

      	v[i].clear(); head[i] = -1;

      	isa[i] = len[i] = dp[i] = du[i] = 0;

    }

}

int main()

{

  	//freopen("ha.in", "r", stdin);

  	//freopen("ha.out", "w", stdout);

  	Mem(head, -1);

  	int T = read();

  	while(T--)

    {

      	scanf("%s", s + 1); n = strlen(s + 1);

      	for(int i = n; i; --i) insert(s[i] - 'a'), id[i] = las;

      	for(int i = 1; i <= cnt; ++i) fa[0][i] = link[i];

      	for(int j = 1; j <= N; ++j)

			for(int i = 1; i <= cnt; ++i) fa[j][i] = fa[j - 1][fa[j - 1][i]];

      	Siz = cnt;

      	na = read();

      	for(int i = 1; i <= na; ++i) solve(1), a[i] = Siz;

      	nb = read();

      	for(int i = 1; i <= nb; ++i) solve(0), b[i] = Siz;

      	for(int i = 1; i <= cnt; ++i) sort(v[i].begin(), v[i].end(), cmp);

      	for(int i = 1; i <= cnt; ++i)

		{

	  		int last = i;

	  		for(int j = v[i].size() - 1; j >= 0; --j)

	    	{

	      		addEdge(last, v[i][j]);

	      		if(!isa[v[i][j]]) last = v[i][j];

	    	}

	  	lst[i] = last;

		}

      	for(int i = 2; i <= cnt; ++i) addEdge(lst[link[i]], i);

      	for(int i = 1; i <= Siz; ++i) if(!isa[i]) len[i] = 0;

      	m = read();

      	for(int i = 1, x, y; i <= m; ++i) x = read(), y = read(), addEdge(a[x], b[y]);

      	write(topo()), enter;

      	clear();

    }

  	return 0;

}

然后还有我的优美的暴力代码啦啦啦。（判环的时候还特意写了个tarjan，其实不用，拓扑后看有没有入度不为0的点就行了，就像上面一样）
```c++
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const ull bse = 998244353;
const int maxn = 2e5 + 5;
const int maxe = 1e7 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans = 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
#endif
}

char s[maxn];

ull has[maxn], p[maxn];

int n, m, na, nb, du[maxn];

bool FLG = 1;

struct Node

{

int L, R, len; ull h;

}ta[maxn], tb[maxn];

In ull calc_has(int L, int len)

{

return has[L + len - 1] - has[L - 1] * p[len];

}

struct Edge

{

int nxt, to;

}e[maxe];

int head[maxn], ecnt = -1;

In void addEdge(int x, int y)

{

if(x == y) FLG = 0;

e[++ecnt] = (Edge){head[x], y};

head[x] = ecnt;

}

bool in[maxn];

int st[maxn], top = 0;

int dfn[maxn], low[maxn], cnt = 0;

int num[maxn], ccol = 0;

In void tarjan(int now)

{

dfn[now] = low[now] = ++cnt;

st[++top] = now; in[now] = 1;

for(int i = head[now], v; ~i; i = e[i].nxt)

{

if(!dfn[v = e[i].to])

{

tarjan(v);

low[now] = min(low[now], low[v]);

}

else if(in[v]) low[now] = min(low[now], dfn[v]);

}

if(low[now] == dfn[now])

{

int x; ++ccol;

do

{

x = st[top--]; in[x] = 0;

++num[ccol];

}while(x ^ now);

}

}

ll dis[maxn];

In void topo()

{

queue q; q.push(0);

for(int i = 1; i <= na; ++i) if(!du[i]) q.push(i), dis[i] = ta[i].len;

while(!q.empty())

{

int now = q.front(); q.pop();

for(int i = head[now], v; ~i; i = e[i].nxt)

{

v = e[i].to;

dis[v] = max(dis[v], dis[now] + ta[v].len);

if(!--du[v]) q.push(v);

}

}

}

In void init()

{

ecnt = -1, top = cnt = ccol = 0; FLG = 1;

int Max = max(na, nb);

for(int i = 0; i <= Max; ++i)

du[i] = dfn[i] = low[i] = num[i] = dis[i] = in[i] = 0, head[i] = -1;

}

int main()

{

//MYFILE();

Mem(head, -1);

int T = read();

while(T--)

{

scanf("%s", s + 1);

n = strlen(s + 1); p[0] = 1;

for(int i = 1; i <= n; ++i)

{

has[i] = has[i - 1] * bse + s[i];

p[i] = p[i - 1] * bse;

}

na = read();

for(int i = 1; i <= na; ++i)

{

int L = read(), R = read();

ta[i] = (Node){L, R, R - L + 1, has[R] - has[L - 1] * p[R - L + 1]};

}

nb = read();

for(int i = 1; i <= nb; ++i)

{

int L = read(), R = read();

tb[i] = (Node){L, R, R - L + 1, has[R] - has[L - 1] * p[R - L + 1]};

}

init();

m = read();

for(int i = 1; i <= m; ++i)

{

int x = read(), y = read();

for(int j = 1; j <= na && FLG; ++j)

if(ta[j].len >= tb[y].len && calc_has(ta[j].L, tb[y].len) == tb[y].h)

addEdge(x, j), ++du[j];

}

if(!FLG) {puts("-1"); continue;}

bool flg = 1;

for(int i = 1; i <= na; ++i) if(!dfn[i]) tarjan(i);

for(int i = 1; i <= ccol && flg; ++i) if(num[i] > 1) flg = 0;

if(!flg) {puts("-1"); continue;}

topo();

ll ans = 0;

for(int i = 1; i <= na; ++i) ans = max(ans, dis[i]);

write(ans), enter;

}

return 0;

}

巴特西

[十二省联考2019]D1T2字符串问题

最新文章

热门文章