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...

记录考试总结 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​ 为悬线最多向右移动到的列编号 则有 ans=max(hi,j×(ti,j−si,j+1))(1≤i≤n,1≤j≤m)ans=max...

记录： 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 互质，则...