Posted in: 比赛公告

「FZOI」Round #30 – (ICPC) 公告

经历了漫长的疫情封锁,我们终于会在 5 月份摆脱 COVID-19 的影响回到学校。回到学校前,是否竞赛手感下降、智力下降甚至颜值下降?本次的「FZOI」Round #30 - (ICPC) 就是给各大即将返校的选手准备的训练赛。

本次比赛的题目来自于组题人 @kal0rona 在各大 OJ 上刷到的一些比较适合恢复手感的题目,平均难度在 NOIp 提高组或 Codeforces Div.2 难度之上,但是峰值难度低于 Codeforces Div.2。

本次比赛分成两个 Episode,开始时间分别为 5 月 2 日和 5 月 3 日的下午 14:00 至 17:00。赛后将会提供视频讲解。

为了更好的让选手从这次比赛中得到恢复和训练,本次的比赛允许三人进行组队、并且提前准备模版,但仍然要遵守 ICPC 赛制的纪律。FZOI 成员中被发现任何学术作弊的行为都将会得到严厉的惩罚。

希望这次大家玩得开心。

Posted in: 算法讲稿

上下界网络流 – 学习笔记

标定

考虑每条边的流量范围:$b(u, v) \leq f(u, v) \leq c(u, v)$。

无源汇上下界可行流

首先我们给这条边标入最大限制 $c(u, v) - b(u, v)$,并默认认为该边已经流入了 $b(u, v)$ 的流量,然后我们可以给每个点设置一个 $M_i$ 来进行流量搜集。

如果:

  • $M_i = 0$,那没啥问题。
  • $M_i > 0$,说明下界要求流入的流量更多,所以我们从附加源点 $S$ 连到此点。
  • $M_i < 0$,同理,说明下界要求流出的流量更多,所以我们专门开辟一个通道为此点流出至附加汇点 $T$。

代码:

Read More "上下界网络流 – 学习笔记"

Posted in: QuestOJ 比赛题解

「FZOI」OI 寒假赛 #12 Div.1 – 题解

A - 幼儿园

这道题的来源是 CF Div.2 D,只有 20 多个人过了。我在比赛的时候差点把这题写出来,然后因为一些玄学错误彻底 GG。

无疑,这是正常比赛中最难的题。但是这道题并不难想:我们可以把多个线段的端点提取出来,然后做一次「线段剖分」。如下图所示:

Read More "「FZOI」OI 寒假赛 #12 Div.1 – 题解"

Posted in: QuestOJ 比赛题解

「FZOI」OI 寒假赛 #1 Div.1 – 题解

A - 资本家 kal0rona

我们可以考虑把每个员工的前缀收益放在折线图上进行考虑:一条折线从$(1, 0)$出发,在$(x, y)$向上走就是给第$x$个员工发钱,上升高度就是发钱数量。最后,把老板当作第$n + 1$个员工即可。可以发现,因为这个是前缀收益,所以最后我们会走到$(n + 1, m)$,我们只需要算从$(1, 0)$到$(n + 1, m)$的不降路径数即可,也就是${n + m \choose m}$。

Read More "「FZOI」OI 寒假赛 #1 Div.1 – 题解"

Posted in: 解题报告

HNOI 2018 省队集训 Day 1 – 解题报告

A - Tree

这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 $1$ 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 $root$ 时,$u, v$ 之间的 $LCA$ 显然是 $lca(u, v), lca(root, u), lca(root, v)$ 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。

Read More "HNOI 2018 省队集训 Day 1 – 解题报告"