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

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "= 2019 ECNU XCPC April Selection 2 = == Problem A == == Problem B == == Problem C == == Problem D == == Problem E == == Problem F ==")
 
 
(16 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
= 2019 ECNU XCPC April Selection 2 =
 
= 2019 ECNU XCPC April Selection 2 =
 +
 +
开始算法专题场。
 +
 +
如果做的很不顺手的，需要阅读相关资料来提高。
 +
 +
* 字符串场没有考裸的匹配题，因为知道大家手上都有模版，考了也没什么意思。
 +
 +
* 字符串总体来说难度还是比较大的。
 +
 +
== 推荐阅读 ==
 +
 +
[[http://xiejiadong.com/?p=331 字符串相关算法学习总结]]
 +
 +
我自己写的这篇文章仅包含基础的三个匹配算法及其应用。
  
 
== Problem A ==
 
== Problem A ==
 +
 +
涉及算法：后缀平衡树。
 +
 +
我出我自己又来了。
 +
 +
[[https://acm.ecnu.edu.cn/blog/entry/284/ F题解]]
  
 
== Problem B ==
 
== Problem B ==
Line 8: Line 28:
  
 
== Problem D ==
 
== Problem D ==
 +
 +
涉及算法：KMP。
 +
 +
对于一个字符串的前缀$x$，显然前缀$Next[x]$是最大公共前后缀，$Next[Next[x]]$也是他的公共前后缀。
 +
 +
于是最大的循环节就是最后一个$Next$嵌套中$Next[y]=0$的前缀$y$。
 +
 +
不知道对于每一位都是$Next$嵌套会不会$TLE$。但是可以通过 dp 做到线性的。
  
 
== Problem E ==
 
== Problem E ==
 +
 +
涉及算法：最小表示法。
 +
 +
模版题。
 +
 +
自行查阅资料。
 +
 +
这道题目用后缀数组来做也是模版题，但我想它卡掉，不知道有没有成功。
  
 
== Problem F ==
 
== Problem F ==
 +
 +
涉及算法：后缀数组。
 +
 +
考虑离线处理。将所有查询和母串相连建后缀数组。
 +
 +
对于每一个查询，在排好序的后缀数组中恰好有一段相对应，可以二分求得 $L,R$。问题就转换为在 $L,R$ 区间内有多少后缀的下标在查询区间范围内的。
 +
 +
这是一个非常经典的区间问题。继续考虑离线处理，从大往小将数插入，然后使用树状数组轻松解决。时间复杂度 $O(nlogn)$ 。
 +
 +
据验题人说暴力加疯狂特判也能过，而且玄学优化不可卡。暴力姿势太大，比不来。
 +
 +
== Problem G ==
 +
 +
非字符串题，用于签到。
 +
 +
找规律。
 +
 +
看似大整数，其实也是大整数，但是用不到 Biginteger。
 +
 +
或许和字符串有一丢丢的关系？—— Kilo_5723

Latest revision as of 09:32, 10 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

涉及算法：后缀数组。

考虑离线处理。将所有查询和母串相连建后缀数组。

对于每一个查询，在排好序的后缀数组中恰好有一段相对应，可以二分求得 $L,R$。问题就转换为在 $L,R$ 区间内有多少后缀的下标在查询区间范围内的。

这是一个非常经典的区间问题。继续考虑离线处理，从大往小将数插入，然后使用树状数组轻松解决。时间复杂度 $O(nlogn)$ 。

据验题人说暴力加疯狂特判也能过，而且玄学优化不可卡。暴力姿势太大，比不来。

Problem G

非字符串题，用于签到。

找规律。

看似大整数，其实也是大整数，但是用不到 Biginteger。

或许和字符串有一丢丢的关系？—— Kilo_5723

Retrieved from "http://acm.ecnu.edu.cn/wiki/index.php?title=2019_ECNU_XCPC_April_Selection_2&oldid=3397"