目录

2020.08.15-2020.08.21 周报

团队训练

无。

_wzx27

专题

FFT 的一些奇妙用法

题目

暂无。

比赛

暂无。

Infinity37

专题

codeforces dp tag 随便做

题目

暂无。

比赛

暂无。

Zars19

专题

无。

题目

无。

比赛

Educational Codeforces Round 93 (Rated for Div. 2) zars19 DONE

本周推荐

Infinity37

来源:codeforces 1389F

tag:线段树优化dp/二分图匹配模型转化

概述

给定n个线段,每个线段都有一个颜色,总共有两种颜色。定义一种坏的线段对为两个线段颜色不相同同时有相交的部分,问最多可以选择多少个线段同时两两不为坏的线段对。

答案

线段树优化dp的答案大家都能想到,但是有一个更妙的转化。我们把每个线段看成一个点,然后在能组成坏的线段对的点上连边,之后我们要求的就是一个最大独立集。因为该图的一些性质可以直接进行贪心匹配。

comments:巧妙的模型转化,图的性质使得可以贪心进行二分图匹配。

_wzx27

来源CF1334G

tag:FFT,字符串匹配

概述:在普通匹配的基础上添加条件 $p(s_i)=t_i$ 时也算匹配。$p$ 是题目给的一个置换。

答案

普通的匹配是可以直接用 $\text{KMP}$ 做的,但 $\text{KMP}$ 需要满足一种等价关系,而加了题目中的条件就不存在这种等价关系了。因为:$p(s_i) = t_p 且 s_j = t_p$ 不能推出 $s_i = s_j$ 不满足传递性。

所以考虑构造多项式 $ f(x) = \sum _{i=0}^{m-1} (s_i-t_{x-m+i+1})^2 \cdot (p(s_i) - t_{x-m+i+1}) $,在 $t$ 串的 $u$ 位置成功匹配当且仅当 $f(u) = 0$。具体细节在这里

comments:用 FFT 匹配做字符串匹配,拓宽了 FFT 的用法

Zars19

来源CF1394A

tag:简单题。

概述:第 $i$ 天取笑Boboniu可以获得 $a_i$ 快乐值。如果当天没有被禁言,就会取笑Boboniu,而当某天取笑Boboniu后如果 $a_i>m$ 接下来的 $d$ 天将会被禁言。现在你可以重新排列 $a_i$ 得到最大的快乐值之和。

答案:排序,枚举被遮盖的天数,判断是否可行以及计算快乐值有一些细节,容易出错。

comments:虽然是很简单的题但容易有一些秘制错误,当晚fst了很多人,卡住也很容易崩心态。