@atcoder - AGC024F@ Simple Subsequence Problem

@description@
@solution@
@accepted code@
@details@

@description@

给定由若干长度 <= N 的 01 字符串组成的集合 S。请找到长度最长的串 t（如果有多个选字典序最小的），使得存在 >= K 个 S 中的字符串，使得 t 是这些字符串的子序列。

@solution@

先看看怎么检验串 t 是否为某个串 s 的子序列：从前往后匹配，贪心地找最前面一个能够匹配上的。

注意到匹配的过程可以建图：每个种类的串 s 建点，向第一次出现的 0/1 对应的后缀连边。

每个点的连边是 O(1)，因此假如把所有 <= N 的串建这个图，实际得到的图也不会很大。

于是就有一个思路：枚举 t，每次将 S 中的串对应的点在这个图上进行移动，看剩余的点是否依然 >= K 个。

看似会 TLE，然而可以修正一下：如果两个字符串走到了同一个点，下一次只移动这一个点即可。

看似还会 TLE，实际上可以过了。

因为每个长度为 p 的字符串会有 2^p 种可能性，而它继续往下匹配只会剩下 2^(N-p) 种匹配可能。因此每一个 p 都是 O(2^N) 的复杂度。

因此总复杂度为 O(N*2^N) （应该是吧，没有认真算过）。

@accepted code@

#include <cstdio>

int ch[2][1<<22], id[22][1<<21], cnt;

void get() {

	id[0][0] = (cnt++), ch[0][id[0][0]] = ch[1][id[0][0]] = -1;

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

		int t = (1 << i), k = (t >> 1);

		for(int s=0;s<t;s++) {

			id[i][s] = (cnt++);

			int p = (s & k), q = (p ? 1 : 0);

			ch[q][id[i][s]] = id[i-1][s^p];

			ch[!q][id[i][s]] = ch[!q][id[i-1][s^p]];

		}

	}

}

int a[22][1<<22], siz[22], c[22][1<<22], num[22][1<<22];

int ans[22], N, K;

void dfs(int d, int s) {

	if( ans[d] == -1 ) ans[d] = s;

	for(int p=0;p<=1;p++) {

		int tot = 0;

		for(int i=0;i<siz[d];i++) {

			int to = ch[p][a[d][i]];

			if( to == -1 ) continue;

			if( num[d + 1][to] == -1 )

				num[d + 1][a[d + 1][siz[d + 1]] = to] = siz[d + 1], siz[d + 1]++;

			tot += c[d][i], c[d + 1][num[d + 1][to]] += c[d][i];

		}

		if( tot >= K ) dfs(d + 1, (s << 1) | p);

		for(int i=0;i<siz[d + 1];i++)

			num[d + 1][a[d + 1][i]] = -1, c[d + 1][i] = 0;

		siz[d + 1] = 0;

	}

}

char s[1<<21];

int main() {

	scanf("%d%d", &N, &K), get();

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

		for(int j=0;j<cnt;j++)

			num[i][j] = -1;

	for(int i=0;i<=N;i++) {

		scanf("%s", s);

		int t = (1 << i);

		for(int j=0;j<t;j++) {

			if( s[j] == '1' )

				num[0][a[0][siz[0]] = id[i][j]] = siz[0], c[0][num[0][id[i][j]]]++, siz[0]++;

		}

		ans[i] = -1;

	}

	dfs(0, 0);

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

		if( ans[i] != -1 ) {

			for(int j=i-1;j>=0;j--)

				putchar(((ans[i] >> j) & 1) + '0');

			puts(""); return 0;

		}

	}

}

@details@

事实证明再怎么精打细算还是有想象之外的越界危险。

还不如直接数组开大 2 倍。

巴特西

@atcoder - AGC024F@ Simple Subsequence Problem

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章