Difference between revisions of "2019 ECNU XCPC April Selection 2"

From EOJ Wiki
Jump to navigation Jump to search
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 D ==
+
== Problem E ==
  
 
涉及算法:最小表示法。
 
涉及算法:最小表示法。
Line 35: Line 43:
 
自行查阅资料。
 
自行查阅资料。
  
== Problem E ==
+
== Problem F ==
  
 
涉及算法:AC 自动机。
 
涉及算法:AC 自动机。
  
 
AC 自动机匹配模版题。
 
AC 自动机匹配模版题。
 
== Problem F ==
 
 
涉及算法:后缀自动机
 

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 自动机匹配模版题。