rsdbkhusky / rsdbkhusky.github.io

This is my personal blog

Hello my friend! 👋 I am Rsdbkhusky

Here is rsdbkhusky's github account. I am an OIer from sjzezsyxx. Working on IT Industry. Usually use C++ and C#. Sometimes use Html, Javascripts, Css and Python. You can know more about me on my blog.

rsdbkhusky.github.io's Issues

基环树 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/12/%E5%9F%BA%E7%8E%AF%E6%A0%91/

P1453 城市环路1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991

Luogu P4544 [USACO10NOV]Buying Feed G | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/Buying%20Feed%20G/

P4544 USACO10NOV Buying Feed G放在前面：本方法时间复杂度为 $O(nW)$ ，单调队列优化 DP。本题还有一道弱化版，欢迎大佬切完这题顺便把那题也切了，并欢迎大家来该题题解看我的另一篇博客。 一. 变量声明： $W$：代替题目中的 $K$，到家时应带的饲料吨数，相当于背包中的背包最大承重（weight）。 $n$：代替题目中的 $N$，商店数量，相当于背包问题中的物

割点 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E5%89%B2%E7%82%B9/

P3388 【模板】割点（割顶）123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include#includeusing na

卢卡斯定理 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E5%8D%A2%E5%8D%A1%E6%96%AF%E5%AE%9A%E7%90%86/

P3807 【模板】卢卡斯定理/Lucas 定理$\operatorname{C}^m_n\operatorname{mod}p=\operatorname{C}^{m/p}{n/p}\times \operatorname{C}^{m\operatorname{mod}p}{n \operatorname{mod}p}\operatorname{mod}p$ 123456789101112

Manacher | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/Manacher/

P3805 【模板】manacher 算法1234567891011121314151617181920212223242526272829303132333435363738394041#include#includeusing namespace std;#define re registerconst int MAXn = 1e7

线段树 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E7%BA%BF%E6%AE%B5%E6%A0%91/

P3372 【模板】线段树 11. 无懒标记不取模1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192

整体二分解静态区间第k小 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/10/%E6%95%B4%E4%BD%93%E4%BA%8C%E5%88%86%E8%A7%A3%E9%9D%99%E6%80%81%E5%8C%BA%E9%97%B4%E7%AC%ACk%E5%B0%8F/

P3834 【模板】可持久化线段树 2（主席树） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576

Luogu CF679A Bear and Prime 100 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/Bear%20and%20Prime%20100/

CF679A Bear and Prime 100一. 审题：1. 前提条件： 无 2. 询问 & 输入： 询问：（最多 $20$ 次） 输出一个数 $x$，代表询问 $x$ 是否是被猜数的约数。 输入： 读入一个字符 yes 或 no 代表这个数是否是被猜数的约数。 3. 输出： 该数是否是素数。 二. 思路 我们知道质数的因数有且只有 $1$ 和自己，也就是 $1$ 和一

Luogo P2616 [USACO10JAN]Buying Feed, II S | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/Buying%20Feed,%20II%20S/

P2616 USACO10 JANBuying Feed, II S放在前面：为对应“普及-”的难度，本文讲解的是 $O(nW^2)$ 复杂度的朴素 DP，如想挑战更高难度请进 Here，并欢迎大家来该题题解看我的另一篇博客上的 $O(nW)$ 解法。 一. 变量声明： $W$：代替题目中的 $K$，到家时应带的饲料吨数，相当于背包中的背包最大承重（weight）。 $n$：代替题目中的 $N$

二分 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/10/%E4%BA%8C%E5%88%86/

重点： $mid$ 取 $l+r$ 还是 $l+r+1$。 “ $=$ “ 的话应该算那种情况。 代码：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<cstd

UVA 1025 城市里的间谍 A Spy in the Metro | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E5%9F%8E%E5%B8%82%E9%87%8C%E7%9A%84%E9%97%B4%E8%B0%8D/

UVA1025 城市里的间谍 A Spy in the Metro（本题有多倍经验哦） 一. 思路1. 思考解法 时间 是个好的 DP 阶段，时间轴上靠后发生的不会影响前面的事，反映到本题上就是 Maria 之后怎么走不会影响现在的最优解，符合无后效性。 Maria 既可以乘向东的地铁，又可以乘向西的地铁，还可以呆着不动。那么一种情况可以由多种情况而来，多种情况也可以发展成一种情况，各种情况互相

Luogu P1654 OSU! | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/OSU!/

P1654 OSU!放在前面：这是一道期望dp大水题，属于那种看题解一看就会，自己写一写就废的那种。 一. 思路（不想看我前面唠叨就直接看代码吧） 1. 确定状态转移方程$d_i$：$i$ 次操作后得的分数。则 $E(d_i)$：$i$ 次操作后期望的的分数。 第 $i$ 轮后，得分发生了怎样的变化了呢？我们先只看从最近一次失败后算起的成功的一段，$i$ 轮前得分是 $x^3$，如果低 $i$ 次

Cdq解三维偏序 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/10/Cdq%E8%A7%A3%E4%B8%89%E7%BB%B4%E5%81%8F%E5%BA%8F/

P3810 【模板】三维偏序（陌上花开）123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949

二叉搜索树 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/

P5076 【深基16.例7】普通二叉树（简化版）1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192

对顶栈 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/23/%E5%AF%B9%E9%A1%B6%E6%A0%88/

P2201 数列编辑器1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#includeusing namespace std;#defi

二叉搜索树 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/

P5076 【深基16.例7】普通二叉树（简化版）1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192

记一只小傻蜂 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E8%AE%B0%E4%B8%80%E5%8F%AA%E5%B0%8F%E5%82%BB%E8%9C%82/

今天，2021 年 6 月 28 日。 笃行楼 5 楼 第三机房，不足 40 cm 的狭窄门缝中，钻进了一只蜂。 这只蜂比较肥大，巨身修尾，青项金翅。 进来就盘旋在天花板上面，半天赶不下来。 傻死了，她要么一直撞灯管，要么一直盘旋着飞，给她掰了些饼干也不吃。 稍晚些的时候，杰从机房的外面进来了，但是杰哥要怎么把她从高度 4m 的高高天花板中再赶出去啊！ 天啊，她怎么一直在飞，真的不累吗。 放张照

树的直径 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E6%A0%91%E7%9A%84%E7%9B%B4%E5%BE%84/

U81904 【模板】树的直径1. 两次Dfs注意：该方法无法解决负权树。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include#include#include<algo

Ac自动机 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/Ac%E8%87%AA%E5%8A%A8%E6%9C%BA/

P3808 【模板】AC自动机（简单版）P3796 【模板】AC自动机（加强版）1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848

逆康托展开 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/25/%E9%80%86%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include#define re register#defin

Luogu CF727C Guess the Array | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/Guess%20the%20Array/

CF727C Guess the Array注：本文含交互题 endl 与 fflush 不同种类的配合使用效果的 测试（见 “四”） 一. 审题：1. 前提条件： 一个数 $n$ 代表数组中数的个数。 2. 询问 & 输入： 询问： 输出两个数 $x$，$y$ 。代表询问 $a_x$ 和 $a_y$ 的和。 格式：? x y 输入： 读入一个数代表这两个数的和。 3.

边双连通分量 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E8%BE%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F/

T103489 【模板】边双连通分量12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include#includeusing name

三分 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/10/%E4%B8%89%E5%88%86/

P3382 【模板】三分法123456789101112131415161718192021222324252627282930313233#include#define re registerconst int MAXn = 13 + 1;const double EPS = 1e-6;int n;double l, r, a[MAXn + 10];double f(

实用小高精 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/18/%E5%AE%9E%E7%94%A8%E5%B0%8F%E9%AB%98%E7%B2%BE/

不实用的高精 推荐一个实用小高精： 1234567891011121314151617181920212223struct BigInt { const static long long base = 1e13; long long s[2]; friend BigInt operator + (BigInt a, const BigInt b) { a.s[0] += b.

树链剖分 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86/

P3384 【模板】轻重链剖分12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697

树状数组 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/

P3374 【模板】树状数组 1P3368 【模板】树状数组 21234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include#define re register#define int long longconst int

快读 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E5%BF%AB%E8%AF%BB/

上面的只能读非负数，下面的能读负数1234template inline void read(T &a) { register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');w

树的重心 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E6%A0%91%E7%9A%84%E9%87%8D%E5%BF%83/

1234567891011121314151617181920212223242526int head[MAXn + 10], cntnex, nex[MAXm * 2 + 10], to[MAXm * 2 + 10];void Insert(int u, int v) { nex[++cntnex] = head[u]; head[u] = cntnex; to[cntnex] = v

锁机 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E9%94%81%E6%9C%BA/

作为一名 $OIer$，我们时时刻刻都有被 $jc$ 的风险。这事我们需要一款简单的锁机程序来锁死保护我们的电脑： 12345678910#include<windows.h> #include<winable.h> #include<time.h>int main() { FreeConsole(); while(1) { if

Luogu P3601 签到题 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E7%AD%BE%E5%88%B0%E9%A2%98/

P3601 签到题一. 思路$1 \le l \le r \le 10^{12}$，$r-l \le 10^6$。很显然，传统的用欧拉函数是积性函数这条性质的从 $1$ 扫到区间右端的方法肯定不行。虽然传统的方法不行。但欧拉函数还有一条有用的公式：$\varphi(n)=n \times \prod\limits_{i=1}^{n}\dfrac{p_i-1}{p_i}$ 。也就是说，我们只要知道

康托展开 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/

P5367 【模板】康托展开1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #define re register#define int long longco

强连通分量 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F/

B3609 [图论与代数结构 701] 强连通分量123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include#include#i

最近公共祖先(lca) | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88(lca)/

P3379 【模板】最近公共祖先（LCA）1. 倍增123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include&

线段树优化建图 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/13/%E7%BA%BF%E6%AE%B5%E6%A0%91%E4%BC%98%E5%8C%96%E5%BB%BA%E5%9B%BE/

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210

邻接表 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E9%82%BB%E6%8E%A5%E8%A1%A8/

12345678910#includeconst int MAXn = 1e4;const int MAXm = 1e4 * 2;//无向图MAXM应开边数二倍int head[MAXn + 10], cntnex, nex[MAXm * 2 + 10], to[MAXm * 2 + 10];void Insert(int u, int v) { nex[++

Treap | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/Treap/

P3369 【模板】普通平衡树12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697

割边 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E5%89%B2%E8%BE%B9/

T103481 【模板】割边12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include#includeusing namespace std;#define re r

点双连通分量 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E7%82%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F/

T103492 【模板】点双连通分量1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include#include<vector&gt

还没完工吧~~~

RT

错排问题 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/10/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98/

P1595 信封问题1234567891011121314#include#define int long long#define re registerconst int MAXn = 20;int n, a[MAXn + 10];signed main() { a[1] = 0; a[2] = 1; scanf("%lld", &amp

点分治 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E7%82%B9%E5%88%86%E6%B2%BB/

P3806 【模板】点分治1123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979

对拍 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E5%AF%B9%E6%8B%8D/

在 OI 赛制 中，代码只能交一次，这是比赛与 OJ 最大的不同。我们如果不能保证代码是正确的，就需要对拍： code1/2.cpp：暴力及正解代码。 random.cpp：随机数据生成器。 match.cpp：对拍程序： 一. 对拍程序$linux$ 下（重点）： 123456789101112131415161718192021222324#include

OI中的数论 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/OI%E4%B8%AD%E7%9A%84%E6%95%B0%E8%AE%BA/

一. 质数1. 概念 概念：$\varphi(n)$：$1\sim n$ 中与 $n$ 互质的数的个数。 如果当 $a, b$ 互质时, 有 $f(a b)=f(a) * f(b)$, 那么称函数 $f$ 为积性函数。 2. 性质 区间质数个数：前 $n$ 个：$\dfrac{n}{\ln n}$。 欧拉函数 $\forall n&gt;1,1 \sim n$ 中与 $n$ 互质的数的和

最长上升子序列(lis) | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/10/%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97(lis)/

本解法时间复杂度$O(nlogn)$，还有一种 DP 的 $O(n^2)$ 的求法，感兴趣的可以上网了解一下 123456789101112131415161718192021222324#include#includeusing namespace std;#define re registerconst int MAXn = 1e5

Luogu P3868 [TJOI2009]猜数字 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E7%8C%9C%E6%95%B0%E5%AD%97/

P3868 [TJOI2009]猜数字一. 思路首先拿道题看到条件给出两组数，其中一组互素，让猜一个数字。自然而然往 crt 上想。但为什么是 crt 呢？ $\forall i \in [1,k]$，有 $b_i \mid (n - a_i)$，这句话可以化为一组同余方程，再移项可得标准的 crt 格式： ~~~~~~~~~~~~~~\begin{cases} n - a_1 \equiv 0

Splay | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/Splay/

P3369 【模板】普通平衡树P3391 【模板】文艺平衡树函数汇总： $check(id)$ $pushup(id)$ $rotate(id)$ $splay(id, goal)$ $find(v)$ $EvaPre(v)$ $EvaNex(v)$ $Insert(v)$ $Delete(v)$ $ValtoRank(v)$ $RanktoVal(rank)$ 文艺平衡树

Luogu P3225 [HNOI2012]矿场搭建 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/18/%E7%9F%BF%E5%9C%BA%E6%90%AD%E5%BB%BA/

一. 思路0. 前置知识：割点，v-dcc（再说一遍，无向图有的是双连通分量，没有强连通分量一说！）。​ 这里推荐几道模板题，学习 Tarjan 建议把他们都 A 了： dcc 割边：Luogu Std。 dcc 割点：Luogu Std。 e-dcc：Luogu Std。 v-dcc：Luogu Std。 scc：Luogu Std。 scc 缩点：Luogu。 （没有找到双连

字符串哈希解最小循环节 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/08/10/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%93%88%E5%B8%8C%E8%A7%A3%E6%9C%80%E5%B0%8F%E5%BE%AA%E7%8E%AF%E8%8A%82/

P3538 POI2012\OKR-A Horrible Poem1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#includeusing namespace st

Luogu P3833 [SHOI2012]魔法树 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/%E9%AD%94%E6%B3%95%E6%A0%91/

P3833 [SHOI2012]魔法树放在前面的前面：本文有树剖图解放在前面：一道树剖板子题，关于树剖的教程网上数不胜数，我就只 概述 一下，就不造轮子了，具体细节请见 OI WIKI。 一. 过程概述0. 基础：邻接表，线段树。1. 第一次 dfs：求出该有根树（如果题目没明确根就任选一个）所有节点的父节点，深度，（以他为根的）子树的大小， 重儿子。 2. 第二次 dfs：求出该有根树所有节点的

Luogu P2432 zxbsmk爱查错 | 燃烧的冰块_husky's blog

https://rsdbkhusky.github.io/2021/07/21/zxbsmk%E7%88%B1%E6%9F%A5%E9%94%99/

P2432 zxbsmk爱查错一. 审题：1.已知&输入： 给出一个长度为 $L$ 的文本串。 给出 $W$ 个单词串。 2.目标&输出： 在文本串中删除尽量少的字母使得文本串只有由词串构成，输出这个最少删除的字母数。 二. 思路1. 思考解法 文本串后面的内容不会影响文本串前半部分的最优解，符合无后效性。 若把文本串右端位置作为状态，文本串右端位置较靠右的状态需要通过文本串右