Cauphenuny's Blog

normal mode: Ctrl-a 数字+1 Ctrl-x 数字-1 Ctrl-o：跳转到上一次光标所在位置 0：行首 ^：行首非空字符 $：行末 g_：行末非空字符 gh：选择 %：跳转到匹配括号 []：上一个在行首的} ][：下一个在行首的{ {：上一个代码块末尾 }： 下一个代码块末尾 [[： 文件开头行 ]]： 文件末尾行 c 删除并插入 [verb]i[char]： [char]可为 ()[]{} ，表示范围在 [char] 所在的匹配括号内容 例： memset(a, 0, sizeof(0)); 光标在第 1 个 0 的位置，输入 di(：删除a, 0, sizeof(0)。 insert mode: Ctrl-w：删除单词 Ctrl-u：删除行，保留缩进 Ctrl-t：缩进++ Ctrl-d：缩进– Ctrl-n/p：补全 visual mode: >：缩进++ <：缩进–

CF708C Centroids 题意简述： 给定一棵 nnn 个点的树，你可以删除一条边并增加一条边，形成一棵新树。 问每个点在进行这样的操作后，是否可能成为新树的重心。 1≤n≤4⋅1051 \le n \le 4\cdot 10^51≤n≤4⋅105 发现没有是一个无根树，很难处理。考虑把树的重心 rt 找出来，然后想象把这颗树从 rt 处提起来 于是对于子树内的每个点 v ，大于 ⌊n2⌋\left\lfloor\dfrac{n}{2}\right\rfloor⌊2n​⌋ 的部分只可能出现在 v 的父亲 u 所在联通块上。 即红色区域。那么我们需要把红色区域拆分成两个大小不大于 ⌊n2⌋\left\lfloor\dfrac{n}{2}\right\rfloor⌊2n​⌋ 的部分，分别接到 v 上。 拆分有几个选择，拆掉 u 的父亲所在子树（即上图 1 部分），或者把与 v 同级的子树拆掉，（即上图 2,3,4 ）。 设分出来不大于 ⌊n2⌋\left\lfloor\dfrac{n}{2}\right\rfloor⌊2n​⌋ 的部分的最大大小为...

转载：pyqpyq 的Blog 定义 一棵树中以一个节点为根的子树的大小的最大值最小的节点为树的重心。 性质一 一棵树中以重心为根的节点的子树大小均不超过整棵树的大小的一半。 证明： 考虑反证法。 假设一棵树中以重心为根的节点的子树大小有子树超过整棵树的大小的一半。 则以超过整棵的大小的一半的子树的根换为整棵树的根。 以原根为根的子树大小一定不超过整棵树的一半。 若其它子树的大小最大值不超过整棵树大小的一半，则现在的根的子树大小的最大值不超过整棵树大小的一半。 而以树的重心为根的子树大小的最大值不超过整棵树大小的一半。 则以树的重心为根的子树大小的最大值不是最小的，与定义矛盾。 若其它子树的大小最大值超过整棵树大小的一半，则继续以以超过整棵树的大小的一半的子树的根为整棵树的根。 由于每次换根都在往下走，所以肯定可以换到叶子节点或者在中间出现矛盾。 而到叶子节点时也可如上述过程推出矛盾。 所以必然矛盾，假设不成立。 所以一棵树中以重心为根的节点的子树大小均不超过整棵树的大小的一半。 判定一 一棵树中以一个节点为根的子树的大小的最大值最小的节点为树的重心。 就是定义啊。 ...

记录考试总结 2020.09.05 比赛入口 比赛时一开始把T1做了，用了个错算法，但是我当时不知道。随后想了一会儿做了T2。最后半个小时一对拍就发现T1用了个错的dp方法，于是赶紧写了个60pts暴力交上去。 然而，T2由于把题目理解错了，只计算了 ∑i=1npi\sum_{i=1}^{n}p_i∑i=1n​pi​ ，导致100pts$\to$20pts。 最终得分：80 Solution： 无线网路发射器选址 经典的求最大矩形问题：悬线法。 记 hi,jh_{i, j}hi,j​ 为以 (i,j)(i,j)(i,j) 为起点，向上的最长空线段（即悬线）长度。 li,jl_{i,j}li,j​ 为 (i,j)(i,j)(i,j) 向左最多拓展到的点 ri,jr_{i,j}ri,j​ 为 (i,j)(i,j)(i,j) 向右最多拓展到的点 si,js_{i,j}si,j​ 为悬线最多向左移动到的列编号 ti,jt_{i,j}ti,j​...

记录： 9.1 训练指南–数学基础2.1&2.2 训练指南–数学基础2.3&2.4 训练指南——组合游戏、概率和期望、置换群 9.5~9.6 NOIP2020模拟测试一 | 总结 NOIP2020模拟测试二 | 总结 9.7 训练指南——矩阵、线性方程组、数值方法 9.12~9.13 NOIP2020模拟测试三 NOIP2020模拟测试四 9.14 训练指南——字符串 9.15 训练指南——平衡树 9.19~9.20 NOIP2020模拟测试五 NOIP2020模拟测试六 9.24 分块入门 - hzwer的博客 9.29 fhq Treap学习笔记 - 我的博客 SA-SAM题单 10-02~04 NOIP2020模拟测试九 NOIP2020模拟测试十 NOIP2020模拟测试十一 10-09 tarjan缩点 10-10 排列组合 10-11 NOIP2020模拟测试十二 10-12 换根dp 10-13 拉格朗日插值 10-17~18 NOIP2020模拟测试十三 ...

先看看 oi-wiki 记录一下比较复杂的插入部分。 判断 st[top-1] 与 lca(st[top - 1], u) 的 dfn 值， 连边 st[top], st[top - 1] 并将 top-- （表示在 lca 以下的边都可以连边，弹栈） 记得 dfn[st[top] - 1] 与 dfn[lca] 相等的时候也要连边并弹出栈 弹出完以后，判断一下栈顶与 lca 是否相等，不相等则连边，（如上图红色边），并把 lca 压入栈 然后将 x 压入栈，判断结束 12345678910111213141516171819202122232425262728293031323334void build() { int cnt = m; sort(a + 1, a + cnt + 1, cmp); st[++top] = 1; for (int i = 1, u, v, x; i <= cnt; i++) { u = st[top]; v = a[i]; x = lca(u,...

定理 存在整数 xxx，yyy 使得 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b) 证明： 考虑求 gcd⁡(a,b)\gcd(a,b)gcd(a,b)...

acwing202. 最幸运的数字 P2398 GCD SUM 给定 nnn ，求 ∑i=1n∑j=1ngcd⁡(i,j)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j)i=1∑n​j=1∑n​gcd(i,j) 数据范围：n≤105n\leq10^5n≤105 不需要反演也能做！ 挨个枚举 i,ji,ji,j 复杂度太高，考虑枚举 gcd⁡(i,j)\gcd(i,j)gcd(i,j) 的值。 对于所有 gcd⁡(x,y)=1\gcd(x,y)=1gcd(x,y)=1，有 gcd⁡(xk,yk)=k(xk≤n,yk≤n)\gcd(xk,yk)=k\quad(xk\leq n,yk\le n)gcd(xk,yk)=k(xk≤n,yk≤n) 所以 gcd⁡(i,j)=k\gcd(i,j)=kgcd(i,j)=k 的 i,ji,ji,j 的个数为：2∑i=1⌊n/k⌋φ(i)−12\sum\limits_{i=1}^{\lfloor...

写出 dp\text{dp}dp 方程后，要先判断能不能使用斜优，即是否存在 function(i)∗function(j)function(i)*function(j)function(i)∗function(j) 的项或者 Y(j)−Y(j′)X(j)−X(j′)\frac{Y(j)-Y(j')}{X(j)-X(j')}X(j)−X(j′)Y(j)−Y(j′)​ 的形式。 通过大小于符号或者 bbb 中 dp[i]dp[i]dp[i] 的符号结合题目要求 (min⁡/max⁡)(\min/ \max)(min/max) 判断是上凸包还是下凸包，不要见一个方程就直接盲猜一个下凸。 当 X(j)X(j)X(j) 非严格递增时，在求斜率时可能会出现 X(j1)=X(j2)X(j_1)=X(j_2)X(j1​)=X(j2​)的情况，此时最好是写成这样的形式：return Y(j)>=Y(i)?inf:-inf，而不要直接返回 infinfinf...

∀n>1\forall n>1∀n>1 ，111 ~ nnn中与 nnn 互质的数的和为 12n×φ(n)\dfrac{1}{2}n\times\varphi(n)21​n×φ(n) 证明：gcd(n,x)=gcd(n,n−x)gcd(n,x)=gcd(n,n-x)gcd(n,x)=gcd(n,n−x)，所以与 nnn 互质的数成对出现，平均数为 n/2n/2n/2 。 若 p 为素数， φ(pk)=pk(1−1p)=pk−1(p−1)\varphi(p^k)=p^k(1-\dfrac{1}{p})=p^{k-1}(p-1)φ(pk)=pk(1−p1​)=pk−1(p−1) φ(n)=n(1−1p1)(1−1p2)…(1−1pk)\varphi(n)=n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\ldots(1-\dfrac{1}{p_k})φ(n)=n(1−p1​1​)(1−p2​1​)…(1−pk​1​) 证明：容斥 若 aaa， bbb 互质，则...