kh_数据结构
- 由于数据结构板子重复太多，所以建议在基础算法里面找，这里是学习的笔记，记录各种情况，算法不完全。更多题目与变体见wp_数据结构
带权并查集
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 ZuesHans's little bag！
相关推荐
2025-11-10
KH_stl字典
bitset 在状态空间搜索、图的连通性、二维偏序或 01 背包问题中，当状态数 NNN 在 1000~2000 级别，常规 O(N2)O(N^2)O(N2) 或 O(N3)O(N^3)O(N3) 做法会 TLE 时，使用 std::bitset 可以利用 CPU 的位运算指令将常数极大地优化（通常是将时间复杂度除以 64），实现“降维打击”。 声明与初始化 (买灯泡) 注意： 在竞技编程中，bitset 的大小必须是常量，不能用变量代替。 123456789#include <bitset>#define int long longusing namespace std;// 声明一个长度为 1000 的 bitset，默认所有位都是 0 (灭)bitset<1000> bs; // 声明并用整数初始化 (十进制转二进制，5 -> 101，即第 0 和第 2 位为 1)bitset<1000> bs2(5); 单点操作 (针对某一个具体开关) 1234567bs.set(5); // 第 5 位设为 1bs.r...
2025-12-10
wp_数据结构
数据结构 并查集 家谱 核心模型:题目要求给出一个父亲的名字，以及他的儿子们。接下来进行若干次查询，查询一个人的祖宗 思维误区 (Bug):套用dsu模板，但是模板默认有启发式合并 修正逻辑 (Patch):这道题强制要求了父亲与儿子的关系，所以删掉启发式合并，把father放在前面son放在后面（模板默认后面的往前面合并） 关键代码: DSU（并查集）里的启发式合并 在并查集中，启发式合并通常被称为 “按秩合并” (Union by Rank) 或 “按大小合并” (Union by Size)。 它的目的是 防止树退化成链，从而保证查询速度。 没有启发式合并：如果每次都固定把 YYY 接在 XXX 下面，而在极端数据下（比如 1→2,2→3,…,N−1→N1 \to 2, 2 \to 3, \dots, N-1 \to N1→2,2→3,…,N−1→N），并查集会变成一条长长的“链表”。查找一次祖先需要 O(N)O(N)O(N) 的时间。 有启发式合并：我们维护每棵树的 size（节点数）或 rank（高度）。永远把更小（或更矮）的那棵树，接到更大（或更高）的那...
2025-11-13
KH优化算法
莫队 普通莫队做法 P2709 【模板】莫队 / 小B的询问 核心模型: 思维误区 (Bug): 修正逻辑 (Patch): 关键代码: 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182struct qury{ int l, r, id;};void solve(){ int n, m, k; cin >> n >> m >> k; vi nums(n + 1); for (int i = 1; i <= n; i++) { cin >> nums[i]; } vi cnt(k + 3); vector<qury> qry(m); ...
2026-05-29
KH_博弈论
博弈操作 入门:简单的公平博弈下dfs搜索 核心原理：如果无论怎么转移，到达的所有状态都是必胜态，或者当前根本无法转移（到达终点），当前状态就是必败态。 左右脑互博 题目:两脑轮流操作，左脑先手，右脑后手。游戏一开始给出了包含 n 个正整数的多重集合(即可以包含重复元素)。每次操作时，脑子必须从集合中删除一个数，并且必须满足删除的这个数大于删除这个数后集合中剩余元素的异或和。若当前集合中只有一个元素，则可以直接删去。无法操作的脑子失败。 思路:题目给了20的数据范围直接搜索就好，在目前这一步我要尽可能地胜利。这只是单纯的01胜利判断 关键代码: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354void solve(){ int n; cin >> n; vi nums(n); int fk = 0; rep(i, 0, n - 1) { ...
2026-03-07
KH_实现合集
实现二进制拼凑某个数字 用代码表达就是从高位到低位扫描： 123456ll R = 0;for(int d = 29; d >= 0; d--){ if(n & (1ll << d)){ // 如果第d位是1 R = R * ten[d] + rli[d]; }}
2026-02-11
KH_对拍写法
python 的随机数生成器写法 基础常见语法 import random随机库 random.randint(a, b): 生成一个 [a,b][a, b][a,b] 范围内的整数（包含 aaa 和 bbb）。 random.choice(seq): 从列表或字符串中随机选择一个元素。 random.uniform(a, b): 生成一个 [a,b][a, b][a,b] 范围内的浮点数。 示例代码 1234567891011121314import randomdef solve(): n = random.randint(1,1000000) print(n) for i in range (n): c=random.randint(1,10) w=random.randint(1,10) print(c,w)# end=" " 表示打印后不换行，而是加个空格 print()# 最后换个行if __name__ == "__main__": ...
