没有传送门题目大意考场上的思路思路参考代码为什么没有想到总结
没有传送门
题目大意
用一个数代表一个细胞，共有
n(n≤500)
n
(
n
≤
500
)
种细胞（用
1∼n
1
∼
n
表示）。细胞可以分裂，分裂成一个有序的细胞串，已知细胞
i
i
分裂会生成的细胞串为 hi,1,hi,2,⋯,hi,lihi,1,hi,2,⋯,hi,li，满足
1≤hi,j≤n
1
≤
h
i
,
j
≤
n
，
li≥2
l
i
≥
2
，
∑hi≤1000
∑
h
i
≤
1000
。
细胞可以连续分裂，会变成连续的细胞串。例如，1 分裂会变成 2 3，2 分裂会变成 1 3，3 分裂会变成 1 2 3，那么 2 1 3 这个细胞串分裂会变成 1 3 |2 3 |1 2 3（| 只是为了好看而写的分隔符，中间是连续的）。现在有一个长度为
m(1≤m≤1000)
m
(
1
≤
m
≤
1000
)
的目标细胞串
S
S
。一开始你有一个细胞 1。如果某一时刻细胞串中出现了 SS，就认为完成了目标。求细胞 1 最少要分裂多少次才能完成目标。如果不能完成目标，输出
−1
−
1
。
考场上的思路
暴力模拟……
想根据目标串还原回去，发现可能的情况无法确定。
由于
li≥2
l
i
≥
2
，因此还原回去时长度变成原来的
12
1
2
，只需要还原
O(logm)
O
(
log
m
)
层就变成了
1
1
个。
思路
首先很容易想到从目标串还原回去，很容易注意到还原一次后长度会减半。
考虑再还原会发生什么。根据前面的结论，我们现在会在一个细胞上，但是这个细胞不一定是 11。那么在最坏情况下，还要再走
O(n)
O
(
n
)
步才能走到
1
1
。因此我们得到一个不是那么有用的结论：答案并不是 O(logm)O(logm)，可能还要加上一个
O(n)
O
(
n
)
。
如果把细胞分裂看成一棵树的话，最后的
s
s
一定是连续的叶结点。我们找到它们的 LCA，就是还原回去的那个细胞。
我们从它们的 LCA 往下走一步，会得到至少两个细胞是目标串的祖先。不妨假设就只有两个细胞，现在考虑这么一个事情：我们以这两个细胞的中间为分割线，每次分裂后，左边只留下最靠右的至多 mm 个细胞，右边只留下最靠左的至多
m
m
个细胞。那么分裂一定次数后形成的目标串一定会被我们保存下来。这是个十分重要的性质，因为这允许了我们在程序中实现细胞分裂的过程。我们只用保存至多 2m2m 个细胞即可。
那么就很自然地想到枚举这个分割点。对于每种细胞分裂后会形成的细胞串，我们枚举分割点，然后模拟
10
10
次（
O(logm)
O
(
log
m
)
）分裂的过程，每次分裂后去寻找是否存在目标串，如果找到了，就更新答案。如何更新答案呢？首先肯定要算上模拟的次数，然后就考虑形成单个细胞要分裂多少次。显然这个可以用 BFS 来实现。时间复杂度
O(lmlogm)
O
(
l
m
log
m
)
。
但是这样一定可以枚举到答案吗？先前我们正在假设以两个细胞的中间为分割线，分裂后目标串会在分割线的左右两侧进行分布。模拟一下这个过程，发现这么一个问题：现在是两个细胞，分裂后，仍然只有两个细胞是目标串的祖先（显然一个在分割线左边，一个在分割线右边）。发现这个局面和分裂前好像没什么区别啊。但是这并不意味着无解，可能一直分裂下去会找到合适的一对，然后就能在
O(logm)
O
(
log
m
)
次分裂内得到解了。而这个过程进行的次数远远不止
O(n+logm)
O
(
n
+
log
m
)
次，可以达到
O(n2+logm)
O
(
n
2
+
log
m
)
次。如果像前面那样从一个结点处理走，那就会漏解。
另外，如果 LCA 下面至少有
3
3
个点是目标串的祖先，那么一定能在 O(logm)O(logm) 次扩展后出解，因为中间的结点一定属于目标串，它们一定会翻倍。所以剩下的情况只有 LCA 下面有
2
2
个点是目标串的祖先。
解决方法很自然可以想到枚举开始的两个结点，然后扩展 O(logm)O(logm) 层。计算答案的方法与以一个结点为 LCA 时相同，先用 BFS 预处理出现这两个结点的最小次数，然后加上扩展次数即可（当然如果没有出现过就不要去扩展了）。问题是，这样做的时间复杂度是
O(n2mlogm)
O
(
n
2
m
log
m
)
，似乎很难通过？不过很好，有
23
23
分了 QAQ。
考虑如果能够匹配目标串意味着什么。这意味着在扩展了
k
k
层后左边部分的结尾接上右边部分的开头等于 SS，也就意味着左边部分的结尾是
S
S
的前缀，右边部分的开头是 SS 的后缀。
如果我们能预处理左边部分的后缀是
S
S
的前缀的有哪些，右边部分的前缀是 SS 的后缀的有哪些，那么我们只需要检查一下有没有长度加起来等于
|S|
|
S
|
的就知道符不符合条件了；或者，检查有没有左边的结尾 + 1 等于右边的开头的，这个可以用 bitset 实现。
我们用 KMP 算法。对于左边的，我们从左往右匹配
S
S
。当进行完 KMP 算法后，当前匹配点就是 SS 的前缀，通过 border 进行跳跃我们就能得到所有是
S
S
的前缀的位置。右边同理，把 SS 反转后从右往左匹配即可。检查时，只需要检查两个集合是否有交即可。时间复杂度
O(nmlogm+n2mlogm÷32)
O
(
n
m
log
m
+
n
2
m
log
m
÷
32
)
，足以通过。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::
cin;
using std::
cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a =
0;
bool positive =
true;
char ch = getchar();
while (!(
std::
isdigit(ch) || ch ==
'-')) ch = getchar();
if (ch ==
'-')
{
positive =
false;
ch = getchar();
}
while (
std::
isdigit(ch))
{
(a *=
10) -= ch -
'0';
ch = getchar();
}
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[
20];
int length =
0;
if (x <
0)
putchar(
'-');
else x = -x;
do buffer[length++] = -(x %
10) +
'0';
while (x /=
10);
do putchar(buffer[--length]);
while (length);
putchar(
'\n');
}
const int maxn =
1005;
int n, m;
std::
vector<int> seq[maxn];
int target[maxn];
#define RunInstance(x) delete new x
struct brute
{
int buffer[
10000000];
void make(
int depth,
int cnt)
{
if (!depth)
{
buffer[++buffer[
0]] = cnt;
return;
}
for (
int i =
0; i < seq[cnt].size(); i++)
make(depth -
1, seq[cnt][i]);
}
brute()
{
int ans =
1;
for (; ans <=
5; ans++)
{
buffer[
0] =
0;
make(ans -
1,
1);
bool bOk =
false;
for (
int i =
1; i <= buffer[
0]; i++)
{
bool bFound =
true;
for (
int j =
1; j <= m; j++)
{
if (i + j -
1 > buffer[
0])
{
bFound =
false;
break;
}
if (buffer[i + j -
1] != target[j])
{
bFound =
false;
break;
}
}
if (bFound)
{
bOk =
true;
break;
}
}
if (bOk)
break;
}
printOut(ans >
5 ? -
1 : ans);
}
};
struct work
{
int g1[maxn];
int g2[maxn][maxn];
void GetG1()
{
memset(g1,
0,
sizeof(g1));
std::
vector<int> q;
g1[
1] =
1;
q.push_back(
1);
int head =
0;
while (head < q.size())
{
int from = q[head++];
std::
vector<int>& s = seq[from];
for (
int i =
0; i < s.size(); i++)
{
if (!g1[s[i]])
{
g1[s[i]] = g1[from] +
1;
q.push_back(s[i]);
}
}
}
}
void GetG2()
{
memset(g2,
0,
sizeof(g2));
std::
vector<std::pair<int, int> > q;
{
std::
vector<int>& s = seq[
1];
for (
int i =
1; i < s.size(); i++)
{
if (!g2[s[i -
1]][s[i]])
{
g2[s[i -
1]][s[i]] =
2;
q.push_back(
std::make_pair(s[i -
1], s[i]));
}
}
}
int head =
0;
while (head < q.size())
{
std::pair<
int,
int> from = q[head++];
std::
vector<int>& s1 = seq[from.first];
for (
int i =
1; i < s1.size(); i++)
{
if (!g2[s1[i -
1]][s1[i]])
{
g2[s1[i -
1]][s1[i]] = g2[from.first][from.second] +
1;
q.push_back(
std::make_pair(s1[i -
1], s1[i]));
}
}
std::
vector<int>& s2 = seq[from.second];
for (
int i =
1; i < s2.size(); i++)
{
if (!g2[s2[i -
1]][s2[i]])
{
g2[s2[i -
1]][s2[i]] = g2[from.first][from.second] +
1;
q.push_back(
std::make_pair(s2[i -
1], s2[i]));
}
}
if (!g2[s1.back()][s2.front()])
{
g2[s1.back()][s2.front()] = g2[from.first][from.second] +
1;
q.push_back(
std::make_pair(s1.back(), s2.front()));
}
}
}
int f[maxn];
std::
bitset<1002> left[
11][maxn];
std::
bitset<1002> right[
11][maxn];
void initFailureS()
{
f[
0] = f[
1] =
0;
int pre =
0;
for (
int i =
1; i < m; i++)
{
while (pre && target[pre +
1] != target[i +
1]) pre = f[pre];
if (target[pre +
1] == target[i +
1]) pre++;
f[i +
1] = pre;
}
}
int temp[maxn];
int cnt[maxn];
void GetLeft(
int idx,
int depth)
{
if (depth >
10)
return;
if (!depth)
{
temp[
0] = cnt[
0] =
0;
cnt[++cnt[
0]] = idx;
temp[++temp[
0]] = idx;
}
else
{
temp[
0] =
0;
for (
int i =
1; i <= cnt[
0] && temp[
0] < m; i++)
{
const std::
vector<int> s = seq[cnt[i]];
for (
int j = s.size() -
1; ~j && temp[
0] < m; j--)
temp[++temp[
0]] = s[j];
}
cnt[
0] = temp[
0];
for (
int i =
1; i <= cnt[
0]; i++)
cnt[i] = temp[i];
std::reverse(temp +
1, temp +
1 + temp[
0]);
}
int match =
0;
for (
int i =
1; i <= temp[
0]; i++)
{
while (match && temp[i] != target[match +
1])
match = f[match];
if (temp[i] == target[match +
1]) match++;
}
while (match)
{
if (match != m)
{
left[depth][idx].
set(match);
if (match !=
1)
int a =
0;
}
match = f[match];
}
GetLeft(idx, depth +
1);
}
void GetRight(
int idx,
int depth)
{
if (depth >
10)
return;
if (!depth)
{
temp[
0] = cnt[
0] =
0;
cnt[++cnt[
0]] = idx;
temp[++temp[
0]] = idx;
}
else
{
temp[
0] =
0;
for (
int i =
1; i <= cnt[
0] && temp[
0] < m; i++)
{
const std::
vector<int> s = seq[cnt[i]];
for (
int j =
0; j < s.size() && temp[
0] < m; j++)
temp[++temp[
0]] = s[j];
}
cnt[
0] = temp[
0];
for (
int i =
1; i <= cnt[
0]; i++)
cnt[i] = temp[i];
std::reverse(temp +
1, temp +
1 + temp[
0]);
}
int match =
0;
for (
int i =
1; i <= temp[
0]; i++)
{
while (match && temp[i] != target[match +
1])
match = f[match];
if (temp[i] == target[match +
1]) match++;
}
while (match)
{
if (match != m)
{
right[depth][idx].
set(m - match);
if (match !=
1)
int a =
0;
}
match = f[match];
}
GetRight(idx, depth +
1);
}
int tempA[maxn];
int tempB[maxn];
int tempAll[maxn *
2];
void GetCut(
int idx,
int pos)
{
tempA[
0] = tempB[
0] =
0;
const std::
vector<int>& s = seq[idx];
for (
int i = pos -
1; ~i; i--)
tempA[++tempA[
0]] = s[i];
for (
int i = pos; i < s.size(); i++)
tempB[++tempB[
0]] = s[i];
int depth =
1;
for (; depth <=
10; depth++)
{
tempAll[
0] =
0;
for (
int i = tempA[
0]; i; i--)
tempAll[++tempAll[
0]] = tempA[i];
for (
int i =
1; i <= tempB[
0]; i++)
tempAll[++tempAll[
0]] = tempB[i];
int match =
0;
for (
int i =
1; i <= tempAll[
0]; i++)
{
while (match && tempAll[i] != target[match +
1])
match = f[match];
if (tempAll[i] == target[match +
1]) match++;
if (match == m)
{
if (!~ans || ans > g1[idx] + depth)
ans = g1[idx] + depth;
return;
}
}
temp[
0] =
0;
for (
int i =
1; i <= tempA[
0] && temp[
0] < m; i++)
{
const std::
vector<int> s = seq[tempA[i]];
for (
int j = s.size() -
1; ~j && temp[
0] < m; j--)
temp[++temp[
0]] = s[j];
}
tempA[
0] = temp[
0];
for (
int i =
1; i <= tempA[
0]; i++)
tempA[i] = temp[i];
temp[
0] =
0;
for (
int i =
1; i <= tempB[
0] && temp[
0] < m; i++)
{
const std::
vector<int> s = seq[tempB[i]];
for (
int j =
0; j < s.size() && temp[
0] < m; j++)
temp[++temp[
0]] = s[j];
}
tempB[
0] = temp[
0];
for (
int i =
1; i <= tempB[
0]; i++)
tempB[i] = temp[i];
}
}
int ans;
work() : ans(-
1)
{
GetG1();
if (m ==
1)
{
printOut(g1[target[
1]] ? g1[target[
1]] : -
1);
return;
}
GetG2();
initFailureS();
for (
int i =
1; i <= n; i++)
GetLeft(i,
0);
for (
int i =
1; i <= n; i++)
for (
int j =
1; j < seq[i].size(); j++)
if (g1[i])
GetCut(i, j);
std::reverse(target +
1, target +
1 + m);
initFailureS();
for (
int i =
1; i <= n; i++)
GetRight(i,
0);
for (
int i =
1; i <= n; i++)
for (
int j =
1; j <= n; j++)
if (g2[i][j])
for (
int k =
0; k <=
10; k++)
if ((left[k][i] & right[k][j]).any())
if (!~ans || ans > g2[i][j] + k)
ans = g2[i][j] + k;
printOut(ans);
}
};
void run()
{
n = readIn();
m = readIn();
for (
int i =
1; i <= n; i++)
{
seq[i].resize(readIn());
for (
int j =
0; j < seq[i].size(); j++)
seq[i][j] = readIn();
}
for (
int i =
1; i <= m; i++)
target[i] = readIn();
RunInstance(work);
}
int main()
{
#ifndef LOCAL
freopen(
"cell.in",
"r", stdin);
freopen(
"cell.out",
"w", stdout);
#endif
run();
return 0;
}
为什么没有想到
看思路，一个显然的原因是走到 LCA 时就没有继续往上走了，也没有再往下走，就这么卡在这了。
另一个原因是我一直在想用 AC 自动机匹配回去，虽然这样显然不可行，但是我就是卡在这儿了。有点被算法卡住的感觉。
总结
现在的题的思维性都很强，基本没有固定的算法。有些题虽然看似复杂，但很简单，原因就是它们被算法死死地限制着，但是只要你会算法就简单了。但是像这道题不受算法约束的题很多，做它们还是要靠智商。
