kzssCCC

摘要： https://www.luogu.com.cn/problem/P5960 对于不等式 \(u-v \ge w\)，连 \(u\rightarrow v\)，权为 \(-w\) 的边，用 \(spfa\) 跑最短路判断负环. //author:kzssCCC #include <bits/stdc 阅读全文

摘要： https://www.luogu.com.cn/problem/P5903 与重链剖分类似，存长儿子以及长度，从叶子跳到根是 \(\mathcal{O}(\sqrt{n})\) 的. 可以 \(\mathcal{O}(1)\) 查询 \(k\) 级祖先，只对长链头维护 \(up\) 和 \(dow 阅读全文

摘要： https://www.luogu.com.cn/problem/P4781 给定 \(n\) 个点 \((x_i,y_i)\) 满足 \(x_i\) 互不相同，经过它们可以确定一个 \(n-1\) 次多项式 \(y=f(x)\)，构造 \(f(x)\). 考虑构造 \(f_i(x)\) 满足图像经 阅读全文

摘要： 切比雪夫距离定义 对于二维平面两点 \((x_1,y_1)\)，\((x_2,y_2)\)，它们的切比雪夫距离为： \[\max(|x_1-x_2|,|y_1-y_2|) \]曼哈顿距离转化成切比雪夫距离 对于平面上点 \((x,y)\)，令 \(u = x+y\)，\(v=x-y\). \[|x_ 阅读全文

摘要： https://qoj.ac/contest/2513/problem/14304/statement/zh_cn 题意 给定一棵树，每个点有点权，任意断边将树分成若干连通分量，让所有连通分量的最大值 \(-\) 最小值之和最大，求这个最大值. \(1\le n \le 10^6\). 思路 考虑 阅读全文

摘要： https://codeforces.com/contest/528/problem/D 题意 给定标准串 \(s\) 和模式串 \(t\)，仅由 \(ACGT\) 四种字符组成. 定义模糊匹配：若 \(s[i-k,\cdots, i+k]\) 存在 \(t_j\)，则 \(s_i\) 与 \(t_ 阅读全文

摘要： https://www.luogu.com.cn/problem/P3803 给定 \(n\) 次多项式 \(A(x)\) 和 \(m\) 次多项式 \(B(x)\)，求乘积 \(C(x)\). 单位根 \(z^n = 1\) 有 \(n\) 个不同的复数根，记为 \(\omega_n\)，相当于在 阅读全文

摘要： https://codeforces.com/problemset/problem/2187/C 题意 给定 \(n\) 个点构成有向图，对于 \(1\le i \lt n\)，有 \(i \rightarrow i+1\) 的边. 另有 \(m\) 条边 \(u \rightarrow v\)，均 阅读全文

摘要： https://codeforces.com/problemset/problem/2194/F1 题意 给定一棵节点数为 \(n\) 的无根树，\(a_i\) 表示节点 \(i\) 的点权. 给定长度为 \(k\) 的序列 \(b\)，将树划分成若干连通分量，每个连通分量的异或和为 \(b\) 中 阅读全文

摘要： https://www.luogu.com.cn/problem/P3379 记 \(first(x)\) 为 \(x\) 在欧拉序中第一次出现的位置，则 \[first(LCA(u,v)) = \min\{first(k)\mid k\in euler[first(u)\cdots first(v 阅读全文