Thy's Blog

圆方树 定义 圆方树是一种常见的将无向图转化为树上操作的方法。顾名思义，圆方树上有两类点：圆点，即无向图原始的点；方点，每个极大点双连通分量中的一个点，与该连通分量中的所有圆点都有连边。 边双连通分量的定义如下： 对于一个无向图中的 极大 点双连通的子图，我们称这个子图为一个 点双连通分量。 了解了点双连通分量之后，圆方树就有了很多完美的性质： 有树的性质，树上的每两个点之间有且只有一条边。 原无向图中的所有点都断开来了，同一个连通分量中的圆点连向同一个方点，因此圆方树上的每条边连接着一个圆点和一个方点。 方点个数为连通分量数，圆点编号为初始编号，方点编号均大于 nnn，总点数小于 2n2n2n。 原图上两点之间互相到达必须经过的点为圆方树上两点路径上的圆点。 过程 由于要找出所有点双连通分量，因此直接套板子即可。 1234567891011121314151617181920212223242526void tarjan(int ver){ dfn[ver] = low[ver] = ++ timestamp; stk[++ stk_top] = ve ...

人生中的第二次 NOIP 结束了，我的 OI 生涯也就此结束了。始于 2023.08.012023.08.012023.08.01，终于 2024.11.302024.11.302024.11.30，从初升高的那个暑假到现在一共十五个月，我的生活被 OI 所占据着，包括寒暑假在一起一共有近十个月在停课搞竞赛，如今就要离开了确实有不舍，但也抱有一份淡然，毕竟已经拼尽全力了一次。 2023年8月1日，第一次来到信息竞赛机房，和我一同上课的人的确只有个位数。第一天刷了很多题，毕竟是完全从零开始，都是些入门语法红题，完全不值为题。 2023年8月2日，今天第一次听说了洛谷这个网站，也是立即注册上了，还写了好几份代码上去，如今来看码风还是非常稚嫩的。 2023年8月中旬，和机房的同学们逐渐熟络起来了，也逐渐模起鱼来了（学 OI 必经之路），直接在机房电脑装了 PCL，和同学们开局域网联机打 MC，最多有五排。现在想起来以前的机房电脑真的什么监控软件都没有，硬盘还原也没有。 2023年8月20日，

Pre 怎么都说 T1 好想但难调啊，简单贪心 + 小模拟评蓝还是太高了，这里就给出一种好写又好调的并查集做法。 Solution 根据题意可知，tk,i=1(k∈{1,2},1≤i≤n)t_{k, i} = 1(k \in \{ 1, 2\}, 1 \le i \le n)tk,i​=1(k∈{1,2},1≤i≤n) 的连续的 iii 所代表的 sk,is_{k, i}sk,i​ 之间可以任意互换，换句话说，字符串 tkt_ktk​ 将 sks_ksk​ 分割成了若干个连通块，属于同一个连通块中的不同字符可以互换，但应当保持 {0,1}\{ 0, 1\}{0,1} 的个数不变。然后一个贪心的思路呼之欲出了： 从左往右遍历到第 iii 个字符时，如果 s1,is_{1, i}s1,i​ 和 s2,is_{2, i}s2,i​ 所处的连通块中存在个数大于 000 的字符 0/10 / 10/1 时，就将匹配数加一，同时将该字符在连通块中的计数减少一；否则匹配数不变化，连通块中字符数量不为 000 的计数减少一。 贪心比较显然，毕竟每个下标对于答案产生的贡献只有 000 或 111 两 ...

最近考试经常考数学，但是我还没有整理过全部的板子，c不了，顺便考前熟悉一下。 质数 / 素数 O(n)O(\sqrt n)O(n​) 判断素数 1234567bool check(int x){ if (x < 2) return false; for (int i = 2; i <= x / i; i ++) if (x % i == 0) return false; return true;} O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn) 埃拉托尼斯筛法 123456789101112bool vis[N];int primes[N], cnt;void Eratosthenes(int N){ for (int i = 2; i <= N; i ++) { if (!vis[i]) primes[++ cnt] = i; else for (int j = i << 1; j <= N; j += ...

Statement 简单题，但是题解貌似没有 dp 做法。 给定一段长度为 nnn 的 010101 字符串，允许至多反转其中一段区间，求满足 010101 相间要求的最大长度。 Solution 很典的状态机，不难想到一共有三种状态： 还没有进行反转 正在进行反转 已经反转完成 我们用 fi,0/1/2f_{i, 0/1/2}fi,0/1/2​ 分别表示第 iii 个数处于以上三种状态时候的最大长度，不难思考得出三者之间的状态转移如下： fi−1,0→fi,0fi−1,1,fi−1,0→fi,1fi−1,1,fi−1,2→fi,2f_{i - 1, 0} \to f_{i, 0}\\ f_{i - 1, 1}, f_{i - 1, 0} \to f_{i, 1}\\ f_{i - 1, 1}, f_{i - 1, 2} \to f_{i, 2} fi−1,0​→fi,0​fi−1,1​,fi−1,0​→fi,1​fi−1,1​,fi−1,2​→fi,2​ 初始状态当然有 f1,0=f1,1=1,f1,2=−∞f_{1, 0} = f_{1, 1} = 1, f_{1, 2} = ...

题目来源 题单：思维 - Virtual Judge problemPdfAll 来源： Dashboard - 2024 China Collegiate Programming Contest (CCPC) Harbin Onsite (The 3rd Universal Cup. Stage 14: Harbin) - Codeforces Dashboard - The 2024 ICPC Kunming Invitational Contest - Codeforces Dashboard - The 2024 ICPC Asia EC Regionals Online Contest (II) - Codeforces Dashboard - The 2024 CCPC Online Contest - Codeforces Dashboard - The 8th Hebei Collegiate Programming Contest - Codeforces Problem A 简单贪心题，难度全在模拟上。 首先选择之后可以充电的电池，并且先充电 ...

今天写分块的时候模板忘光了，故写以记之。 Code Init 1234567891011void Init(){ sz = sqrt(n), block = n / sz + (n % sz != 0); for (int i = 1; i <= block; i ++) st[i] = (i - 1) * sz + 1, ed[i] = i * sz; ed[block] = n; for (int i = 1; i <= block; i ++) for (int j = st[i]; j <= ed[i]; j ++) belong[j] = i;} 其中块长视题目情况而改变，一般为 n\sqrt nn​。 Modify / Query 123456789101112131415void/int Function(int x, int y){ int bx = belong[x], by = belong[y]; // pushdown(bx), ...

Pre 题目链接。 这才是属于斜率优化的模板题，转移方程简单，公式转化也简单。 Statement 有 NNN 个石头，编号为 1,2,…,N1,2,\dots,N1,2,…,N，第 iii 个高为 hih_ihi​。保证 hhh 严格单调递增。 有一只青蛙在第一个石头上，它可以跳到石头编号为 i+1,i+2,…,Ni + 1, i + 2, \dots, Ni+1,i+2,…,N。当他跳到编号 jjj 石头时的花费是 (hi−hj)2+C(h_i - h_j) ^ 2 + C(hi​−hj​)2+C。求跳到编号为 NNN 石头的最小花费。 Solution Transform 首先转移方程可以直接秒掉，定义 dpidp_idpi​ 表示落到第 iii 个石头上的最小代价，有： dpi=min⁡j<idpj+(hi−hj)2+Cdp_i = \min_{j < i} dp_j + (h_i - h_j) ^ 2 + C dpi​=j<imin​dpj​+(hi​−hj​)2+C 然后参数分离，有： dpi=min⁡j<i(dpj+hi2−2hihj+hj2+C) ...

Debug 1234inline void debug() { cerr << '\n'; }template<typename Type, typename... Other>inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a) Read In 1234567891011template<typename Type>inline void read(Type &res){ res = 0; int ch = getchar(), flag = 0; while (!isdigit(ch)) ...

Statement 给定可能含前导零的三个位数为 nnn 的整数 A,B,CA,B,CA,B,C，求出排列 ppp 的个数，使得三个整数的每一位经过排列映射后得到的 A′,B′,C′A',B',C'A′,B′,C′ 可以使 A′+B′=C′A' + B' = C'A′+B′=C′ 成立，答案对 109+710^9 + 7109+7 取模。 下文中定义位数从右向左，例如 A1A_1A1​ 表示 AAA 的个位上的数，AnA_nAn​​ 为最高位的数。 Solution 一道并不难的排列组合计数题，复杂就在处理不同数位之间的进位问题。 不进位的情况 先考虑不进位的情况，每一位之间都不会互相影响，同时由于 A′,B′,C′A',B',C'A′,B′,C′ 不能含有前导零，我们定义 zerozerozero 表示有 000 的列数。 答案简洁明了，第一列放非 000 列，后面随便放即可。 ans=(n−zero)×(n−1)!ans = (n - zero) \times (n - 1)! ans=(n− ...