差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:weekly16 [2020/08/21 11:26]
infinity37 [本周推荐]
+++ 2020-2021:teams:wangzai_milk:weekly16 [2020/08/21 16:34] (当前版本)
zars19 [_wzx27]
@@ 行 4: / 行 4: @@
 无。
 ===== _wzx27 =====
 ==== 专题 ====
+[[FFT 的一些奇妙用法]]
 ==== 题目 ====
+暂无。
 ==== 比赛 ====
+暂无。
 ===== Infinity37 =====
@@ 行 27: / 行 33: @@
 ==== 专题 ====
+无。
 ==== 题目 ====
+无。
 ==== 比赛 ====
+[[Educational Codeforces Round 93 (Rated for Div. 2) zars19]] **DONE**
 ===== 本周推荐 =====
 ==== Infinity37 ====
@@ 行 41: / 行 54: @@
 **概述**：
-给定一颗树和两套01权值，现在可以花费1的代价修改某点的权值，问最小修改几次可以使得第一套权值和第二套权值的树同构。
+给定n个线段，每个线段都有一个颜色，总共有两种颜色。定义一种坏的线段对为两个线段颜色不相同同时有相交的部分，问最多可以选择多少个线段同时两两不为坏的线段对。
 **答案**：
-先找到重心，以重心为根对树进行hash，如果有两个重心那就增加一个重心连接两个重心再进行树hash。
+线段树优化dp的答案大家都能想到，但是有一个更妙的转化。我们把每个线段看成一个点，然后在能组成坏的线段对的点上连边，之后我们要求的就是一个最大独立集。因为该图的一些性质可以直接进行贪心匹配。
+**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**：简单题。
-我们设状态$F_{i,j}$代表第一套权值的$i$子树与第二套权值的$j$子树同构的最小代价。具体转移要使用一个二分图完备匹配的费用流，对$i,j$这两棵树的所有子树，hash值相同并且树高相同的连接一条边，我们假设这两个点是$u,v$，这条边的流量为1，费用为$F_{u,v}$，然后依次转移即可。
+**概述**：第 $i$ 天取笑Boboniu可以获得 $a_i$ 快乐值。如果当天没有被禁言，就会取笑Boboniu，而当某天取笑Boboniu后如果 $a_i>m$ 接下来的 $d$ 天将会被禁言。现在你可以重新排列 $a_i$ 得到最大的快乐值之和。
-**comments**:费用流转移dp的另一道题目，和第十场的题目主要区别在于无根树的处理，找到重心进行树hash
+**答案**：排序，枚举被遮盖的天数，判断是否可行以及计算快乐值有一些细节，容易出错。
+**comments**：虽然是很简单的题但容易有一些秘制错误，当晚fst了很多人，卡住也很容易崩心态。

CVBB ACM Team

用户工具

站点工具

差别

页面工具