Thy's Blog

AC Library [AC Library](atcoder/ac-library: AtCoder Library) 是 AtCoder 官方推出的已经完全封装的缺省源代码，为了减少参赛者在像线段树、平衡树等数据结构或者取模方面浪费过多的时间，允行直接进行调用。 首先先前往 Releases · atcoder/ac-library 下载最新版的文件。解压后里面的 atcoder 文件夹即为整个库，复制后直接丢进本地编译器的库文件中，差不多类似 mingw64/lib/gcc/.../include/c++ 的文件夹中。 使用方法 头文件引用：#include <atcoder/all> 名称标签声明：using namespace atcoder modint 位于 <atcoder/modint> 当中，使用时需要先选择一个模数。 如果模数  mod \bmodmod 为 998244353998244353998244353 或 100000000710000000071000000007​，那么有现成的类可用，使用定义：typedef atcder: ...

好久没有写题解了，刷到了一道非常组合的题目。 Statement 给定整数 NNN （N≤500N \le 500N≤500）和不固定模数 MMM，求出 NNN 个点连出无向图的个数，满足顶点 111 到 NNN 的最短距离严格大于顶点 111 到其他节点的最短距离。 Solution 模数不一定为质数，因此在得到模数之后再预处理组合数组。 首先固定节点 111 和节点 NNN，NNN 毫无疑问是唯一距离 111 最远的一个点，因此考虑 distdistdist 从小到大进行转移。注意力惊人的话注意到边权为 111，因此可以将整幅图进行分层，然后就可以定义出 dpi,jdp_{i, j}dpi,j​ 表示固定了前 iii 个点，最后一层有 jjj 个点的方案总数。 显然每一个点只会在一层出现，答案即为 distN,1dist_{N, 1}distN,1​。 考虑如何转移，首先遍历二维数组肯定是 N2N^2N2 级别的。时间复杂度允许我们多一个 NNN 用来枚举上一层有几个点，即 dpi,j←dpi−j,kdp_{i, j} \gets dp_{i - j, k}dpi,j​←dpi−j ...

圆方树 定义 圆方树是一种常见的将无向图转化为树上操作的方法。顾名思义，圆方树上有两类点：圆点，即无向图原始的点；方点，每个极大点双连通分量中的一个点，与该连通分量中的所有圆点都有连边。 边双连通分量的定义如下： 对于一个无向图中的 极大 点双连通的子图，我们称这个子图为一个 点双连通分量。 了解了点双连通分量之后，圆方树就有了很多完美的性质： 有树的性质，树上的每两个点之间有且只有一条边。 原无向图中的所有点都断开来了，同一个连通分量中的圆点连向同一个方点，因此圆方树上的每条边连接着一个圆点和一个方点。 方点个数为连通分量数，圆点编号为初始编号，方点编号均大于 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) ...