Difference between revisions of "2019 ECNU XCPC April Selection 2"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 14: | Line 14: | ||
== Problem A == | == Problem A == | ||
| + | |||
| + | 涉及算法：后缀平衡树。 | ||
| + | |||
| + | 我出我自己又来了。 | ||
| + | |||
| + | [[https://acm.ecnu.edu.cn/blog/entry/284/ F题解]] | ||
== Problem B == | == Problem B == | ||
== Problem C == | == Problem C == | ||
| + | |||
| + | == Problem D == | ||
涉及算法：KMP。 | 涉及算法：KMP。 | ||
| Line 27: | Line 35: | ||
不知道对于每一位都是$Next$嵌套会不会$TLE$。但是可以通过 dp 做到线性的。 | 不知道对于每一位都是$Next$嵌套会不会$TLE$。但是可以通过 dp 做到线性的。 | ||
| − | == Problem | + | == Problem E == |
涉及算法：最小表示法。 | 涉及算法：最小表示法。 | ||
| Line 35: | Line 43: | ||
自行查阅资料。 | 自行查阅资料。 | ||
| − | == Problem | + | == Problem F == |
涉及算法：AC 自动机。 | 涉及算法：AC 自动机。 | ||
AC 自动机匹配模版题。 | AC 自动机匹配模版题。 | ||
| − | |||
| − | |||
| − | |||
| − | |||
Revision as of 05:54, 6 April 2019
2019 ECNU XCPC April Selection 2
开始算法专题场。
如果做的很不顺手的，需要阅读相关资料来提高。
推荐阅读
我自己写的这篇文章仅包含基础的三个匹配算法及其应用。
Problem A
涉及算法：后缀平衡树。
我出我自己又来了。
[F题解]
Problem B
Problem C
Problem D
涉及算法：KMP。
对于一个字符串的前缀$x$，显然前缀$Next[x]$是最大公共前后缀，$Next[Next[x]]$也是他的公共前后缀。
于是最大的循环节就是最后一个$Next$嵌套中$Next[y]=0$的前缀$y$。
不知道对于每一位都是$Next$嵌套会不会$TLE$。但是可以通过 dp 做到线性的。
Problem E
涉及算法：最小表示法。
模版题。
自行查阅资料。
Problem F
涉及算法：AC 自动机。
AC 自动机匹配模版题。