ZuesHans's little bag

基于数据范围打表预处理 筛法枚举 F. Easy Demon Problem 核心模型:调和级数枚举预处理 思维误区 (Bug):首先是对于题目负因数case没写上。其次是复杂度。这道题错解是n√nlogn，注意到数据范围会变成1e8，加上map常数大会tle。第一步优化换了unorded_set （O(1)查询最坏on）题目卡哈希冲突。 修正逻辑 (Patch):看到多次查询&&因子||倍数||最大公约数，在数据范围允许的条件下可以对值域内所有数有的性质进行打表。 关键逻辑：双重循环，但是内层循环是按倍数增长，这一块的复杂度实际上是nlogn的 关键代码: 1 nlogn找因子 123456789vector<vi> divisors(2e5+2);void precompute_divisors() { for (int i = 1; i <= 2e5; ++i) { // i 作为约数 for (int j = i; j <= 2e5; j += i) { // j 是 i...

字符串 字典树 检索字符串 维护异或极值 维护异或和 在处理异或（XOR）问题时，如果题目的核心逻辑能转化为**“在某个集合中，为当前数字 xxx 寻找一个匹配对象 yyy，使得 x⊕yx \oplus yx⊕y 的值最大（或最小）”，那么01字典树（0-1 Trie）**几乎就是标准答案。 双生魔咒 核心模型:一个维护前缀字符串，要做匹配/拆贡献的算法->字典树 思维误区 (Bug):没想到可以将前缀长度*数量的贡献拆分为字典树上每一个位置节点的贡献//想写非常难以维护的搜索或者魔改但其实思维绕了远路//看不懂字典树在做什么 修正逻辑 (Patch):拆贡献思维， 关键代码: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677struct Trie{ int tre[MAXN][70]; int cn...

构造算法 这个文章主要针对cf div2 cd题难度的做题感想 题目类型 去看题目要求的输出： 如果要求你输出构造的具体条目 有输出要求（字典序之类的）：那这个构造一定有一个或者一群比较优的算法，在这些算法里面一定能按某种贪心来找到正确的构造 没有输出要求：一般贪心之类的 如果要求你输出最大/最小和…一般不需要直接构造答案。 此时关注数据范围，如果要求你多次输出（或者求最优，可能需要每一种构造方案都比较一下）大概率是O1或者Ologn算法 O1常用前缀和/后缀和/推理数学性质构造式子 排列数的组合是阶乘级别的

P7913 [CSP-S 2021] 廊桥分配 通用优化：前缀和优化输出答案 优先队列模拟 优先队列模拟飞机进入时贪心分配廊道 前缀和优化快速查询 离散化思想 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677struct tim{ int l, r;};void solve(){ int n, m1, m2; cin >> n >> m1 >> m2; vector<tim> gn(m1); vector<tim> gw(m2); rep(i, 0, m1 - 1) cin >> gn[i].l >> gn[i].r; rep(i, 0, m2 - 1) cin >>...

数据结构 并查集 家谱 核心模型:题目要求给出一个父亲的名字，以及他的儿子们。接下来进行若干次查询，查询一个人的祖宗 思维误区 (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（高度）。永远把更小（或更矮）的那棵树，接到更大（或更高）的那...

括号序列 通过性质或者数学构造优化 通过元素代价优化 ImbalancedArray->根据乘法原理算出每个项的贡献->维护一个区间的最大值/最小值 核心模型:推式子模拟计算 思维误区 (Bug): 修正逻辑 (Patch) 要求区间最大值和最小值的差。进行简单的数学划分就能划出来->sum={min}+{max}. 对于每个数来说，计算他能影响到的区间，也就是他可以给总结果的贡献 根据乘法原理可以算出一个数字他可以贡献的价值为nums[i]，他贡献的次数是他作为最大值/最小值出现在某个区间的组合种类数->ans +=(ll) (nums[i] x (i - le[i]+1) X (ri[i] - i+1));（乘法原理） 单调栈就是用来维护这种最近区间的 关键代码: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697...

[toc] 差分与前缀和 差分 + 前缀和原理 用途：区间修改后求点值或最小值。 常见坑：差分数组需初始化，注意边界。 1234567891011121314151617181920212223242526struct niubi { int l, r, gap;};void solve() { int n, p; cin >> n >> p; vector<int> c(n + 1); for (int i = 1; i <= n; i++) cin >> c[i]; vector<int> hsh(5e6 + 1); for (int i = 1; i <= n; i++) hsh[i] = c[i] - c[i-1]; vector<niubi> nums(p + 1); for (int i = 1; i <= p; i++) cin >> nums[i].l >&...

图论与搜索 DFS 深度优先搜索 用途：枚举、路径搜索、连通性。 常见坑：注意回溯还原（如标记数组清零），加剪枝防超时。 F. Parabola Independence 寻找最常路 核心模型:寻找最长路，数学几何性质 修正逻辑 (Patch):把图分为上下两部分，按照规则建立DAG，通过dfs（好久没写好生疏）找到上下对于这个点而言最长路径，夹一下出结果 难点：数学几何性质 关键代码: 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788struct line{ int a, b, c;};bool canwalk(line a, line b){ int chaa = a.a - b.a; int chab = a.b - b.b; i...

动态规划入门 我该怎么看出这是一道DP 求最大/小值求方案数量求子序列 贪心做不了(有反例) 依赖前面的值，无后效性 怎么写DP 状态是谁？状态有哪些？状态必须包含所有能够影响下一阶段决策的信息 怎么转移？dp[i]是从哪里转移过来的？怎么转移代价最小/收益最大/能计算全部路径？ 初始状态 DP数组怎么写 一般求什么什么就是DP数组 要不要开二维？就问自己:“如果有两个人同时走到第 iii 步，但他们之前的经历不同，这种不同会限制他们接下来的选择吗？” 能不能压缩？用滚动数组来代替二维，我们只考虑会影响结果的值。只记我们需要记的，过期的扔掉。 DP原理 数字三角形 用途：从顶到底或底到顶，求最大路径和。 常见坑：从底到顶递推可省去边界处理。 123456789101112void solve() { int n; cin >> n; int sjx[100][100]; for (int i = 0; i < n; i++) for (int j = 0; j <= i; j...

数学 gcd构造性质 矩阵 核心模型:左右互质性质：相邻自然数必然互质。余数非零性质：跨越边界的质数选择 思维误区 (Bug):上下互质性质：质数步长 + 辗转相除法。元素唯一性质：带余除法的唯一性。数学表达： 在 n 较小（如 2500 以内）时，大于 n 的第一个质数 PPP 与 n 的距离非常近，最大差值不超过 34。 修正逻辑 (Patch): 关键代码: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071const int N = 1e7 + 10; // 10^7 级别int primes[N], cnt; // primes存质数，cnt存质数个数bool st[N]; // st[i]为true表示i是合数(被筛掉了)，false表示是质数void get_primes(int n){ for ...

贪心 如上P2887 [USACO07NOV] Sunscreen就是典型的贪心，重点是如何去通过我们固定左端点的大胆尝试去实现 反悔贪心 P2949 [USACO09OPEN] Work Scheduling G (全局贪心) 我一开始的错误思路 人人都能想得到去走时间，然后将最紧急的任务先做了然后再紧急的任务里面贪心 最大的问题是:你的贪心是占用时间的，是有后效性的，万一后面有价值更高的任务他就不是期望值了 DP？时间跨度巨大：Di≤109D_i \le 10^9Di​≤109。任务数量（N）较大：N≤105N \le 10^5N≤105。离散化时间之后依然n方 正确思路以及为什么: 以后你在做题时，如果满足以下特征，请立刻想到反悔贪心： 选择带有顺序性（或者可以排序）。 当前的选择会影响后续的资源（比如占用了时间、金钱）。 我们在乎的是“数量”或者“总价值”。 如果发生冲突，我们可以通过“撤销”之前的某个劣质选择，来接纳当前的优质选择，且这种交换一定是不亏的（甚至更赚） AC代码 12345678910111213141516171819202...

基础算法 二分搜索 用途：答案单调时逼近最优解。 常见坑： 最小值模板：if(check) r=mid else l=mid+1。 最大值模板：if(check) l=mid else r=mid-1。 注意边界（left 初始化为最大单元素）。 货运难题 1234567891011121314151617181920212223242526272829int n, k;bool check(int pans, const vector<int> &nums) { int hsh = 0, cnt = 0; for (int i = 0; i < n; i++) { if (hsh + nums[i] > pans) { cnt++; hsh = nums[i]; } else hsh += nums[i]; } return cnt <= k-1;}voi...