Marlin的博客 | Marlin's Blog

并查集-下

并查集-下并查集的小扩展可以定制信息:并查集目前有多少个集合,以及给每个集合打上标签信息题目 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

Git使用与代理

为什么我的Git总是用不了？

本文借助 Roo Code Agent 自动排查并修正了我的 Git 配置，最终由它汇总整理成文。 Git 使用与代理在使用 Git 时，特别是在某些网络环境下，我们可能需要配置代理才能正常访问远程仓库（如 GitHub）。本文将介绍如何正确配置 Git 代理以解决连接问题。通常这种情况可以通过使用 GitHub Desktop 软件来解决，但是，如果使用命令行，则需要手动配...

Posted by Marlin on August 14, 2025

常见经典递归总结

排列、组合、子集枚举

常见经典递归总结子集枚举题目 1 返回字符串的全部字序列时间复杂度：$O(n*2^n)$(子集枚举+遍历) 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 bool st[20]; set<string> set_str; void dfs(int x, stri...

Posted by Marlin on August 14, 2025

根据数据量猜解法的技巧

天字第一号重要技巧

根据数据量猜解法的技巧一个基本事实：C/C++运行时间1s，可以运行常数数量级的程序1e8次左右。所以可以根据这个事实，来猜测自己算法是否正确。问题规模和可用算法 n 上限安全复杂度典型算法 / 思路备注 ≤ 11 O(n!) 全排列、暴力状态...

Posted by Marlin on August 13, 2025

对数器打表找规律的技巧

对数器打表找规律的技巧使用场景对数器打表找规律的使用场景：输入参数是简单类型，返回值也是简单类型。步骤可以用最暴力的实现求入参不大情况下的答案，往往只需要最基本的递归能力打印入参不大情况下的答案，观察规律把规律变成代码，就是最优解了例子题目1 用袋子买苹果问题使用规格8和规格6的袋子买苹果问题。输入n个苹果，苹果数量必须要装满袋子。问苹果数量能否...

Posted by Marlin on August 7, 2025

最大公约数、同余原理

最大公约数、同余原理最大公约数定义两个正整数 $a$ 和 $b$ 的最大公约数（GCD，Greatest Common Divisor）是指能够同时被 $a$ 和 $b$ 整除的最大的正整数。求解 1. 辗转相除法辗转相除法（Euclidean algorithm）是一种求最大公约数的算法。时间复杂度为 $O((log a)^3)$。设 $a$ 和 $b$ 为正整...

Posted by Marlin on August 7, 2025

重要排序算法总结

重要排序算法总结一、排序算法的稳定性定义：排序算法的稳定性是指：对于原始序列中两个相等的元素，在排序后它们的相对顺序不发生改变。 ✅ 稳定：相等元素的相对位置在排序前后保持一致。 ❌ 不稳定：相等元素的相对位置可能被颠倒。稳定性的重要性：对基础类型（如 int、double）无意义：因为值相同就无法区分，顺序无关紧要。对非基础类型（如对象、结构体）有...

Posted by Marlin on August 6, 2025

基数排序

基数排序基于比较的排序只需要定义好两个对象之间怎么比较即可，对象的数据特征并不关心，很通用。不基于比较的排序和比较无关的排序，对于对象的数据特征有要求，并不通用。计数排序，非常简单，但是数值范围比较大了就不行了。基数排序的实现细节，非常优雅的一个实现。关键点：前缀数量分区的技巧、数字提取某一位的技巧。时间复杂度 $0(n)$，额外空间复杂度 $0(m)$，需要辅助空间做...

Posted by Marlin on August 5, 2025

Marlin's Blog