2020-2021:teams:wangzai_milk:weekly16
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly16 [2020/08/21 11:29] infinity37 [Infinity37] |
2020-2021:teams:wangzai_milk:weekly16 [2020/08/21 16:34] (当前版本) zars19 [_wzx27] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 无。 | 无。 | ||
| + | |||
| ===== _wzx27 ===== | ===== _wzx27 ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | [[FFT 的一些奇妙用法]] | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | 暂无。 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | 暂无。 | ||
| ===== Infinity37 ===== | ===== Infinity37 ===== | ||
| 行 27: | 行 33: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无。 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | 无。 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | [[Educational Codeforces Round 93 (Rated for Div. 2) zars19]] **DONE** | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| + | |||
| ==== Infinity37 ==== | ==== Infinity37 ==== | ||
| 行 49: | 行 62: | ||
| **comments**:巧妙的模型转化，图的性质使得可以贪心进行二分图匹配。 | **comments**:巧妙的模型转化，图的性质使得可以贪心进行二分图匹配。 | ||
| + | ==== _wzx27 ==== | ||
| + | |||
| + | **来源**：[[https://codeforces.com/problemset/problem/1334/G|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$。具体细节在[[FFT 的一些奇妙用法|这里]] 。 | ||
| + | |||
| + | **comments**：用 FFT 匹配做字符串匹配，拓宽了 FFT 的用法 | ||
| + | |||
| + | ==== Zars19 ==== | ||
| + | |||
| + | **来源**：[[http://codeforces.com/problemset/problem/1394/A|CF1394A]] | ||
| + | |||
| + | **tag**：简单题。 | ||
| + | |||
| + | **概述**：第 $i$ 天取笑Boboniu可以获得 $a_i$ 快乐值。如果当天没有被禁言，就会取笑Boboniu，而当某天取笑Boboniu后如果 $a_i>m$ 接下来的 $d$ 天将会被禁言。现在你可以重新排列 $a_i$ 得到最大的快乐值之和。 | ||
| + | |||
| + | **答案**：排序，枚举被遮盖的天数，判断是否可行以及计算快乐值有一些细节，容易出错。 | ||
| + | |||
| + | **comments**：虽然是很简单的题但容易有一些秘制错误，当晚fst了很多人，卡住也很容易崩心态。 | ||
2020-2021/teams/wangzai_milk/weekly16.1597980566.txt.gz · 最后更改: 2020/08/21 11:29 由 infinity37
