无。
暂无。
暂无。
暂无。
暂无。
无。
无。
来源:codeforces 1389F
tag:线段树优化dp/二分图匹配模型转化
概述:
给定n个线段,每个线段都有一个颜色,总共有两种颜色。定义一种坏的线段对为两个线段颜色不相同同时有相交的部分,问最多可以选择多少个线段同时两两不为坏的线段对。
答案:
线段树优化dp的答案大家都能想到,但是有一个更妙的转化。我们把每个线段看成一个点,然后在能组成坏的线段对的点上连边,之后我们要求的就是一个最大独立集。因为该图的一些性质可以直接进行贪心匹配。
comments:巧妙的模型转化,图的性质使得可以贪心进行二分图匹配。
来源: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 的用法
来源:CF1394A
tag:简单题。
概述:第 $i$ 天取笑Boboniu可以获得 $a_i$ 快乐值。如果当天没有被禁言,就会取笑Boboniu,而当某天取笑Boboniu后如果 $a_i>m$ 接下来的 $d$ 天将会被禁言。现在你可以重新排列 $a_i$ 得到最大的快乐值之和。
答案:排序,枚举被遮盖的天数,判断是否可行以及计算快乐值有一些细节,容易出错。
comments:虽然是很简单的题但容易有一些秘制错误,当晚fst了很多人,卡住也很容易崩心态。