NOI2016优秀的拆分

一种想法是枚举分割位置，然后考虑前面部分有多少种可行的AA拆分方式，后面部分有多少种可行的BB拆分方式，然后乘法原理即可
那么问题是如何快速求出合法方案
解法是首先枚举长度len，然后将序列分成 $\frac{n}{len}$ 段，然后我们对于每个连续的三个段i，j, k，求一下i, j的最长公共后缀a， j，k的最长公共前缀b,
如果a + b < len，显然无法构造
如果a + b >= len，那么整整一个区间都可以构造出来，差分统计一下答案
因为某些地方没清空以及某些地方特判写狗了， WA成狗



#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define M 60010

using namespace std;

int read() {

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int log[M];

struct SA {

	char s[M];

	int sa[M], tmp[M], tex[M], rnk[M], f[M][17], n, m, q;

	bool check(int i, int j, int w) {

		return tmp[i] == tmp[j] && tmp[i + w] == tmp[j + w];

	}

	void qsort() {

		for(int i = 0; i <= m; i++) tex[i] = 0;

		for(int i = 1; i <= n; i++) tex[rnk[tmp[i]]]++;

		for(int i = 1; i <= m; i++) tex[i] += tex[i - 1];

		for(int i = n; i >= 1; i--) sa[tex[rnk[tmp[i]]]--] = tmp[i];

	}

	void suffix() {

		memset(tmp, 0, sizeof(tmp));

		memset(tex, 0, sizeof(tex));

		memset(sa, 0, sizeof(sa));

		memset(rnk, 0, sizeof(rnk));

		memset(f, 0, sizeof(f));

		m = 127, q = 0;

		for(int i = 1; i <= n; i++) rnk[i] = s[i], tmp[i] = i;

		qsort();

		for(int w = 1; q < n; w <<= 1, m = q) {

			q = 0;

			for(int i = n - w + 1; i <= n; i++) tmp[++q] = i;

			for(int i = 1; i <= n; i++) if(sa[i] > w) tmp[++q] = sa[i] - w;

			qsort();

			swap(rnk, tmp);

			rnk[sa[1]] = q = 1;

			for(int i = 2; i <= n; i++) if(check(sa[i - 1], sa[i], w)) rnk[sa[i]] = q;

				else rnk[sa[i]] = ++q;

		}

		q = 0;

	//	cerr << "\n";

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

			if(q) q--;

			int j = sa[rnk[i] + 1];

			if(rnk[i] == n) continue;

			while(s[i + q] == s[j + q] && i + q <= n && j + q <= n) q++;

			f[rnk[i]][0] = q;

		//	cerr << q << " ";

			//if(q >n) cerr<<"!";

		}

	//	cerr << "\n";

		//for(int i = 1; i <= n; i++) cerr << rnk[i] << " ";

	//	cout << "\n";

		for(int j = 1; j <= 15; j++) {

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

				if(i + (1 << (j - 1)) > n) break;

				f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

			}

		}

	}

	int lcp(int a, int b) {

		a = rnk[a], b = rnk[b];

		if(a > b) swap(a, b);

		int k = log[b - a];

		return min(f[a][k], f[b - (1 << k)][k]);

	}

} a, b;

int be[M], ed[M];

char s[M];

void work() {

	memset(s, 0, sizeof(s));

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

	int n = strlen(s + 1);

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

		a.s[i] = s[i], b.s[i] = s[n - i + 1];

	}

	memset(be, 0, sizeof(be));

	memset(ed, 0, sizeof(ed));

	a.n = b.n = n;

	a.suffix();

	b.suffix();

	for(int len = 1; len <= n / 2; len++) {

		for(int i = len, j = i + len; j <= n; i += len, j += len) {

			int x = min(a.lcp(i, j), len), y = min(b.lcp(n - (i - 1) + 1, n - (j - 1) + 1), len - 1);

			int t = x + y - len + 1;

			if(x + y >= len) {

				be[i - y]++;

				be[i - y + t]--;

				ed[j + x - t]++;

				ed[j + x]--;

			}

		}

	}

	ll ans = 0;

	for(int i = 1; i <= n; i++) be[i] += be[i - 1], ed[i] += ed[i - 1], ans += 1ll * ed[i - 1] * be[i];

	cout << ans << "\n";

}

int main() {

	for(int i = 2; i < M; i++) log[i] = log[i >> 1] + 1;

	int T = read();

	while(T--) work();

	return 0;

}

/*

10

zzzzzzzzzzzzzzzzzzzzzzzzzzz

icicicicicicicicicicic

saasaasaasaasaasaasaa

znunznunznunznunznun

ttfhhttfhhttfhhttfhhttfhh

fqxqblfqxqblfqxqblfqxqblfqxqbl

xxpruxxpruxxpruxxpru

mpheqsmpheqsmpheqsmpheqs

ptvbemqptvbemqptvbemqptvbemq

nxykqknxykqknxykqknxykqk

2

xxpruxxpruxxpruxxpru

zzzzzzzzzzzzzzzzzzzzzzzzzzz

*/

巴特西

NOI2016优秀的拆分

最新文章

热门文章