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$