ZuesHans's little bag

交互模板 C++ 代码: 1234567891011121314151617181920#include <cstdio>#include <iostream>int main() { for (int l = 1, r = 1000000000, mid = (l + r) >> 1, res; l <= r; mid = (l + r) >> 1) { std::cout << mid << std::endl; std::cin >> res; if (res == 0) { return 0; } else if (res == -1) { l = mid + 1; } else if (res == 1) { r = mid - 1; } else { puts("OvO, I AK IOI"...

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__": ...

补题所得，按照知识板块分，可能加上其他地方找到的题 代码实现 [乘法逆元] (https://oi-wiki.org/math/number-theory/inverse/) 快速幂法求逆元 12345678910111213inline ll qpow(ll a, ll b, ll mod = MOD) { ll res = 1; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res;}ll inv(ll a, ll mod) { return qpow(a, mod - 2, mod);} 乘法原理（独立事件同时发生） 加法原理（互斥事件） A+B problem 核心模型: 题目给出一群概率如何打表？如何转化题目条件 题目条件转化 这道题我认为最难的是读懂同时满足的三条条件 最终所有...

基于数据范围打表预处理 筛法枚举 F. Easy Demon Problem 核心模型:调和级数枚举预处理 思维误区 (Bug):首先是对于题目负因数case没写上。其次是复杂度。这道题错解是n√nlogn，注意到数据范围会变成1e8，加上map常数大会tle。第一步优化换了unorded_set （O(1)查询最坏on）题目卡哈希冲突。 修正逻辑 (Patch):看到多次查询&&因子||倍数||最大公约数，在数据范围允许的条件下可以对值域内所有数有的性质进行打表。 关键逻辑：双重循环，但是内层循环是按倍数增长，这一块的复杂度实际上是nlogn的 关键代码: 1 Codeforces 1154G - Minimum Possible LCM 核心模型:枚举gcd 思维误区 (Bug):记录第一直觉为什么错了 (如: 以为是DP其实是贪心 / 读错题) 修正逻辑 (Patch):下次看到什么特征，要修正为正确思路 关键代码: 1// 只贴最核心的 3-5 行逻辑或 Check 函数，不要贴 main 时空复杂度优化 BFS E. Produc...

构造算法 这个文章主要针对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));（乘法原理） 单调栈就是用来维护这种最近区间的 关键代码: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727...

[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 >&...

动态规划入门 我该怎么看出这是一道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...

数学 数论 C. Fadi and LCM 今天，Osama给了Fadi一个整数 X，Fadi想知道 max(a,b)的最小值，使得 LCM(a,b)等于 X。 a和 b都应该是正整数。 LCM(a,b)是能被 a和 b整除的最小正整数。例如， LCM(6,8)=24, LCM(4,12)=12, LCM(2,3)=6。 -解题思路 - 根据题意有X=a*b 除以 gcd（a，b） - 为了让ab更小我们贪心的从根号X开始找 - 贪心数学推论->正整数 XXX，至少有一对互质因子。(他和1)->任何一个数字都可以通过质数相乘得到->LCM的取法是：对于每一个质数，取两人中指数“最高”的那个。 - 切分lcm定理:对于任何一个质因子（比如一堆2，或者一堆3），它们必须作为‘一坨’整体，要么全给 a，要么全给 b，绝对不能切开。 AC代码 123456789101112131415161718192021222324252627void solve(){ int n; cin >> n; vi prob; ...