hycqwq

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 的实现，感觉只讲了一些表面的浅层内容。有个人问：「我们明天的工程题...

A Dark Room

0 条评论 杂谈 无标签 hycqwq
https://adarkroom.doublespeakgames.com/?lang=zh_cnThis is a dark room.你，不知为何，出现一个漆黑的房间中。你生起一团火。有一个陌生人循着火光走来，你不知道她是谁，但是为了在这刺骨的寒夜中生存下来，你让她留了下来。你们开始到森林里伐木，拥有建造技术的她建起了一个陷阱，用来捕捉猎物。你们在林中建起一栋小屋，很快就有流浪者在此定...

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...

给博客换了个字体

0 条评论 水文 无标签 hycqwq
新年新气象，今天给博客换了个字体 =w=，用的是仓耳今楷 05-W04 呐太好看了呜呜字体文件在 https://cdn.hycqwq.top/font/CangErJinKai-05-W04.ttf，想要的可以自取呀~水文章

题解 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$