CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
[[http://112.74.186.118/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95|back]]

====== 2020/07/11--2020/07/17 周报 ======

===== 团队训练 =====

===== 姜一凡 =====

==== 专题 ====

[[..:计算几何]]

==== 比赛 ====

无

==== 题目 ====

===== 蒋贤蒙 =====

==== 专题 ====

[[..:jxm2001:树套树|树套树 1]]

[[..:jxm2001:图论_1|图论 1]]

[[..:jxm2001:图论_2|图论 2]]

==== 比赛 ====

无

==== 题目 ====

见专题部分

===== 王赵安 =====

==== 专题 ====

[[..:字符串基础_lgwza|字符串基础]]

[[..:字符串匹配_lgwza|字符串匹配]]

[[..:字符串哈希_lgwza|字符串哈希]]

[[..:字典树_trie_lgwza|字典树(Trie)]]

[[..:前缀函数与_kmp_算法_lgwza|前缀函数与 KMP 算法]]
==== 比赛 ====

无
==== 题目 ====

见专题部分
===== 本周推荐 =====

==== 姜一凡 ====

[[https://www.luogu.com.cn/problem/P1742|洛谷p1742]]

最小圆覆盖模板

==== 蒋贤蒙 ====

[[https://www.luogu.com.cn/problem/P5192|洛谷p5192]]

=== 分类 ===

网络流

=== 题意 ===

一个摄影师，$n$ 天时间，$m$ 个取材对象。要求 $n$ 天后第 $x$ 个取材对象至少需要取材 $G_x$ 张照片。

第 $k$ 天可以取材 $C_k$ 个对象，总共可以取材 $D_k$ 张照片，当天每个可取材对象的取材照片数量必须在区间 $[L_{k_i},R_{k_i}]$ 内。

问是否存在满足条件的方案，如果存在输出总共可以取材的最大照片数，如果不存在输出 $-1$。

=== 题解 ===

把天和取材对象都当成一个节点，建有源上下界网络流图。

$n$ 天后第 $x$ 个取材对象至少需要取材 $G_x$ 张照片可以理解为第 $x$ 个取材对象代表节点向汇点连一条上下界为 $[G_x,\inf]$ 的边。

第 $k$ 天总共可以取材 $D_k$ 张照片可以理解为源点向第 $k$ 天代表节点连一条上下界为 $[0,D_k]$ 的边。

第 $k$ 天可取材对象的取材照片数量必须在区间 $[L_{k_i},R_{k_i}]$ 内可以理解为第 $k$ 天代表节点向第 $k_i$ 个取材对象连一条上下界为 $[L_{k_i},R_{k_i}]$ 的边。

最后求一下有源汇上下界的最大流即可。

=== 评价 ===

一道不错的有源汇上下界最大流练习题。

==== 王赵安 ====

[[https://codeforces.com/contest/1200/problem/E|CF1200E Compress Words]]

=== 分类 ===
哈希、KMP

=== 简要题意 ===
给你若干个字符串，答案串初始为空。第 $i$ 步将第 $i$ 个字符串加到答案串的后面，但是尽量地去掉重复部分（即去掉一个最长的、是原答案串的后缀、也是第 $i$ 个串的前缀的字符串），求最后得到的字符串。

字符串个数不超过 $10^5$，总长不超过 $10^6$。

=== 解法 ===
法一：每次需要求最长的、是原答案串的后缀、也是第 $i$ 个串的前缀的字符串。枚举这个串的长度，哈希比较即可。

法二：用 KMP 算法解决。构造一个待拼接串在**前**,当前拼接好的串在**后**的新串，求出当前拼接好的串的**最后一个字符**的 $\pi[i]$，即为重复的前、后缀的最长长度

=== 评价 ===
一道比较基础的题。有助于哈希和 KMP 算法的理解。
CVBB ACM Team

用户工具

站点工具

页面工具
