zaizwk

Hello Huawei开一个专栏记录暑期实习的碎碎念……

单源路径问题全是正边对于全是正边的题目，最短路问题上所有算法都行得通，主要看一个熟练度问题 最短Floyd基于动态规划的思想，从节点A到节点B的距离的最小值，等于所有途径AB之间起连通作用的点的路径的最小值，在小图里面非常好写，时间复杂度 $O(n^3)$ 1234for k in range(1, N + 1): for i in range(1, N + 1): for j in range(1, N + 1): f[i][j] = min(f[i][j], f[i][k] + f[k][j]) Bellman-Ford每一轮都对边进行松弛操作 $dis(v) = min(dis(v), dis(u) + w(u, v))$ ，如果有负环则可以一直松弛下去，如果最后发现最后一轮还在松弛，说明进入了负环，时间复杂度是 $O(mn)$ 12345678910111213141516es = [[] for _ in range(N)]dis = [inf] * Nbellman(n, s): dis[s] = 0 f = False ...

关于异或定义对两个数的二进制位逐位求异或，如果位相同则取 $0$ ，否则取 $1$ 例如 $5\ xor\ 3 = 6$ 基本性质 $0 \ xor\ n = n$ $n \ xor\ n = 0$ $a \ xor\ b \ xor\ b = c$ $a\ xor\ b\ xor\ c = a\ xor (b\ xor\ c)$ 特殊性质 对一个二进制位反复取反，等于它反复地异或 $1$ 对于 $1 - n$ 之间所有的数求异或，结果呈现以下特点 a = [x, 1, x + 1, 0] 对于 $x mod4$ 的结果取对应的位数， 例如 $xor[1..4] = a[0] = 4;xor[1..6] = a[2] = 7$ 异或的差分和前缀和和普通加减法一致，只不过，异或的逆运算，仍然是异或 由上述性质，我们现在可以得到 任何连续区间的异或和 随机数字的连续异或和（使用前缀和） 区间异或，单点查询的异或（使用差分）

数论基础质数筛获得 $N$ 以内的全部素数 12345678910111213141516#inlcude <bits/stdc++.h>using namespace std;const int N = (int)(2e6 + 10);int n, c, primes[N];bool comp[N];int main() { cin >> n; for (int i = 2; i <= n; i++) { if (!comp[i]) primes[c++] = i; for (int j = 0; 1ll * i * primes[j] <= n; j++) { comp[primes[j] * i] = true; if (i % primes[j]) break; } }} 二次筛当 $N$ 比较大，但是 $R - L$ 的区间长度比较小的时候，获得 $L, R$ 之内的素数 123 ...

欧拉函数问题背景求得小于 $N$ 且与 $N$互质的数字的个数 一些比较重要的性质 对于素数 $k$ 的欧拉函数取值是 $k - 1$ 欧拉函数是积性函数 $\varphi(m n) = \varphi(m) \varphi(n)$ 求解公式 \varphi(n) = n\prod_{i = 1}^{n}\frac{p_i - 1}{p_i}其中 $p_1, p_2, \dots p_n$ 是 $n$ 的质因数 代码写法单个数求值取模(参考的是质因数分解的做法)12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int max ...