平行四边形不等式 2D1D 定义1（平行四边形不等式） 若二元实函数 f(x,y)f(x, y)f(x,y) 满足 ∀l1⩽l2⩽r1⩽r2\forall l_1\leqslant l_2\leqslant r_1\leqslant r_2∀l1​⩽l2​⩽r1​⩽r2​，有 f(l1,r1)+f(l2,r2)⩽f(l1,r2)+f(l2,r1)f(l_1,r_1) + f(l_2,r_2)

几何相关算法 向量命名空间 用pt命令空间内的Point类，实现基本的向量加减乘除运算，大小比较<以及相等==判断，内积dot和外积cross，向量长度length，向量夹角angle，向量旋转rotate，以及一些求交点，判断是否正规相交，判断是否点在线段上，计算点到直线、线段距离的函数。 #include <cmath> #include <string> #includ

线段树操作 线段树二分询问 UVA - 11525 - Permutation，SPOJ - NKMOU - IOI05 Mountains，UVA - 12419 - Heap Manager 本质就是利用线段树是二叉树的性质，如果某个区间信息具有单调关系，那么就可以通过判断左右儿子节点中该信息的大小，判断进入哪个儿子节点。线段树的二分询问一般是要求整个区间上最左或最右侧的某个解，通过维护前

简介 总所周知，模拟退火十分玄学，用于求解某些方案数极大（无穷）的问题上，有些NP问题在小范围上，可以使用模拟退火求最优解（TSP问题）。 实现 如果新的状态解更优，则更新答案，否则以一定概率接受新状态。 状态转移 假如现在要求状态的最小值。 定义：TTT 为当前温度，E1E_1E1​ 为新状态，E0E_0E0​ 为原状态，则发生状态转移的概率为： P(E1−E0)={1E1<E0

字符串 Trie树 UVA - 1401 - Remember the Word - Trie+DP组合，UVA - 11732 - “strcmp()” Anyone? - Trie #define reset(A) memset(A, 0, sizeof(A)) const int maxnode = ...; const int maxc = ...; struct Trie {

AtCoder Beginner Contest 213 E - Stronger Takahashi 题意 给出一个迷宫: .代表可以走的道路，#代表墙，你可以花费一点力气打破任意一个 2×22\times 22×2 区域中的所有的墙 请问从迷宫的左上角走到右下角，最少要花费多少力气？ 思路 这道题相比F题要水多了，但我并没看出来 这题可以相当于建图跑最短路，但由于图上的边权只有0和1，所

AtCoder Beginner Contest 212 E - Safety Journey 题意 给出一个含有 N(N⩽5000)N(N\leqslant 5000)N(N⩽5000) 个顶点的完全图，编号从1到N，从中删去 M(M⩽5000)M(M\leqslant 5000)M(M⩽5000) 条边，要求每次从1号顶点出发，经过 K(K⩽5000)K(K\leqslant 5000)K

AtCoder Beginner Contest 215 E - Chain Contestant 题意 给出一个由 101010 种大写字母 A∼JA\sim JA∼J 组成的字符串 SSS，长度为 NNN，求 SSS 有多少个下标序列满足下列条件： 令下标序列所对应的 SSS 的子序列为 TTT，满足同一种字母在 TTT 中都是连续出现的，如：AAABBCCC 满足条件，但 AABBACC

AtCoder Beginner Contest 214 D - Sum of Maximum Weights 题意 给出一颗 NNN 个顶点的树，每条边都具有边权值，定义与顶点有关的二元函数 f(u,v)f(u, v)f(u,v) 为 顶点 uuu 到顶点 vvv 的最短路径上的边权的最大值。 求 ∑i=1N−1∑j=i+1Nf(i,j)\sum_{i=1}^{N-1}\sum_{j=i+1

AtCoder Regular Contest 125 B - Squares 题意 给出一个 NNN，求有多少对 (x,y)(x,y)(x,y) 满足如下条件： 1⩽x,y⩽N1\leqslant x, y\leqslant N1⩽x,y⩽N。 x2−yx^2-yx2−y 是一个平方数。（规定 000 也是平方数） 答案对 998244353998244353998244353