洛谷 P1081 [NOIP2012 提高组] 开车旅行 题解 发表于 2022-06-27 更新于 2024-04-13 分类于 Dumby的OI生涯 洛谷题目链接Acwing题目链接 思路先预处理出最近和次近的城市,记录下每次循环后所在城市的位置,然后倍增处理。 阅读全文 »
利用拓扑排序求 DAG 最短路 发表于 2022-02-14 更新于 2024-04-13 分类于 Dumby的OI生涯 背景给定一张带负权边的有向无环图(DAG),$N$ 个点,$M$ 条边,求源点到各点的最短路。 分析因为有负权边,无法用 dijkstra 直接求最短路。 用 SPFA 又容易被出题人卡成傻子。 考虑到是 DAG,可以使用拓扑排序在 $O\left( N+M \right)$ 时间范围内求出最短路。 阅读全文 »
!!!🏮新年好🏮!!! 发表于 2022-01-31 更新于 2024-04-13 分类于 站务 已经是22年了捏。 !!!🏮新年好🏮!!! Dumby_cat 隆重推出 Dumblog 新年款!!!(其实就是变红了。。。) 总之,祝各位来访者新年快乐!!!
一只蒟蒻的组合数学的入门笔记 发表于 2021-09-02 更新于 2024-04-13 分类于 Dumby的OI生涯 加法及乘法原理加法原理完成一件事有 $n$ 类方法,每类方法有 $m$ 个不同的方法,那么完成这件事总共就有 $N=m_{1}+m_{2}+…+m_{n}$ 种方法。 阅读全文 »
Luogu P5136 sequence 题解报告 发表于 2021-08-27 更新于 2024-04-13 分类于 Dumby的OI生涯 题目描述试求出: $\left \lceil \left ( \frac{1+\sqrt{5}}{2} \right )^{n} \right \rceil \bmod 998244353$ 多测 阅读全文 »
洛谷P3263题解报告 发表于 2021-08-26 更新于 2024-04-13 分类于 Dumby的OI生涯 洛谷P3263 题意描述给定 $b$、$d$ 和 $n$。 试求出: $\left \lfloor \left ( \frac{b+\sqrt{d} }{2} \right )^{n} \right \rfloor \bmod{p} $ 阅读全文 »
一只蒟蒻的并查集学习笔记 发表于 2021-07-06 更新于 2024-12-05 分类于 Dumby的OI生涯 并查集是甚么并查集(Disjoint-set data structure),直译为 “不交集数据结构”,顾名思义,它是种数据结构。并且,它是种用来处理 不交集(不相交集合)的合并和查询问题 的数据结构。并查集维护的是元素之间的关系。 阅读全文 »
一只蒟蒻的数论学习笔记(欧拉函数专题篇) 发表于 2021-07-02 更新于 2024-04-13 分类于 Dumby的OI生涯 定义1 到 $N$ 中与 $N$ 互质的数的个数被称为欧拉函数,记为 $\varphi(N)$。 函数式$\varphi \left ( n \right ) = n \times \prod_{i=1}^{m} \left ( 1-\frac{1}{p_{i}} \right )$ 阅读全文 »