今日又是三道集训队作业原题。。又没部分分。。

反正我都不会必定爆零就没交了。。

$\text{score：NULL rk：NULL}$

Problem A：Birthday

题目描述

给定 $n$ 个仅包含 a,b 的字符串。

你需要去掉尽可能少的字符串，使得剩下的字符串中不存在某一个串是另一个串的子串。

数据范围

对 $100\%$ 的数据，$1 \le n \le 750, ~ \sum\limits_{i = 1}^n |s_i \le 10^7$

题解

原题 CF590E

由于 $n$ 很小，很显然可以对每一对字符串判断一个是不是另一个的子串，如果是就连个单向边，最终形成一个 $DAG$ 然后在上面搞

那么对于建图，先建个$\text{AC}$自动机，在 $trie$ 的结尾存一下编号，然后把每个串扔上去匹配，每次匹配与走到节点 $fail$ 树上的所有编号（即它的子串）连边

当然直接连边肯定会 $T$，实际上你只要往在 $fail$ 树往上找到的第一个编号以及本身节点的编号（如果存在的话）连边，然后传递闭包就好了，这样复杂度就正确了

那么接下来的任务就是在 $DAG$ 上求出最长反链并构造方案

那这就是 [CTSC2008]祭祀

代码

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>

using namespace std;

const int MAXN = 750 + 10;
const int MAXM = 1e07 + 10;
const int MAXL = 2 * MAXN + MAXN * MAXN;

const int INF = 0x7fffffff;

struct LFDS { int to, next; };
LFDS iLink[MAXN * MAXN];
int iHead[MAXM]= {0}, isize = 0;
void Insert (int u, int v) {
	iLink[++ isize].to = v;
	iLink[isize].next = iHead[u];

	iHead[u] = isize;
}

int N;
char str[MAXM];
vector<int> sve[MAXN];

int tr[MAXM][2]= {0}, m = 0;
void insert (int ind) {
	int p = 0, n = strlen (str + 1);
	for (int i = 1; i <= n; i ++) {
		int c = str[i] - 'a';
		sve[ind].push_back(c);
		if (! tr[p][c]) tr[p][c] = ++ m;
		p = tr[p][c];
	}
	Insert (p, ind);
}
int fail[MAXM]= {0};
queue<int> que;
int lastp[MAXM]= {0};
bitset<MAXN> g[MAXN];
void build () {
	for (int i = 0; i < 2; i ++)
		if (tr[0][i])
			que.push(tr[0][i]);
	while (! que.empty()) {
		int u = que.front(); que.pop();
		lastp[u] = iHead[fail[u]] ? fail[u] : lastp[fail[u]];
		for (int i = 0; i < 2; i ++) {
			if (tr[u][i]) {
				fail[tr[u][i]] = tr[fail[u]][i];
				que.push(tr[u][i]);
			}
			else tr[u][i] = tr[fail[u]][i];
		}
	}
}
void work (int ind) {
	int p = 0;
	for (int i = 0; i < (int) sve[ind].size(); i ++) {
		int c = sve[ind][i];
		p = tr[p][c];
		int tp = p;
		for (int j = 1; j <= 2; j ++) {
			for (int k = iHead[tp]; k; k = iLink[k].next) {
				int v = iLink[k].to;
				if (v == ind) continue;
				g[v][ind] = 1;
			}
			tp = lastp[tp];
		}
	}
}

struct LFS { int to, cap, next; } ;
LFS Link[MAXL << 1];
int Head[MAXN << 1]= {0}, size = 1;
void Insert (int u, int v, int cap) {
	Link[++ size].to = v;
	Link[size].cap = cap;
	Link[size].next = Head[u];

	Head[u] = size;
}
void add (int x, int y, int cap) {
	Insert (x, y, cap); Insert (y, x, 0);
}

int S, T, _N;
int depth[MAXN << 1]= {0};
bool BFS () {
	while (! que.empty()) que.pop();
	memset (depth, 0, sizeof (depth));
	depth[S] = 1, que.push(S);
	while (! que.empty()) {
		int u = que.front(); que.pop();
		for (int i = Head[u]; i; i = Link[i].next) {
			int v = Link[i].to, cap = Link[i].cap;
			if (depth[v] || ! cap) continue;
			depth[v] = depth[u] + 1;
			if (v == T) return true;
			que.push(v);
		}
	}
	return false;
}
int cur[MAXN << 1]= {0};
int Dinic (int p, int flow) {
	if (p == T) return flow;
	int rest = flow;
	for (int &i = cur[p]; i && rest; i = Link[i].next) {
		int v = Link[i].to, cap = Link[i].cap;
		if (depth[v] != depth[p] + 1 || ! cap) continue;
		int k = Dinic (v, min (cap, rest));
		if (! k) depth[v] = - 1;
		Link[i].cap -= k, Link[i ^ 1].cap += k;
		rest -= k;
	}
	return flow - rest;
}
int MAXFLOW () {
	int ret = 0;
	while (BFS ()) {
		for (int i = 1; i <= _N; i ++) cur[i] = Head[i];
		ret += Dinic (S, INF);
	}
	return ret;
}
int match[MAXN]= {0};

bool tagl[MAXN]= {false}, tagr[MAXN]= {false};
void DFS (int u) {
	tagr[u - N] = true;
	for (int i = 1; i <= N; i ++)
		if (g[i][u - N] && ! tagl[i]) {
			tagl[i] = true;
			DFS (match[i]);
		}
}

int main () {
	scanf ("%d", & N);
	for (int i = 1; i <= N; i ++) {
		scanf ("%s", str + 1);
		insert (i);
	}
	build ();
	for (int i = 1; i <= N; i ++) work (i);
	for (int k = 1; k <= N; k ++)
		for (int i = 1; i <= N; i ++)
			if (g[i][k])
				g[i] |= g[k];
	S = 2 * N + 1, _N = T = 2 * N + 2;
	for (int i = 1; i <= N; i ++)
		add (S, i, 1), add (i + N, T, 1);
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			if (g[i][j])
				add (i, j + N, 1);
	int ans = N - MAXFLOW ();
	printf ("%d\n", ans);
	for (int i = 1; i <= N; i ++)
		if (! Link[4 * i - 2].cap)
			for (int j = Head[i]; j; j = Link[j].next)
				if (! Link[j].cap) {
					match[i] = Link[j].to;
					break;
				}
	for (int i = 1; i <= N; i ++)
		if (Link[4 * i].cap)
			DFS (i + N);
	for (int i = 1; i <= N; i ++)
		if (! tagl[i] && tagr[i])
			printf ("%d ", i);
	puts ("");

	return 0;
}

Problem B：A Sequence of Permutations

题目描述

给定两个长为 $n$ 的排列 $p, q$，设 $f(p, q)$ 为使第 $p_i$ 个数为 $q_i$ 的排列

已知 $a_1 = p, a_2 = q, a_{n + 2} = f(a_n, a_{n + 1})$，求 $a_k$

数据范围

对 $100\%$ 的数据，$n \le 10^5, ~ k \le 10^9$

前置知识

定义两个排列 $p, q$ 的乘法为，设 $r = pq$，则有
$$
r_i = p_{q_i}
$$
该乘法满足结合律，但不满足交换律

该乘法的单位元为 $e$ 满足 $e_i = i$，那么排列 $p$ 的逆元 $p^{- 1}$ 即可定义为 $p^{- 1}$ 满足 $p^{- 1}_{p_i} = i$

对逆元，有 $(pq)^{- 1} = q^{- 1}p^{- 1}$，同理对多个排列相乘的逆元，将它们反过来再分别求逆，最后按顺序相乘即可

下面给出该逆元公式的简单证明：

  • 设 $A = (pq)^{- 1}$，则有 $A_{p_{q_i}} = i$
  • 设 $B = q^{- 1}p^{- 1}$，则有 $B_i = q^{- 1}{p^{- 1}_i}$，令 $i = p_i$，有 $B{p_i} = q^{- 1}i$，再令 $i = q_i$，最后有 $B{p_{q_i}} = i$
  • 即 $A_{p_{q_i}} = B_{p_{q_i}}$，故等式成立

题解

$$
\begin{aligned}
&f(p, q)_{p_i} = q_i \\
\Rightarrow &f(p, q) * p = q \\
\Rightarrow &f(p, q) = qp^{- 1}
\end{aligned}
$$

然后打表找规律
$$
\begin{aligned}
a_1 &= p \\
a_2 &= q \\
a_3 &= qp^{- 1} \\
a_4 &= qp^{- 1}q^{- 1} \\
a_5 &= qp^{- 1}q^{- 1}pq^{- 1} \\
a_6 &= qp^{- 1}q^{- 1}p^2q^{- 1} \\
a_7 &= qp^{- 1}q^{- 1}pqpq^{- 1} \\
a_8 &= qp^{- 1}q^{- 1}pqp^{- 1}qpq^{- 1} \\
\cdots
\end{aligned}
$$
令 $t = qp^{- 1}q^{- 1}p$，则 $a_7 = tpt^{- 1}, a_8 = tqt^{- 1}$，那么可以得到 $a_{6k + 1} = t^kpt^{- k}, a_{6k + 2} = t^kqt^{- k}$，对 $t$ 做个快速幂，然后剩下的几项暴力一下就好了

时间复杂度 $O (n \log \frac{k}{6})$

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1e05 + 10;

int N, K;
int P[MAXN], Q[MAXN];
int IP[MAXN], IQ[MAXN];
int T[MAXN], IT[MAXN];
int Tk[MAXN], ITk[MAXN];

void mul (int* ret, int* p, int* q) { for (int i = 1; i <= N; i ++) ret[i] = p[q[i]]; }
void inv (int* I, int* p) { for (int i = 1; i <= N; i ++) I[p[i]] = i; }
int A[MAXN], ret[MAXN];
void power (int* x, int p) {
	for (int i = 1; i <= N; i ++) ret[i] = i;
	while (p) {
		if (p & 1) { mul (A, ret, x); for (int i = 1; i <= N; i ++) ret[i] = A[i]; }
		mul (A, x, x); for (int i = 1; i <= N; i ++) x[i] = A[i];
		p >>= 1;
	}
	for (int i = 1; i <= N; i ++) x[i] = ret[i];
}
void print (int* a) {
	for (int i = 1; i <= N; i ++) {
		if (i > 1) putchar (' ');
		printf ("%d", a[i]);
	} puts ("");
}
int a[7][MAXN];
void solve (int n) {
	if (n == 0) n = 6;
	mul (a[1], P, ITk), mul (A, Tk, a[1]);
	for (int i = 1; i <= N; i ++) a[1][i] = A[i];
	if (n == 1) { print (a[1]); return ; }
	mul (a[2], Q, ITk), mul (A, Tk, a[2]);
	for (int i = 1; i <= N; i ++) a[2][i] = A[i];
	if (n == 2) { print (a[2]); return ; }
	for (int i = 1; i <= n - 2; i ++)
		for (int j = 1; j <= N; j ++) a[i + 2][a[i][j]] = a[i + 1][j];
	print (a[n]);
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), K = getnum ();
	for (int i = 1; i <= N; i ++) P[i] = getnum ();
	for (int i = 1; i <= N; i ++) Q[i] = getnum ();
	inv (IP, P), inv (IQ, Q);
	mul (T, IQ, P), mul (A, IP, T);
	for (int i = 1; i <= N; i ++) T[i] = A[i];
	mul (A, Q, T); for (int i = 1; i <= N; i ++) T[i] = A[i];
	inv (IT, T); int k = K / 6; if (! (K % 6)) k --;
	for (int i = 1; i <= N; i ++) Tk[i] = T[i]; power (Tk, k);
	for (int i = 1; i <= N; i ++) ITk[i] = IT[i]; power (ITk, k);
	int r = K % 6; solve (r);

	return 0;
}

Problem C：Synchronized Subsequence

题目描述

有一个长度为 $2n$ 的仅由字符 $\mathtt{a}, \mathtt{b}$ 构成的字符串，且 $\mathtt{a}$ 的个数恰好等于 $\mathtt{b}$ 的个数，都出现了 $n$ 次

你需要保留一些字符，剩下的字符删掉。对于一个 $i$，你可以保留从左往右数的第 $i$ 个 $\mathtt{a}$ 和第 $i$ 个 $\mathtt{b}$

注意，对于这两个字符，只能同时保留或同时删掉，不能只保留其中一个

请你求出能得到的字典序最大的串

数据范围

对 $100\%$ 的数据，$1 \le n \le 3000$

题解

其实好像可以直接贪心来着，但我觉得 贪心 + $dp$ 的方法更值得记录

现在考虑若强制要求第 $i$ 对 $a, b$ 存在有什么样的局面，设第 $i$ 对 $a, b$ 在字符串中的位置 $apos_i. bpos_i$

  • 若 $apos_i < bpos_i$，那么在把该对 $a, b$ 之间的 $a$ 全部删掉之前都不是更优的，故它们之间的 $a$ 应全部删去，最终留下 $ab$
  • 若 $apos_i > bpos_i$，显然它们之间的 $b$ 都必须全部存在

那么现在记 $f_i$ 表示强制选第 $i$ 对 $a,b$，对 $i…n$ 对 $a, b$ 组合成的最大串，记 $g_i$ 表示 $\max (f_i, f_i + 1, …, f_n)$

注意 $f, g$ 都是 $\text{string}$ 类型

转移就看代码把

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

const int MAXN = 3000 + 10;

int N;
char str[MAXN << 1];
int apos[MAXN]= {0}, bpos[MAXN]= {0};
int an = 0, bn = 0;

string f[MAXN], g[MAXN];
// f[i]: 强制选第i对a、b，对i...n对a、b的最大串
// g[i]: max (f[i], f[i + 1], ..., f[n])

int main () {
	scanf ("%d%s", & N, str + 1);
	for (int i = 1; i <= N << 1; i ++) {
		if (str[i] == 'a') apos[++ an] = i;
		if (str[i] == 'b') bpos[++ bn] = i;
	}
	for (int i = N; i >= 1; i --) {
		if (apos[i] < bpos[i]) {
			int j = i;
			while (j <= N && apos[j] < bpos[i]) j ++;
			f[i] = "ab" + g[j];
		}
		else {
			int j = i;
			while (j <= N && bpos[j] < apos[i]) j ++;
			for (int k = 1; k <= j - i; k ++) f[i] += 'b';
			f[i] += 'a' + (i + 1 == j ? g[i + 1] : f[i + 1]).substr(j - i - 1, string::npos); // j-i-1表示i...j-1都已经放完，取g[i+1]或f[i+1]的j...n段
		}
		g[i] = max (f[i], g[i + 1]);
	}
	cout << g[1] << endl;

	return 0;
}