Marlin的博客 | Marlin's Blog

欧拉函数

欧拉函数（Euler’s Totient Function）欧拉函数是数论中的核心概念之一，广泛应用于密码学、模运算和群论等领域。它是指一个正整数 $n$ 与 $1, 2, \dots, n-1$ 互质的数的个数。 1. 什么是欧拉函数？对于正整数 $n$，欧拉函数 $\varphi(n)$ 定义为：小于或等于 $n$ 且与 $n$ 互素（即 $\gcd(k, n) ...

Posted by Marlin on October 1, 2025

质数判断、质因子分解、质数筛

质数判断、质因子分解、质数筛质数判断判断较小的数是否为质数试除法 $O(\sqrt n)$ 1 2 3 4 5 6 7 8 9 10 bool isPrime(int n){ if(n <= 1) return false; for(int i = 2; i * i <= n; i++){ if(n % i == 0...

Posted by Marlin on September 30, 2025

贪心经典专题 1

贪心狭义的贪心每一步都做出在当前状态下最好或最优的选择，从而希望最终的结果是最好或最优的算法广义的贪心通过分析题目自身的特点和性质，只要发现让求解答案的过程待得到加速的结论，都算广义的贪心贪心是最符合自然智慧的思想，一般分析门槛不高理解基本的排序、有序结构，有基本的逻辑思维就能理解但是贪心的题目，千题千面，极难把握难度在于证明局部最优可以得到全局最优。不过可以使用对数...

Posted by Marlin on September 6, 2025

宽度优先遍历及其扩展

BFS

宽度优先遍历及其扩展宽度优先遍历基本内容 bfs 的特点是逐层扩散,从源头点到目标点扩散了几层,最短格就是多少 bfs 可以使用的特征是任意两个节点之间的相互距离相同（无向图） bfs 开始时,可以是单个源头、也可以是多个源头 bfs 频繁使用队列,形式可以是单点弹出或者整层弹出 bfs 进行时,进入队列的节点需要标记状态,防止同一个节点重复进出队列 bfs 进行时,可能会包含剪枝策略...

Posted by Marlin on August 27, 2025

为什么你总是连不上自习室的 Wi-Fi？

——一次真实踩坑实录与自救指南

写在前面的一些名词 DHCP（Dynamic Host Configuration Protocol）：动态主机配置协议，是一种局域网协议，用于动态分配 IP 地址。 DHCP 租约：动态主机配置协议租约，是指 IP 地址租用期限，通常为 30 分钟到 24 小时，过期后 IP 地址自动释放。 SSID（Service Set Identifiers）：无线局域网的名称，通常...

Posted by Marlin on August 24, 2025

最小生成树

MST(Minimum Spanning Tree)

最小生成树概念生成树：n 个点、n-1 条边，连通且无环。最小生成树 MST：边权总和最小的生成树。最小瓶颈树: 所有生成树中最大边权最小的树。最小瓶颈树一定是 MST。 Kruskal（边排序 + 并查集）复杂度排序：$O(m log m)$ 并查集：$O(m α(n)) + O(n)$ 总：$O(m log m) + O(n)$。 ...

Posted by Marlin on August 22, 2025

拓扑排序拓展

拓扑排序的扩展技巧重要技巧:利用拓扑排序的过程,上游节点逐渐推送消息;给下游节点的技巧注意: 这个技巧已经是树型 dp 的内容了,不过即便不会动态规划,本节题也能做。题目 1 最大食物链计数上游节点向下游节点推送消息，下游节点收到消息后计数，最后统计下游节点的计数之和。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21...

Posted by Marlin on August 22, 2025

并查集-下

并查集-下并查集的小扩展可以定制信息:并查集目前有多少个集合,以及给每个集合打上标签信息题目 1 移除最多的同行或同列石头 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 struct DSU {...

Posted by Marlin on August 18, 2025

并查集-上

并查集-上 1. 并查集是什么并查集（Disjoint Set Union，简称 DSU）是一种树型数据结构，专门用来高效地维护「元素分组」与「合并集合」两类操作： find(u)：查询元素 u 所在集合的代表元（根）。 merge(u, v)：把 u 与 v 所在集合合并成一个。并查集的核心思想只有一句话：用一棵树表示一个集合，树根就是集合的代表元，所有节...

Posted by Marlin on August 18, 2025

N皇后问题-位运算

N 皇后问题-位运算 N 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。国际象棋中皇后可以攻击同行、同列以及同对角线的棋子。因此，N 皇后问题要求找到一种布局，使得任意两个皇后都不能处于同一行、同一列或同一对角线上。冲突条件详解在解决 N 皇后问题时，我们需要判断当前位置是否与已经放置的皇后发生冲突。冲突主要分为三种情况： ...

Posted by Marlin on August 16, 2025

Marlin's Blog