Description
给你一个由 NSEW*?[] 构成的模式串 $S$，意义为：
*：代表一个任意不定长度的可空串。?：代表一个不定的动作（NSEW）。[A]：代表 A 可以出现也可以不出现，其中 A 也是一个模式串。NSEW：代表对应动作（上、下、左、右）。
如果这个模式串能够匹配一个轨迹串，那么称这个轨迹是优美的。
现在给你 $n$ 个轨迹串 $s_i(1 \leq i \leq n)$，请你求出 $s_i$ 的每个前缀是不是优美的。
评测时自动启动 O2 优化。
Solution
比赛的时候想到了，但是觉得有括号嵌套，写起来会很复杂。
赛后写了以后发现其实是我想得太复杂了。
考虑设 $f_{i, j} = 0 / 1$ 表示串 $S$ 的前 $i$ 位和串 $s_i$ 的第 $j$ 位 不匹配 / 匹配，然后暴力转移即可。
遇到 [] 的话可以选择跳进去匹配或者跳过括号去匹配。
一开始找括号匹配的时候甚至连栈都没有用，都不知道自己哪来的勇气去测样例的……
Code
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
| #include <cstdio>
#include <cstring>
#define maxN 110
#define maxQ 1000010
char st[maxN], p[maxQ];
short f[maxN][maxQ];
int stack[maxQ], right[maxQ];
int main ()
{
scanf("%s", st + 1);
int lenSt = strlen(st + 1);
for(int i = 1;i <= lenSt; i++)
{
if(st[i] == '[')
{
stack[++stack[0]] = i;
}
else if(st[i] == ']')
{
right[stack[stack[0]]] = i;
stack[0]--;
}
}
int True = 0;
scanf("%d", &True);
True++;
while(--True)
{
scanf("%s", p + 1);
int lenP = strlen(p + 1);
f[0][0] = True;
for(int i = 0;i <= lenSt; i++)
{
for(int j = 0;j <= lenP; j++)
{
if(f[i][j] != True)
{
continue;
}
if(st[i + 1] == '?')
{
f[i + 1][j + 1] = True;
}
else if(st[i + 1] == '*')
{
f[i][j + 1] = True;
f[i + 1][j] = True;
f[i + 1][j + 1] = True;
}
else if(st[i + 1] == '[')
{
f[i + 1][j] = True;
f[right[i + 1]][j] = True;
}
else if(st[i + 1] == ']')
{
f[i + 1][j] = True;
}
else if(st[i + 1] == p[j + 1])
{
f[i + 1][j + 1] = True;
}
}
}
for(int i = 1;i <= lenP; i++)
{
printf("%d", f[lenSt][i] == True);
}
printf("\n");
}
return 0;
}
|