Difference between revisions of "2019 ECNU XCPC April Selection 2"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| (14 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | = 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 == | ||
== Problem C == | == Problem C == | ||
| + | |||
| + | == Problem D == | ||
| + | |||
| + | 涉及算法：KMP。 | ||
对于一个字符串的前缀$x$，显然前缀$Next[x]$是最大公共前后缀，$Next[Next[x]]$也是他的公共前后缀。 | 对于一个字符串的前缀$x$，显然前缀$Next[x]$是最大公共前后缀，$Next[Next[x]]$也是他的公共前后缀。 | ||
| Line 15: | Line 37: | ||
不知道对于每一位都是$Next$嵌套会不会$TLE$。但是可以通过 dp 做到线性的。 | 不知道对于每一位都是$Next$嵌套会不会$TLE$。但是可以通过 dp 做到线性的。 | ||
| − | == Problem | + | == 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