Ender's blog

Learn English With HDUOJ undirected [adj.] 无向的 weighted [adj.] 加权的 denote [v.] 表示 navy [n.] 海军 tough [adj.] 艰难的、坚固的 fleet [n.] 舰队 encounter [v.] 遭遇 embattle [vt.] 布阵 cannon [n.] 大炮 engagement [n.] 交战、约会 arbitrary [adj.] 武断的 iceberg [n.] 冰山 column [n.] 列、柱子 unpredictable [adj.] 不可预测的 represent [v.] 相当于 battlefield [n.] 战场 respectively [adv.] 各自地 iteratively [adv.] 反复地 symbolize [vt.] 象征

哈希(Hash)算法模板 1234567891011121314151617const ull MOD = 998244353;typedef unsigned long long ull;ull h[MAXN], p[MAXN];inline ull hash(string s) { //求哈希值 static const ull BASE = 131; ull res = 0; int len = s.length(); for(int i = 0; i < len; i++) { p[i] = p[i - 1] * BASE; h[i] = (h[i - 1] * p[i] + ull(s[i])) % MOD; } return h[len - 1];}inline ull sub_hash(int l, int r) { //子串哈希值 return ((h[r] - h[l] * p[r - l + 1]) % MOD + MOD) % MOD;& ...

k条白边最小生成树问题 问题 给定一张图，每条边都有一个权值和颜色，仅为黑色或白色，求一条恰好包含 kkk 条白边的最小生成树。 求解 这个问题与分数规划问题非常类似 给每条白边的权值都增加 CCC ，二分 CCC ，求此时的最小生成树总权值 www ，并求出这个树包含几条白边。 假如包含的白边数 r>kr > kr>k ，则增大 CCC ，否则减小 CCC ，直到 r=kr = kr=k ，则最小生成树的总权值则为 w−k∗Cw - k * Cw−k∗C

分数规划模型学习笔记 问题 给定 nnn 个二元组 (ai,bi)(a_i, b_i)(ai​,bi​) ，从中选出 kkk 个二元组使得 ΣaiΣbi\frac{\Sigma a_i}{\Sigma b_i}Σbi​Σai​​ 尽可能大，求出最小值。 求解 假设 ΣaiΣbi≥x\frac{\Sigma a_i}{\Sigma b_i} \geq x Σbi​Σai​​≥x 则可以将式子变形为 Σai−x⋅Σbi≥0\Sigma a_i - x \cdot \Sigma b_i \geq 0 Σai​−x⋅Σbi​≥0 对 xxx 进行二分，将 ai−x⋅bia_i - x \cdot b_iai​−x⋅bi​ 从大到小排序，选出前 kkk 个 ，判断式子是否成立，如果成立则增加 xxx ，不成立则减小 xxx ，直至求出最优解。

树链剖分学习笔记

线段树优化建图笔记 问题 给定 nnn 个结点， mmm 组边，第 iii 组边从 $ P_i$ 向 LiL_iLi​ 到 RiR_iRi​ 这段点号区间中所有点连一条长度为 ViV_iVi​ 的边，求最短路。 线段树使用 首先线段树每一个区间节点都向这个节点的子区间节点连一条长度为零的边，叶子结点向这个长度为 111 的区间所表示的点连一条长度为零的边。 如果有一组边为从 333 号点向 [4,8][4, 8][4,8] 这段区间连长度为 vvv 的边，则从 333 号点向区间节点 [4,4][4, 4][4,4] 连一条长度为 vvv 的边，再从 333 这个点向区间节点 [5,8][5, 8][5,8] 连一条长度为 vvv 的边，就完成了连边以及建图。 代码模板 在写了在写了

二分图的最大独立集问题 最大独立集和最大团 一个图中包含尽可能多个互相没有边的点组成的集合就称为这个图的最大独立集。 一个图中包含尽可能多个彼此都有边相连的点组成的集合称为这个图的最大团。 在一个图中的最大独立集等于在这个图的补图中的最大团。 与二分图的关系 不幸的是，在一般的图中，求解最大独立集是一个NP完全问题，但是幸运的是，在二分图中，这是一个可以解的问题，在二分图中，最大独立集中的点数等于所有点数减去匹配的数量，假设这个二分图一共有 nnn 个结点，并且形成了 kkk 个匹配，即说明其中至少 kkk 个形成匹配的结点被删掉之后，这个图中剩下的所有点就彼此都没有边相连了，所以最大独立集的数量为 n−kn - kn−k 。 而如果存在一个图，两边所有的节点都有边相连，并且两边有有几条边彼此相连，这显然是一个二分图的补图，如果要求这个图的最大团，即可以将该问题转化为对补图求最大独立集。 而同理，如果一个题目中涉及最大独立集或者最大团，就可以将该问图与二分图联想。

二分图匹配问题 问题 在一个二分图中，每一个点只能匹配一个点，求这个图中最多能存在多少对匹配上的点。 匈牙利算法 dfs(i) 函数为尝试让 i 进行匹配的函数，如果 i 号点可以进行匹配，则答案 ans++ 。 dfs 函数的原理为：首先对与 i 号点有边的点尝试匹配，如果该点已经被匹配，则尝试让该点匹配的点重新匹配，如果匹配成功，修改该点匹配的点为 i 否则尝试下一个点。 算法代码 12345678910111213141516171819202122int n, m;bool dfs(int i) { for(int j = 1; j <= m; j++) { if(match[i][j] && !use[j]) { use[j] = true; if(!result[j] || dfs(result[j])) { result[j] = i; return true; &# ...

Tarjan学习笔记 有向图强连通分量 定义 在有向图中，如果存在极大子图中从任意一点出发均能到达其他所有点，则称这个子图为有向图的强连通分量。 Tarjan求强连通分量 如果将这个有向图dfs成一棵树，当其加入一条边使得有向树中形成环时，这个环上的所有点都属于同一个强连通分量。当且仅当，加入的边从当前节点指向该节点的祖宗节点时，才有可能出现环；而且当存在当前节点指向该节点的祖宗节点时，若有加入一条起点终点深度相同的边，并且从终点可以走到连向祖宗节点的边的点，该祖宗节点也能走到加入的边的起点，图中也能形成新的环。 dfn[i] 用来记录第 i 个点的dfs序， low[i] 表示第 i 个点加边之后可以走到最靠上的点的dfs序。 dfs的起点为图中所有入度为零的点，枚举以当前节点 now 为起点的所有边的终点，如果该终点还没有被dfs过，则先dfs这个点，再用该终点的 low 值更新 low[now] 的值 ，如果该终点已经被dfs过了，该终点有可能是祖宗节点，则用该终点的dfs序更新 low[now] 的值。 如果某个点所连向的其他点没有dfs完成，或者该节点不知道处于哪个确定的强连 ...

2-SAT 问题学习笔记 问题 给定 nnn 个变量与 mmm 个等式，每个变量只能为 falsefalsefalse 或是 truetruetrue ，每个等式都至多有两个变量 xi,xjx_i , x_jxi​,xj​ ，并且等式右边给出这两个变量通过至多一个位运算符运算得到的结果，形如： x1 and x2=falsex2 or x3=truex3 xor x1=falsex2=truex_1\ and\ x_ 2 = false \\ x_2\ or\ x_3 = true \\ x_3\ xor\ x_1 = false \\ x_2 = true x1​ and x2​=falsex2​ or x3​=truex3​ xor x1​=falsex2​=true 判断是否有解 可以将这个问题转化为求强连通分量问题，首先这张图的点为每个 xix_ixi​ 的两种状态，如果根据第 kkk 个等式， 知道 xix_ixi​ 一定能够推出 xjx_jxj​ 的值，例如 x1andx2=falsex_1 and x_2 = falsex1​andx2​=false ，当 x1=tru ...