无标题
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576struct Edge { int to; double w;};bool check_shortest(int n, vector<vector<Edge>> &g) { vector<double> dis(n + 1, 0); vector<int> cnt(n + 1, 0); vector<int> inq(n + 1, 0); queue<int> q; // 判整个图有没有负环：所有点入队 for (int i = 1; i <= n; i++) { q.push(i); inq[i] ...
ZU_基础算法
交互模板 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"...
无标题
A174605 数学证明 序列定义 由 Mathematica 代码可知： a(n)=∑k=0n(k−s2(k))a(n) = \sum_{k=0}^{n} \bigl(k - s_2(k)\bigr) a(n)=k=0∑n(k−s2(k)) 其中 s2(k)s_2(k)s2(k) 是 kkk 的二进制表示中 1 的个数（popcount）。 Legendre 公式：ν2(n!)=n−s2(n)\nu_2(n!) = n - s_2(n)ν2(n!)=n−s2(n) 这是核心引理。 证明： 设 nnn 的二进制表示为 n=∑j=0Lbj⋅2jn = \sum_{j=0}^{L} b_j \cdot 2^jn=∑j=0Lbj⋅2j，其中 bj∈0,1b_j \in {0,1}bj∈0,1。 由 Legendre 公式，n!n!n! 中素因子 2 的幂次为： ν2(n!)=∑i=1∞⌊n2i⌋\nu_2(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{2^i} \right\rfloor ν2(n!)=i=1∑...
KH_博弈论
博弈操作 入门:简单的公平博弈下dfs搜索 核心原理：如果无论怎么转移，到达的所有状态都是必胜态，或者当前根本无法转移（到达终点），当前状态就是必败态。 左右脑互博 题目:两脑轮流操作，左脑先手，右脑后手。游戏一开始给出了包含 n 个正整数的多重集合(即可以包含重复元素)。每次操作时，脑子必须从集合中删除一个数，并且必须满足删除的这个数大于删除这个数后集合中剩余元素的异或和。若当前集合中只有一个元素，则可以直接删去。无法操作的脑子失败。 思路:题目给了20的数据范围直接搜索就好，在目前这一步我要尽可能地胜利。这只是单纯的01胜利判断 关键代码: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354void solve(){ int n; cin >> n; vi nums(n); int fk = 0; rep(i, 0, n - 1) { ...
kh_数据结构
由于数据结构板子重复太多，所以建议在基础算法里面找，这里是学习的笔记，记录各种情况，算法不完全。更多题目与变体见wp_数据结构 带权并查集
KH_线性基
线性基 线性基模板 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172struct LinearBasis { ll d[64]; ll p[64]; // 用于重建后的基，方便求第 k 小 int cnt; // 线性基中元素的个数 bool has_zero; // 是否可以异或出 0 LinearBasis() { fill(d, d + 64, 0); fill(p, p + 64, 0); cnt = 0; has_zero = false; } // 核心插入操作 bool insert(ll x) { for (int i = 62; i >= 0; i--) { ...
KH_实现合集
实现二进制拼凑某个数字 用代码表达就是从高位到低位扫描： 123456ll R = 0;for(int d = 29; d >= 0; d--){ if(n & (1ll << d)){ // 如果第d位是1 R = R * ten[d] + rli[d]; }}
sp_奇思妙想小题目
这里记录着我对题目的奇思妙想。因为我找不到oj，但是我又觉得这种题目很典，所以就搞了一个专门记录的帖子。不保证代码和分析全对，正确性由gemini3 pro支持… 1 题目描述 给出长度为n的数组ai（均为正整数），给出m，选择子序列使得子序列里面的乘积==n 解法解答：使用拆因子dp做法->在已经有的因子里面选择（这里一个实现难点是不能重复，而愚蠢的zues一开始没实现这个），跑背包dp 跑过随机数据代码： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455void solve(){ int n; cin >> n; int m; cin >> m; // m = 67; map<int, int> mp; for (int i = 0; i < n; i++) { int d; ...
KH_期望DP与概率论
对于期望 DP，我们一般采用逆序来定义状态，即考虑从当前状态到达终点的期望代价。 根据期望的线性性质计算出数学期望表达式 注意点 E[X^2] \neq (E[X])^2$$ -> 正确的代入姿势：展开全平方公式 收集邮票 核心模型:期望dp 思维误区 (Bug):展开完全平方式，x->f(x) x^2->g(x)注意一一映射关系 理解递推公式: 当前状态的期望 = ∑[转移到下一个状态的概率×(下一个状态的期望+本次转移的代价)]\sum [ \text{转移到下一个状态的概率} \times (\text{下一个状态的期望} + \text{本次转移的代价}) ]∑[转移到下一个状态的概率×(下一个状态的期望+本次转移的代价)] 一维初始方程：$$E(i) = P \cdot (E(i+1) + 1) + (1-P) \cdot (E(i) + 1)$$ g(x)=P⋅(g(x+1)+2f(x+1)+1)⏟抽到新票的贡献+(1−P)⋅(g(x)+2f(x)+1)⏟抽到旧票的贡献g(x) = P \cdot \underbrace{(...
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__": ...
wp_spţ牛客寒假营典题
补题所得，按照知识板块分，可能加上其他地方找到的题 代码实现 [乘法逆元] (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 核心模型: 题目给出一群概率如何打表？如何转化题目条件 题目条件转化 这道题我认为最难的是读懂同时满足的三条条件 最终所有...
wp_优化
gcd相关 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){ ...