CF201D Brand New Problem 简略题解

Problem D – Codeforces Round #127 (Div. 1)

多模式串匹配，是不是又是AC自动机啊？

显然，每个文本串中，模式串的排列构成的子序列的逆序对数量只和模式串有关。所以我们可以对模式串建立Trie树，每扫入一个文本串的单词就进行匹配。可以做到$\mathrm{O}(K)$，K为文本串总长（虽然单个字符串的长度极小可以$\mathrm{O}(NK)暴跳$）。这样就构建出一个由$1$到$n$构建的数列。

枚举$15!$的全排列然后暴搜显然不可行。我们注意到，如果钦定一个数$x$，只要知晓当前的排列中前$j$位分别是哪些数，就可以立刻算出$x$加入排列后新增的逆序对数量。则我们考虑状压DP。

容易设计出这样的状态：$dp(S, i)$表示“已经加入的数的集合为$S$，且最后一个单词是第$i$个”造成的最小逆序对数。

显然，我们能够写出的最快的转移，是从数列开头依次枚举当前位置单词所处的集合并尝试从其子集转移，共计$\mathrm{O}(2^n * k)$的计算，会严重超时。

但我们注意到，一个集合S确定后，只会通过确定的、不超过$|S| – 1$个子集转移。同时，扫描到数列的后面，所有状态可能都不会再次更新——当我们指定的所有的子集$S’$的状态都完成更新后，第一次对$S$的状态的更新就是最小逆序对数。

也就是说，如果我们知道某种$S$构成的排列构成的最小逆序对数能够在某些位置被更新到，那么显然第一次更新是最优的，这会给$S$的超集的更新带来最大的可能。

所以，为了避免在后续位置进行的重复的、低效的更新，我们可以将状态和值交换一下，只考虑“对集合$S$完成转移同时逆序对数量为i的最小字串位置”，也就是对一开始设计的状态产生更新的最靠前的位置，就符合我们上述的思想。同时注意到，最大可能的逆序对数非常小，至多$105$对，所以我们可以放心地顺次枚举集合$S$，对于刚刚定义的$f(S, i)$，存在子集$S’$满足有且仅有一个元素$x$属于$S$而不属于$S’$话，则有$f(S, i) = f(S’, i – x造成的逆序对数)后的最近的x的位置$。

很容易通过$O(k)$的倒序扫描的预处理求出一个数组$post(x, i)$，表示在数列的第$x$位以后第一个出现的模式串$i$的位置。

时间复杂度$\mathrm{O}(\sum k\times n + 2^n  \times C_{n}^{2} \times n)$，可以通过本题。

Submission 131643571

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 20, INF = 0x3f3f3f3f;
int n, tr[160][26], ed[160], len, x, cnt;
int m, k, res, seq[N], l, post[16][N], inv, simi = -INF, ori;
int dp[1<<15][128];
char mode[16];

void process (int id) {
	x = 0; len = strlen (mode);
	for (int i = 0; i < len; ++i) {
		if (!tr[x][mode[i] - 'a']) tr[x][mode[i] - 'a'] = ++cnt;
		x = tr[x][mode[i] - 'a'];
	}
	ed[x] = id;
}
int query () {
	len = strlen (mode); x = 0;
	for (int i = 0; i < len; ++i) {
		if (!tr[x][mode[i] - 'a']) return 0;
		x = tr[x][mode[i] - 'a'];
	}
	return ed[x];
}
int popcnt (int x) {
	int res = 0;
	while (x)
		++res, x = x & (x - 1);
	return res;
}

int main () {
	/* CF201D Brand New Problem 吴秋实 */
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
	scanf ("%s", mode);
	process (i);
}
scanf ("%d", &m);
for (int seg = 1; seg <= m; ++seg) {
	scanf ("%d", &k); l = 0;
	for (int i = 1; i <= k; ++i) {
		scanf ("%s", mode);
		res = query ();
		if (res) seq[++l] = res;
	}
	
	for (int i = 1; i <= n; ++i) { post[i][l] = INF; for (int j = l - 1; j >= 0; --j)
			if (seq[j + 1] == i) post[i][j] = j + 1;
			else post[i][j] = post[i][j + 1];
	}
	memset (dp, 0x3f, sizeof dp);
	dp[0][0] = 0, res = INF;
	for (int s = 1; s < 1<<n; ++s)
		for (int x = 1; x <= n; ++x) {
			if ((s&(1<<(x-1))) == 0) continue; inv = popcnt (s>>x);
			for (int i = inv; i <= (n - 1) * n / 2; ++i) { // 造成了多少新的逆序对？ if (inv > i) continue;
				if (dp[s^(1<<(x-1))][i - inv] != INF)
					dp[s][i] = min (post[x][dp[s^(1<<(x-1))][i - inv]], dp[s][i]);
			}
		}

	for (int i = 0; i <= n * (n - 1) / 2; ++i)
		if (dp[(1<<n)-1][i] != INF) { res = i; break;} if ((n - 1) * n / 2 - res + 1 > simi)
		simi = (n - 1) * n / 2 - res + 1, ori = seg;
}
if (simi <= 0) return puts ("Brand new problem!"), 0;
printf ("%d\n", ori);
printf ("[:");
for (int i = 1; i <= simi; ++i)
	putchar ('|');
puts (":]");

	return 0;
}