noip2020 模拟赛
记录考试总结 2020.09.05 比赛入口 比赛时一开始把T1做了，用了个错算法，但是我当时不知道。随后想了一会儿做了T2。最后半个小时一对拍就发现T1用了个错的dp方法，于是赶紧写了个60pts暴力交上去。 然而，T2由于把题目理解错了，只计算了 ∑i=1npi\sum_{i=1}^{n}p_i∑i=1npi ，导致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...
2020.09 -> 2020.12
记录： 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,...
BSGS
求解满足 ax≡b(modp)a^x\equiv b\pmod pax≡b(modp) 的最小 xxx （ ppp 是质数） 分块？设分块大小为 ttt 考虑 i∈[0,⌈nt⌉],j∈[1,t]i\in[0,\left\lceil\dfrac{n}{t}\right\rceil],j\in[1,t]i∈[0,⌈tn⌉],j∈[1,t] 则 axa^xax 可以表示成 ait−ja^{it-j}ait−j ait−j≡b(modp)a^{it-j}\equiv b\pmod p ait−j≡b(modp) 转换一下 ait≡baj(modp)a^{it}\equiv ba^j\pmod p ait≡baj(modp) 预处理出所有的 bajba^jbaj 存到一个 map / unordered_map 中，在枚举 i in range[1, n/t] 判断 aita^{it}ait 是否和某个元素 bajba^jbaj 相等，答案即为 it−jit-jit−j 复杂度...
Bézout定理
定理 存在整数 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∑nj=1∑ngcd(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)21n×φ(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−p11)(1−p21)…(1−pk1) 证明：容斥 若 aaa， bbb 互质，则...
拉格朗日插值
oi-wiki 给出 nnn 个点 Pi(xi,yi)P_i(x_i,y_i)Pi(xi,yi)，将过这 nnn 个点的最多 n−1n-1n−1 次（为什么是 n−1n-1n−1 次：因为可以构造出 nnn 个线性方程，只能解出从常数项系数到 n−1n-1n−1 次项的系数）的多项式记为 f(x)f(x)f(x) ，求 f(k)f(k)f(k) 的值。 如图所示，将每一个点在 xxx 轴上的投影 (xi,yi)(x_i,y_i)(xi,yi) 记为 HiH_iHi 。对每一个 iii ，我们选择一个点集 {Pi}∪{Hj∣1≤i≤n,i≠j}\{P_i\}\cup\{H_j|1\le i\le n,i\neq j\}{Pi}∪{Hj∣1≤i≤n,i=j} ，作过这 nnn 个点的至多 n−1n-1n−1 次的线 gi(x)g_i(x)gi(x) 。图中 f(x)f(x)f(x) 用黑线表示，gi(x)g_i(x)gi(x) 用彩色线表示。 这样得到的 gi(x)g_i(x)gi(x) 在各自对应的 xix_ixi 处取得 yiy_iyi...
P2596 [ZJOI2006]书架 总结
link 构造一颗中序遍历是序列的Treap，发现可以很容易地求出序列上第 xxx 位的值，即为 getval(root, x) ，但是不好求一个数 kkk 在序列上的位置。这时我们就可以维护一个值 idx(k)idx(k)idx(k) ，表示值为 kkk 的节点编号，这时只需要设计出一个函数来求节点 uuu 的排名了，而这个函数也很容易实现，对于一个节点 uuu ，每次将它向树根跳，如果它是右儿子，那么就将它父亲的左子树的值以及父亲的大小计入结果。 12345678910int getpos(int id) { int f, cnt = 0; while ((f = p[id].f) != 0) { if (id == p[f].rs) { cnt += p[p[f].ls].siz + 1; } id = f; } return cnt;} 既然要存储一个节点的父亲，那么 pushup...