欧拉函数 对于正整数 nnn，欧拉函数 φ(n)\varphi(n)φ(n) 代表小于 nnn 的数中，所有与 nnn 互质的数的个数。一般认为 φ(1)=1\varphi(1) = 1φ(1)=1。 性质1 对于素数 ppp，1∼(p−1)1\sim (p-1)1∼(p−1) 都与其互质，所以 φ(p)=p−1\varphi(p)=p-1φ(p)=p−1。 性质2 对于互质的 m,nm,nm,n ...

倍增 给定一棵包含 n 个节点的有根无向树，节点编号互不相同，但不一定是 1∼n。 有 m 个询问，每个询问给出了一对节点的编号 x 和 y 询问 x 与 y 的祖孙关系。 输入格式 输入第一行包括一个整数 表示节点个数； 接下来 n 行每行一对整数 a 和 b，表示 a 和 b 之间有一条无向边。如果 b 是 −1，那么 a 就是树的根； 第 n+2 行是一个整数 m 表示询问个数； 接下来 ...

简介 原理 利用三角不等式的可以用图论的方式求解一个不等式组，设 δ(s,x)\delta(s,x)δ(s,x) 为 s→xs \to xs→x 的最短路长度，那么： δ(s,x)≤δ(s,y)+w(y,x)\delta(s,x)\le\delta(s,y)+w(y,x) δ(s,x)≤δ(s,y)+w(y,x) 对于下面的不等式组，可以构造一个图来求最短路找到一个可行解。 {x1≤x2+C1x2 ...

SPFA 负环模板 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你判断图中是否存在负权回路。 建立一个虚拟原点，到所有点的距离都是 0，因此需要在初始化时把所有点都加入队列中，并且不用初始化距离。 由于 SPFA 算法只会把找到路径更小的节点加入到队列中，所以根据抽屉原理只要遍历一个节点的路径大于等于所有节点的数量，那么这条路径一定存在环，并且由于是 S ...

单源最短路 道路与航线 农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。 他想把牛奶送到 T 个城镇，编号为 1∼T。 这些城镇之间通过 R 条道路 (编号为 1 到 R) 和 P 条航线 (编号为 1 到 P) 连接。 每条道路 i 或者航线 i 连接城镇 Ai 到 Bi，花费为 Ci。 对于道路，花费 Ci 为正数；然而航线的花费很神奇，花费 Ci 可能是负数。 道路是双向的，可以从 ...

简介 线段树是用于维护一个区间内具有结合律数据的高效数据结构，单次操作复杂度为 O(log⁡n)O(\log n)O(logn)，但常数较大。 将一个区间不断以 mid=⌊l+r2⌋,[l,mid],[mid+1,r]mid=\lfloor \cfrac{l+r}{2}\rfloor,[l,mid],[mid+1,r]mid=⌊2l+r​⌋,[l,mid],[mid+1,r] 为区间分为两个子树， ...

简介 在 DP 数组中多加一维用来存储状态，进行状态转移的时候也与记录的状态相关。 股票买卖 IV 给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。 原题链接。 状态表示 f(i,j,s) ...

简介 如标题，本文主要记录中学物理中的一些不那么重要但是又确实会用到的边角料知识。有些需要微积分，有些不需要。 测电阻实验的电流表内外接误差分析 设待测电阻为 RRR，电流表电压表内阻为 RA,RVR_A,R_VRA​,RV​ 并且 RA≪R≪RVR_A\ll R\ll R_VRA​≪R≪RV​，下面分析为什么将 RRR 与 RARV\sqrt{R_AR_V}RA​RV​​ 比较。 内接法 对于内 ...

机器分配 总公司拥有 M 台 相同 的高效设备，准备分给下属的 N 个分公司。 各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。 问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。 分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 M。 链接：AcWing 1013。 本题考查多重背包问题与求方案数，代码如下： 1234567891011 ...

背包问题求具体方案 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。 链接：AcWing 12。 当判断当前物品 i 是否取时，判断下列是否成立即可： j \ge ...