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/18--2020/07/24 周报 ======

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

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

==== 专题 ====

[[..:bsgs]]

==== 比赛 ====

==== 题目 ====

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

==== 专题 ====

[[..:jxm2001:图论_3|图论 3]]

[[..:jxm2001:矩阵树定理|矩阵树定理]]

==== 比赛 ====

无

==== 题目 ====

见专题部分

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

==== 专题 ====

[[..:后缀数组_lgwza|后缀数组]]
==== 比赛 ====

[[..:codeforces_round#658 (Div. 2)_lgwza|Codeforces Round #658 (Div. 2)]] ''%%pro:4/5/6  rk:1181/14672%%''
==== 题目 ====

===== 本周推荐 =====

==== 姜一凡 ====

[[https://www.luogu.com.cn/problem/P3846|洛谷p3846]]

== 分类 ==

BSGS

== 大致题意 ==

求 $b^l=n(mod p)$ 对于 $l$ 的最小整数解

== 题解 ==

BSGS模板题，直接套模板即可。

==== 蒋贤蒙 ====

===  餐巾计划问题 ===

[[https://www.luogu.com.cn/problem/P1251|洛谷p1251]]

== 分类 ==

网络流

== 题意 ==

一个餐厅第 $i$ 天需要 $r_i$ 条新餐巾，每条新餐巾用完后得到旧餐巾，一开始餐厅没有餐巾。

买一条新餐巾费用为 $p$；快洗一条旧餐巾时间为 $m$ 天，费用为 $f$；慢洗一条旧餐巾时间为 $n$ 天，费用为 $s$。

数据保证 $f\gt s,m\lt n$，问餐厅营业 $N$ 天的最小花费。 

== 题解 ==

把一天分成一天的开始和一天的结束，一天的开始需要提供 $r_i$ 条新餐巾，于是连一条容量为 $r_i$ 费用为 $0$ 的边到汇点。

接下来考虑三种获取新餐巾的操作。首先可以买新餐巾，对应源点连一条容量为 $\inf$ 费用为 $p$ 的边到当天的开始。

另外也可以通过清洗之前的旧餐巾获得。不妨假设如果旧餐巾洗完就会被立即使用，不然可以留到以后再洗。这样假设的目的是减少连边数量。

于是第 $i$ 天的结束向第 $i+m$ 天的开始连一条容量为 $\inf$ 费用为 $f$ 的边，向第 $i+n$ 天的开始连一条容量为 $\inf$ 费用为 $s$ 的边。

再考虑维护旧餐巾，旧餐巾可以通过两种方式获取。

首先一天的结束将有 $r_i$ 条新餐巾变成旧餐巾，于是从源点连一条容量为 $r_i$ 费用为 $0$ 的边到一天的结束。

另外旧餐巾也可以继承前一天剩下的未被清洗的旧餐巾，对应每天结束向第二天结束连一条容量为 $\inf$ 费用为 $0$ 的边。

最后跑最小费用最大流即可。

== 评价 ==

一道比较考察建模能力的网络流题。

==== 王赵安 ====

[[https://www.luogu.com.cn/problem/P4051|P4051 JSOI2007字符加密]]

** 分类 **：后缀数组

** 简要题意 **：寻找最小的循环移动位置

** 解法 **：把字符串接到自己后面变成长度为 $2len$ 以后直接求后缀数组。按题目要求输出结尾的字符就好了

** 评价 **：经过理解转化后可发现这是道后缀数组裸题
CVBB ACM Team

用户工具

站点工具

页面工具
