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: 比赛公告

ddk的良心模拟赛 公告

在网课的间隙,你是否会感到空虚;

在作业的尽头,你是否会滋生焦虑;

你是否还在吐槽着练习题的千篇一律,

抑或是疫情之下无法出门的枯燥无趣?

那么,放下你的鼠标,握起你的妙笔,

“退群杯” “ddk的良心模拟赛”,发挥你卓越的才能!

大家好!我不是EncodeTalker,我是ddk,一位刚学OI大概10天的萌新,喜欢唱跳rap爆零射箭。EncodeTalker是我的一位可爱的圆滚滚的学长(雾)。

有一天,我拿着我刚学OI时遇到的难题去问我的学长,学长沉思了$(10^9+7) s$后,说“这些题实在太简单了,我分分钟切爆,而且我可以把它们加强哦。我来看看你会不会做加强版吧。“看着一道道我不会的题目,我只能来求助各位了。

本次比赛将于2020年2月29日下午2:00开始,将进行4.5h,共有5个题目,其中包含一道交互题,如果您对交互题了解较少,可以参照这个题的“使用交互库”的评测方式。

希望大家能帮助来自乌干达的可怜的ddk,祝大家在切题的时候都能“ちまちませずに、ドーンと行くぜ!”(雾)

注:本次比赛全程提供赛时答疑,如对题目有任何疑问可直接询问我的学长EncodeTalker.

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 – 题解"