Xiaruize's Blog - Welcome to xiaruize's Blog!

Simplifying the Farm

Simplifying the Farm

Created2022-12-31|Updated2022-12-31|NFLS20221231|并查集•组合计数•图论

[USACO11DEC]Simplifying the Farm G By xiaruize 题面求一张竞赛图中最小生成树的方案数思路 Kruskal求最小生成树，记录每个长度的边被选择几次重新跑Kruskal,对于长度一样的边，dfs检查有多少选法，使结果仍然是最小生成树，乘法原理求结果例如，在这张图中，对于长度为1的边，本来选定2条，所以只有一种方案对于长度为2的边，本来选定1条，dfs检查其它长度为2的边，均可以，答案 ×3\times 3×3 Code

abc280-f

Created2022-12-03|Updated2022-12-04|AtcoderAtcoder Beginner ContestABC 280F Pay or Receive|Atcoder•Atcoder Beginner Contest•Graph•Tree

ABC280-F-Pay or Receive By xiaruize 很容易可以想到先用并查集处理联通块，下文中将默认讨论对于每个联通块内的处理分情况讨论情况1 如图，当存在一个环，使得围着这个环一圈的路径的 disdisdis 值 ≠0\neq 0=0 ，那么，容易发现，这个联通块上的所有的两点距离一定为 infinfinf 情况二对于这种情况，只需要选择一个’根节点’，并记录每个节点到它的距离，显然这个距离唯一(否则这个图满足情况一) 因为图满足这个性质: 一条边正反两次经过的代价为0 所以，L⇒RL \Rarr RL⇒R 的距离 === LLL 到 rootrootroot 的距离 +++ rootrootroot 到 RRR 的距离而上述的距离用 dfsdfsdfs 在 O(n)O(n)O(n) 的时间下求出 Code

abc_279d

Created2022-11-30|Updated2022-12-03|AtcoderAtcoder Beginner ContestABC 279D Freefall|Atcoder•Atcoder Beginner Contest•三分

三分-abc279d By xiaruize 前置知识三分俗话说:二分不行就三分那么，三分是什么？如果你不会二分,请点击链接跳转二分需要一个序列满足单调性，那么，如果是一个单峰函数，如何求极值呢？设 f(x)f(x)f(x) 在 x=ax=ax=a 时取到 maxmaxmax 为 bbb 取 l,rl,rl,r 表示当前的两端，l<a,r>al<a,r>al<a,r>a 取区间 [l,r][l,r][l,r] 的三等分点 lmid,rmidlmid,rmidlmid,rmid 令l′=f(lmid),r′=f(rmid)l'=f(lmid),r'=f(rmid)l′=f(lmid),r′=f(rmid) 若 l′<r′l'<r'l′<r′, lmid<almid < almid<a 若 l′>r′l'>r'l′>r′, rmid>armid > armid>a 对应的收缩区间 abc279_d 显 ...

exgcd-crt

Created2022-11-19|Updated2022-11-20|CSP|exgcd•crt

exgcd - crt gcd 最大公约数(Hreatest Common Divisor) 欧几里得算法 gcd⁡(a,b)=gcd⁡(b,amod b)\gcd(a,b)=\gcd(b,a\mod b) gcd(a,b)=gcd(b,amodb) 可以通过反证法证明 123456int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);} exgcd 用于接形如 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b) 的方程 ax+by=gcd⁡(a,b)设{ax1+by1=gcd⁡(a,b)bx2+(amod b)y2=gcd⁡(b,amod b)∵gcd⁡(a,b)=gcd⁡(b,amod b)∴ax1+by1=bx2+(amod b)y2∴x1=y2,y1=x2−⌊ab⌋y2ax+by=\gcd(a,b)\\ 设 \begin{cases} ax_1+by_1=\gcd(a,b)\\ b ...

菱形求和

Created2022-11-19|Updated2022-11-30|CSP|前缀和•切比雪夫距离

菱形求和 Method 1 考虑每次中心由 (x,y)⇒(x,y+1)(x,y) \rArr (x,y+1)(x,y)⇒(x,y+1) 的变化情况如图1-1中所示所以可以考虑用前缀和维护斜向的格子，O(1)O(1)O(1) 的进行转移 (x,y)⇒(x+1,y)(x,y) \rArr (x+1,y)(x,y)⇒(x+1,y) 同理 Method 2 前置知识切比雪夫距离考虑点 (x,y)(x,y)(x,y)，将所有的点 (x,y)⇒(x+y,x−y)(x,y)\rArr (x+y,x-y)(x,y)⇒(x+y,x−y) 表示此时，原来两点 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2)(x1,y1),(x2,y2) 之间的曼哈顿距离 ∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|∣x1−x2∣+∣y1−y2∣ 转化为 max⁡(∣x1−x2∣,∣y1−y2∣)\max(|x_1-x_2|,|y_1-y_2|)max(∣x1−x2∣,∣y1−y2∣) 思路然后就是板子 ...

CSP2022游记

Created2022-11-09|Updated2022-11-19|游记CSP|游记•CSP

CSP2022游记 By xiaruize 前一天打了10多个板子。。。 (感觉最后只用到了线段树 CSP-J 不得不说，环境比南航的机房要好很多，至少室温在人体可以接受的范围内 T1 脑子没了，这种题直接快速幂了。。。差点就写炸了，幸好拍一下。。。大样例好水 T2 仍然没有脑子，可以二分的题非要 O(1)O(1)O(1) , 考完发现求根公式 −b±Δ−2\frac{-b \pm \sqrt{\Delta}}{-2}−2−b±Δ 每判整数。。。但是，因为某种众所周知的原因，我 AC\text{\color{green}{AC}}AC 了 T3 打了40分，我是蒟蒻qwq T4 dpdpdp 板子题 CSP-S 上午的文件不删差评 T1 T1T1T1 就不会qwq 上厕所想的思路，感觉没啥问题，乱写过了大样例，就摆烂了民间数据官方数据 35 80 T2 T2T2T2 线段树/ST板子题民间数据官方数据 luogu CE 80 INFoj 100 80 T3 & T4 民间数据官方 ...

Loading the Database