三维几何及常见例题三维几何必要初始化点线面封装12345678910111213141516171819202122232425262728293031323334353637struct Point3 { ld x, y, z; Point3(ld x_ = 0, ld y_ = 0, ld z_ = 0) : x(x_), y(y_), z(z_) {} Point3 &operator+=(Point3 p) & { return x += p.x, y += p.y, z += p.z, *this; } Point3 &operator-=(Point3 p) & { return x -= p.x, y -= p.y, z -= p.z, *this; } Point3 &operator*=(Point3 p) & { return x *= p.x, y *= p.y, z *= p.z, *this; } Point3 &am ...

串子串与子序列 中文名称 常见英文名称 解释 子串 连续的选择一段字符（可以全选、可以不选）组成的新字符串 子序列 从左到右取出若干个字符（可以不取、可以全取、可以不连续）组成的新字符串 kmp 应用： 在字符串中查找子串； 最小周期：字符串长度-整个字符串的 ； 最小循环节：区别于周期，当字符串长度 时，等于最小周期，否则为 。 以最坏 的时间计算 在 中出现的全部位置。 12345678910111213std::vector<int> get_next(std::string& t) { std::vector<int> next(t.size()); next[0] = -1; for (int i = 0, j = -1; i < (int)t.size();) { if (j == -1 || t[i] == t[j]) { ++i, ++j; next[i] = j; } else ...

动态规划01背包有 件物品和一个容量为 的背包，第 件物品的体积为 ，价值为 ，求解将哪些物品装入背包中使总价值最大。 思路： 当放入一个价值为 的物品后，价值增加了 ，于是我们可以构建一个二维的 数组，装入第 件物品时，背包容量为 能实现的 最大价值，可以得到 转移方程 。 123456for (int i = 1; i <= n; i++) for (int j = 0; j <= W; j++){ dp[i][j] = dp[i - 1][j]; if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); } 我们可以发现，第 个物品的状态是由第 个物品转移过来的，每次的 转移过来后，第 个方程的 已经没用了，于是我们想到可以把二维方程压缩成 一维 的，用以 优化空间复杂度。 123for (int i = 1; i <= n; i++) //当前装第 i 件物品 for (int ...

二维几何库实数类实现（双精度）123456789using Real = int;using Point = complex<Real>; Real cross(const Point &a, const Point &b) { return (conj(a) * b).imag();} Real dot(const Point &a, const Point &b) { return (conj(a) * b).real();} 平面几何必要初始化字符串读入浮点数12345678910111213141516const int Knum = 4;int read(int k = Knum) { string s; cin >> s; int num = 0; int it = s.find('.'); if (it != -1) { // 存在小数点 num = s.size() - it - 1; // 计算小数位数 s.erase(s.begin ...

博弈论巴什博奕 有 个石子，两名玩家轮流行动，按以下规则取石子： 规定：每人每次可以取走 个石子，拿到最后一颗石子的一方获胜。 双方均采用最优策略，询问谁会获胜。 两名玩家轮流报数。 规定：第一个报数的人可以报 ，后报数的人需要比前者所报数大 ，率先报到 的人获胜。 双方均采用最优策略，询问谁会获胜。 （其中 ），后手必胜（后手可以控制每一回合结束时双方恰好取走 个，重复 轮后即胜利）； （其中 ），先手必胜（先手先取走 个，之后控制每一回合结束时双方恰好取走 个，重复 轮后即胜利）。 扩展巴什博弈 有 颗石子，两名玩家轮流行动，按以下规则取石子：。 规定：每人每次可以取走 个石子，如果最后剩余物品的数量小于 个，则不能再取，拿到最后一颗石子的一方获胜。 双方均采用最优策略，询问谁会获胜。 时，后手必胜； （其中 ） 时，后手必胜（这些数量不够再取一次，先手无法逆转局面）； （其中 ） 时，先手必胜； （其中 ） 时，先手必胜（这些数量不够再取一次，后手无法逆转局面）； Nim 博弈 有 堆石子，给出每一堆的石子数量，两 ...

图论常见概念 oriented graph：有向图 bidirectional edges：双向边 平面图：若能将无向图 画在平面上使得任意两条无重合顶点的边不相交，则称 是平面图。 无向正权图上某一点的偏心距：记为 Missing or unrecognized delimiter for \bigecc(u) = \max \big{ dist(u, v) \big} ，即以这个点为源，到其他点的所有最短路的最大值。如下图 点， 即为 。 图的直径：定义为 Missing or unrecognized delimiter for \bigd = \max \big{ ecc(u) \big} ，即最大的偏心距，亦可以简化为图中最远的一对点的距离。 图的中心：定义为 Missing or unrecognized delimiter for \bigarg=\min \big{ ecc(u)\big} ，即偏心距最小的点。如下图，图的中心即为 点。 图的绝对中心：可以定义在边上的图的中心。 图的半径：图的半径不同于圆的半径，其不等于直径的一半（但对于绝对中心定义上的直径 ...

图论常见结论及例题常见结论 要在有向图上求一个最大点集，使得任意两个点 之间至少存在一条路径（可以是从 到 ，也可以反过来，这两种有一个就行），即求解最长路； 要求出连通图上的任意一棵生成树，只需要跑一遍 bfs ； 给出一棵树，要求添加尽可能多的边，使得其是二分图：对树进行二分染色，显然，相同颜色的点之间连边不会破坏二分图的性质，故可添加的最多的边数即为 ； 当一棵树可以被黑白染色时，所有染黑节点的度之和等于所有染白节点的度之和； 在竞赛图中，入度小的点，必定能到达出度小（入度大）的点 See 。 在竞赛图中，将所有点按入度从小到大排序，随后依次遍历，若对于某一点 满足前 个点的入度之和恰好等于 ，那么对于上一次满足这一条件的点 ， 到 点构成一个新的强连通分量 See 。 举例说明，设满足上方条件的点为 ，那么点 到 构成一个强连通分量、点 到 构成一个强连通分量。 选择图中最少数量的边删除，使得图不连通，即求最小割；如果是删除点，那么拆点后求最小割 See。 如果一张图是平面图，那么其边数一定小于等于 See 。 若一张有向完全图存在环，则一定存 ...

基础算法常用函数12345678910111213141516int mypow(int n, int k, int p = MOD) { // 复杂度是 log N int r = 1; for (; k; k >>= 1, n = n * n % p) { if (k & 1) r = r * n % p; } return r;}i64 mysqrt(i64 n) { // 针对 sqrt 无法精确计算 ll 型 i64 ans = sqrt(n); while ((ans + 1) * (ans + 1) <= n) ans++; while (ans * ans > n) ans--; return ans;}int mylcm(int x, int y) { return x / gcd(x, y) * y;} 12345678910111213141516171819202122template<class T> int log2floor(T n) { // ...

多边形相关平面多边形两向量构成的平面四边形有向面积123template<class T> T areaEx(Point<T> p1, Point<T> p2, Point<T> p3) { return cross(b, c, a);} 判断四个点能否组成矩形/正方形可以处理浮点数、共点的情况。返回分为三种情况： 代表构成正方形； 代表构成矩形； 代表其他情况。 1234567891011template<class T> int isSquare(vector<Pt> x) { sort(x.begin(), x.end()); if (equal(dis(x[0], x[1]), dis(x[2], x[3])) && sign(dis(x[0], x[1])) && equal(dis(x[0], x[2]), dis(x[1], x[3])) && sign(dis(x[0], x[2])) && ...