OI

Johnson 全源最短路算法学习笔记

0 条评论 OI 笔记 无标签 hycqwq
Floyd 算法可以以 $O(n^3)$ 的时间求得图上全源最短路。然而这个复杂度在许多题目中是不可接受的。这时我们可以使用另外一种全源最短路算法 Johnson。Johnson 全源最短路径算法 - OI Wiki引入考虑到全源最短路就相当于对每个节点跑一边单源最短路，我们尝试在 $n$ 次单源最短路的基础上做一些优化。跑 $n$ 次 Dijkstra，总复杂度为 $O(nm \log m...

网络流学习笔记

0 条评论 OI 笔记 无标签 hycqwq
网络流（network flow）就是一个网络（有向图）上的流。网络流简介 - OI Wiki一、前置知识1.1 割（cut）把网络分为 $S, T$ 两部分，使得源点在 $S$ 中，汇点在 $T$ 中，其容量 $V$ 为所有从 $S$ 到 $T$ 的边的容量之和，这就是一个割。1.2 增广路（augmenting path）从源到汇的流（经过的边的流量的最小值）大于 $0$ 的路径。1.3...

THUWC 2024 游记

0 条评论 OI 游记 无标签 hycqwq
Day 0 | 2024.01.26坐飞机落地 CKG。报到领了东西，忘记去上机测试了。/kkDay 1 | 2024.01.27上午直接上机，8 点到 13 点共 5 小时。/fad啥没写出来遗憾离场。下午拍完照（牌子上「男士」写成「男土」了 /xk）去礼堂听专题讲座开大会，结果前半段时间在看表演、听序言什么玩意。讲 AI 的实现，感觉只讲了一些表面的浅层内容。有个人问：「我们明天的工程题...

GDKOI 2024 游记

0 条评论 OI 游记 无标签 hycqwq
又来 GDKOI 了。在提高抱铃不如在普及拿点分。Day 0 | 2024.01.05上完一整天课才去的，难受。和去年一样的东西，听说普及有纪念牌，但是没拿到。Day 1 | 2024.01.06松湖莞中好大啊，差点迷路。早上讲构造题，听懂 $\frac{4}{5}$。下午题就是一坨，做法全部写假，估分 $0$。四题总共两个大样例，平均每题半个。/oh/oh/ohDay 2 | 2024.0...

题解 ATabc334F Christmas Present 2

0 条评论 OI 题解 无标签 hycqwq
小蒟蒻想不出 $O(n)$ 的解法，来交一发二维 dp 加优化的题解。Problem圣诞老人要按顺序给 $n$ 个人送礼物，每个人（包括它自己）家都有一个坐标，而圣诞老人手上最多只能拿 $k$ 个礼物（这就意味着他可能要在送完某些人之后回家补充礼物），求他给所有人送完礼物再回到自己家所需要走的最短距离。Solution考虑 $dp_{i, j}$ 表示当前已经送完了前 $i$ 个人的礼物，（...

题解 CF1900D Small GCD

1 条评论 OI 题解 无标签 hycqwq
赛时没做出来。第二天把题告诉同机房大佬，想了一天说不会 /ch。后面看了官方题解，同时感谢这位佬 /bx。Solution与官方题解相似。定义：$m = \max\limits_{j = 1}^n a_j$。$cg_i$ 表示对于任意 $1 \le x < y < z \le n$，$f(a_x, a_y, a_z) = i$ 的 $(x, y, z)$ 个数；$cm_i$ 表示...

停课集训小记

2 条评论 OI 游记 无标签 hycqwq
停课去高中部，真爽。Day 1 / 2023.10.30 / flag: AC10第一天，进门的时候保安把我们（有 4 个）拦住了（把校卡拿去开通高中权限，结果免费旧卡换新，还是高中部的样式，赚大了。做杂题，过了 P2947 P1559 P4376。进度：3 / 10还安排了一场 CF，结果 C 题吃了 6 发罚时。。题目是 1886 的。进度：5 / 1011:58：离结束还有 12 分钟...

NOIP 2023 游记

0 条评论 OI 游记 无标签 hycqwq
CSP 考完，紧接着就是 NOIP。Day 0.1 / 2023.10.25-26教练说要停课集训了。希望能拿个一等。Day 1 / 2023.11.18考炸了。Day 2 / 2023.11.14$100 + 20 + 5 + 0 = 125$

CSP 2023 游记

1 条评论 OI 游记 无标签 hycqwq
CSP 2023 落幕，我才想起写游记。Tip：本文中的天数编号连续的，实际可能并不连续。Day 0.1 / 2023.08.*整个 8 月在搞普及，因为去年 J 组考的太差了甚至比前年 J 和去年 S 还低。别问是初赛还是复赛，这还要说吗。Day 0.2 / 忘了看周围人在疯狂看一本通，也不知道为啥。初赛不是随便写写就过了吗，为什么 lza 那么担心啊。Day 1 / 2023.09.16...

题解 CF1840D Wooden Toy Festival

0 条评论 OI 题解 无标签 hycqwq
Problem给定 $n$ 个数 $a_1, a_2, a_3, \cdots, a_n$，自选 $3$ 个数 $x, y, z$ 使$$\max\limits_{i = 1}^{n} \{\min\{|a_i - x|, |a_i - y|, |a_i - z|\}\}$$最小。求这个最小值。Solution考虑将 $a$ 分为 $3$ 个区间，使区间中最大数与最小数之差不超过 $m$，利...