P12572 [UOI 2023] An Array and Addition Again 只有数组末尾有一个 局限性太大了，考虑先花 次操作把整个数组填满 。 之后直接往后面 DFS 即可，即减去当前位置的 ，除以 ，就是下一个位置需要达到的数，复杂度是两倍的 ，可以接受。 代码： #include<bits/std

NOIP 二十连测 day4 温度 很显然的是我们可以先把所有的 都对 取模一下，然后排个序，此时的答案就应该是最大值和最小值的平均值（向上取整） 最优解是要考虑有些 多减去了一个 变成负数，这些 肯定是排序后数列的一个后缀，枚举这个后缀，每次计算是 的。 代码： #include<bits/stdc++.h> usi

博客日志 虚拟主机时代 2025-08-06 博客搭建完毕。 2025-08-07 博客正式上线，发布第一篇文章和"站点简介"页面。 2025-08-08 更新SSL证书，用户可以更安全地访问此博客。 2025-08-09 更新账户系统并增添隐私政策，用户可以注册账号。 2025-08-10 更新"友情链接"与"蒸汽平

有一段时间没写总结了，不能再拖了。。。 26 NOIP 二十连测 day1 | 正睿 OI 题目 #3681 | 正睿 OI 根据每个人最多连两条边可以知道，最后的连通块要么是环、要么是链，那就简单了。 但是挂了十分，原因是当一个连通块没有产生贡献时，就不需要再删边了。 代码： C++ #include using n

26 CSP 七连测 day4 | 正睿 OI 题目 #3649 | 正睿 OI 尝试找一些性质，如果区间内 的数量为奇数，考虑将最后一个 移动到最后，其余两两配对，移动到一起；如果区间内 的个数为偶数，那考虑直接两两配对或者将最后一个放到最后，并且在其余的 中找一个跳过。 这个东西用线段树乱搞一下即可。 代码： C+

26 CSP 七连测 day3 | 正睿 OI 题目 #3642 | 正睿 OI 这题用的是 DP，感觉更好想一点。。。 先考虑不是一个环，设 表示当前这个位置是点亮还是熄灭， 到最后时在用概率把链连成环需要的贡献减去即可。这个贡献的计算考虑每次遇到不确定状态的位置时，我们都会新增一条分支，需要减去的贡献也会乘以 ，最

正睿 CSP 七连测 Day2 Oblivion 设 表示仅考虑 到 且 邪恶的方案数。考虑枚举一个左端点 ，表示 到 中的人都是善良的，那方案合法当且仅当 到 $\lfloor \frac{i+j}{2}\rfloor $ 中所有有指向的都为 L， 到 $i $ 中所有有指向的都为 R。同样需要考虑 作为第一个邪恶的

基础知识 LGV 引理仅适用于有向无环图。 定义 为路径 上每条边边权之积。 定义 为从 到 的每条路径 的 之和。 现在有一个起点集合 与终点集合 ，定义矩阵 ： 那么矩阵 的行列式就是每一种互不相交的路径权值和的总和。 如果是路径计数问题的话，可以把边权都设为 。 题目 P6657 【模板】LGV 引理 模板题。

前置芝士 Matrix - Tree 定理，中文名：矩阵树定理。 度数矩阵 对于无向图，度数矩阵 的定义是： 对于有向图，分入度矩阵 和出度矩阵 ，定义如下： 邻接矩阵 对于无向图，邻接矩阵 的定义为： 其中 表示 两点之间所连边数。 对于有向图，邻接矩阵 的定义为： 其中 表示从点 指向 的边数。 拉普拉斯矩阵 说到

P4242 树上的毒瘤 这题太累人了，就算是我这种马蜂紧凑的也爆写了将近 5 KB 的代码。 观察一下题目，先是维护树上颜色段，想到树剖+线段树；再是若干关键点之间两两求贡献，想到虚树+点分治。写点分治时，我们固定一个 LCA，不难发现两条链合并时 LCA 处颜色相等，那贡献就是颜色段和减 。那我们建虚树时就直接把两个

前言 今天是集训最后一天。。。 题目： 排列游戏 我们发现，想要字典序最小，肯定第一个填 是最优的，这样以来后面每个位置的奇偶性都确定了，我们直接按照从小到大放就行。 但是有一个特例，就是当 的时候，第一个放 没有合法解，只能放 。 代码： C++ #include using namespace std; int c

题单： CF1637E Best Pair 考虑不同的 最多只有 种，所以我们直接记录每个 对应的 ，对其排序，然后暴力枚举两个 对应的 ，从大到小看是否满足条件，最多 次不满足条件。 代码： C++ #include using namespace std; typedef long long ll; const i

好文推荐：一些网络流经典建模 - 洛谷专栏 网络流总结 之前初学网络流时并没有在博客上记录，昨天的网络流题也都是用二分图相关算法写的，所以今天先总结一下网络流相关的算法。 前置基础芝士 网络是指一个有向图 ，有两个特殊节点：源点 和汇点 。每条有向边 都有一个权值 ，称为边的容量。若 ，则 。 用 表示边 上的流量，

一些笔记 一些关系 二分图匹配大小 = 最小点覆盖大小 = - 二分图最大独立集。 DAG 最小路径覆盖 = - 拆点图注最大匹配 = 偏序集最长反链（即在 DAG 上选出最大的两两不可到达的点集）。 什么是拆点图？ 对于 DAG 中每一条边 ，我们在新图中连无向边：，则形成了一个二分图。这个二分图即原 DAG 的拆点

一些笔记 差分约束 2-SAT 三元环枚举 最小树形图 定义：有向图的最小生成树。 算法： 朴素算法：朱刘算法（见下面的例题） 最优算法：Tarjan 优化朱刘算法（待学习） P1948 [USACO08JAN] Telephone Lines S 考虑二分答案 ，将边权大于 的边权设为 ，其余设成 ，跑一遍 01-B

前言 昨天通知今天有台风，所以今天上午改成了神秘模拟赛，题目啥的放最后吧。 P5304 [GXOI/GZOI2019] 旅行者 考虑二进制分组，即枚举 个关键点的编号的二进制位，将 、 分成两个集合，用一个超级源点连向一个集合、用一个超级汇点连向另一个集合，跑最短路即可。由于最终的答案的点对一定有一位上是不一样的，所以

前言 T4 暴力居然爆 了，非常诡异，本来感觉拿个 的糖糖分数还是可以的。 T5 依旧想了个非常伪的做法，甚至还没调出来，好在虽然伪但是拿到了多重背包的部分分。 T6 没时间看了。 可是啊 数学瞎搞一通。 C++ #include using namespace std; #define int long long i

CF727C Guess the Array 先问前三个，就可以算出来前三个，后面就更简单了。 代码： C++ #include using namespace std; const int N=1e5+5; int n; int a[N],x,y,z; signed main(){ cin»n; cout>x; c

待办 学习后缀自动机； 完成相关例题。 题单 P3809 【模板】后缀排序 先说一个 的做法，那就是直接排序，重写 cmp，用哈希+二分找到两个串的最长公共前缀，比较下一位即可。 代码： C++ #include using namespace std; using ull=unsigned long long; co

待办： 学习回文树。 AC 自动机与回文树例题若干。 题单： P5357 【模板】AC 自动机 模板，上代码： C++ #include using namespace std; const int N=2e5+5; struct ACAM{ int tr[N][30]; int fail[N],cnt[N],in[N

前言 很久没写串串题字符串题了，并且博客上似乎也没有关于字符串的专题，所以今天把一些基础的模板重新打了一遍，放了上来。 题单 CF1200E Compress Words 字符串哈希题。 维护答案串的前缀哈希，对新加入的串做前缀哈希处理，并暴力枚举答案串后缀与新串前缀的重合长度即可。 代码： C++ #include

什么是人类智慧题？ 为了方便通过关键词搜索到这篇文章，在此解释一下我对人类智慧题的定义：构造（交互、通信）、Ad-hoc、随机。 题单 CF1110E Magic Stones 牛炸了的 Ad-hoc。 首先特判 与 是否相等。 先看一组变化： 尝试差分，得到： 会发现以上操作对于差分数组而言就是交换相邻项，所以直接判

必胜态与必败态 先手必胜 = “存在”一个后继局面是后手必败。 先手必败 = “对于所有”后继局面，都是后手必胜。 SG 函数 对于多个独立的游戏，可以分别计算它们的 SG 函数值，再求 Nim 和（即异或和）； 对于单个游戏，每个状态的 SG 函数值都是它的所有后继状态的 SG 函数值的 值； 特别地，终止状态（即没

期望 定义：离散版本和连续版本，通常 OI 里用到的是离散的，也就是 期望在任意条件下具有线性性，即 期望在无关的情况下可以相乘，即如果 无关， 条件概率 定义： 是 发生的情况下， 发生的概率 生成函数 生成函数（Generating function），又称母函数，是一种形式幂级数，通过其系数揭示序列信息。生成函数

前言 B 班太难了，回 C 班了。。。 二项式反演 二项式反演经常被使用于那些求恰好为 个的方案数的问题。 常用形式： 表示至多 个的方案， 表示恰好 个的方案： gn=∑i=0n(ni)fi⟺fn=∑i=0n(−1)n−i(ni)gig_n = \sum_{i = 0}^{n} {n \choose i}f_i\if

ZR 集训 Day14 - 动态规划与动态规划常见优化方法 前言 今天转 B 班了，题目比较神秘。 P2150 [NOI2015] 寿司晚宴 考虑枚举两个人所选数字的质因子集合。但是 以内的素数很多，这时想到根号分治， 以内的数只会有一个大于 的质因数，所以我们把这个质因数单拎出来。 以内的素数只有 个，很好状压。我们

ZR 集训 Day13 - 同余、线代入门 P4774 [NOI2018] 屠龙勇士 将题目转化为解方程组： {atack1x≡a1modp1atack2x≡a2modp2…atacknx≡anmodpn\begin{cases} atack_1x\equiv a_1 \mod p_1 \ atack_2x\equiv

2026 暑假 C 班 Day2 之学废离去 二进制与一 IV 想不到吧，T1也能挂，还是没加 long long，简直唐飞了。 代码： C++ #include using namespace std; #define int long long const int N=45; int T,x,idx,ans; bo

ZR 集训 Day11 - 矩阵、递推与动态 DP P1349 广义斐波那契数列 $$ \begin{bmatrix} a_i & a_{i+1} \end{bmatrix} \times \begin{bmatrix} 0 & q \ 1 & p \end{bmatrix} = \begin{bmatrix} a_{

ZR 集训 Day10 - DP 优化 P1886 【模板】单调队列 / 滑动窗口 模板，不知道为啥之前一直 20 pts。 C++ #include using namespace std; const int N=1e6+5; int n,k; int a[N],q[N]; void get(int y){ int

状态压缩 DP，数位 DP P1433 吃奶酪 设 表示当前选择的集合为 时，最后一个拿到的奶酪为 ，所走的最小距离，就可以枚举最后一个点和走到的新点进行转移，复杂度 。 代码： C++ #include using namespace std; int n; double ans=1e9; double x[25],

ZR 集训 Day8 - 区间 DP、树形 DP P1880 [NOI1995] 石子合并 区间 DP 模板，代码： C++ #include using namespace std; const int N=205; int n,ans=1e9; int a[N],sum[N],f[N][N]; signed mai

2026 暑假 C 班模拟 Day1 之全员 AK | 正睿 OI 合并果子 一眼二分，check 直接瞎搞一通。 一开始地瞎搞了 1h 的链表，发现自己是糖丸。 C++ #include using namespace std; #define int long long const int N=1e6+5; int

ZR 集训 Day6 - 可持久化、虚树 SP11470 TTM - To the moon 可持久化线段树题。 会发现对于区间修改我们是需要懒标记的，但是对一个版本打了懒标记后下传可能会影响其他版本。这里用到了标记永久化的思想，打上懒标记后不下传，而是在统计答案时递归作为参数下传。 代码： C++ #include

ZR 集训 Day5 - 树上信息维护 CF1009F Dominant Indices 长链剖分模板题，和重链剖分一样，只不过把重儿子的定义换成了深度最大的儿子。对于一点的深度的定义，是这个点与这个点子树内叶子节点距离的最大值加一。 当 DFS 至一个点时，我们用常数的复杂度将其重儿子的 DP 值转移给它，并暴力地将

ZR 集训 Day4 – 平衡树及其应用 P6136 【模板】普通平衡树（数据加强版）（P3369 【模板】普通平衡树） 这俩就改改输入的区别，就按加强版来讲了。 这里使用的是 FHQ Treap，因为它非常简洁易懂，只需要核心掌握两个操作：分裂和合并。 分裂 分裂函数需要四个参数 ，意思是将以 为根的 Treap 按

ZR 集训 Day3 - 基础分块算法与离线算法 P8253 [NOI Online 2022 提高组] 如何正确地排序 - 洛谷 1. 显然 ， 那答案就会等于 。 2. 先考虑最大值，最小值可以取反后再求一遍最大值。 我们假设 是最大的，就有两个关系： 得到两个偏序关系后，就变成了二维偏序问题，直接排序+BIT 即

ZR 集训 Day2 - 线段树进阶 CF915E Physical Education Lessons 动态开点板子，代码： C++ #include using namespace std; #define lc(p) tr[p].lson #define rc(p) tr[p].rson int n,q,idx,

ZR 集训 Day1 - 基础数据结构及其应用 AT_abc380_e [ABC380E] 1D Bucket Tool 使用并查集表示一个连通块，分别用 表示连通块 的颜色、左端点和右端点。 进行修改操作时，要向当前连通块的左右两边看看能否合并。 代码： C++ #include using namespace st

P2245 星际导航 这是一道模板题，借这道模板解释 Kruskal 重构树的构造与作用。 定义 Kruskal 重构树是基于 Kruskal 的最小生成树算法在无向图中得出的树所构造而成的树。 构造 上图是样例 上图是样例的最小生成树 C++ void ks(){ for(int i=1;i `void ks(){

P4129 [NEERC 2005 / SHOI2006] 仙人掌 显然得到答案为 ，其中 表示环的个数， 表示环的边数。 注意需要使用高精度。 C++ #include using namespace std; const int N=1e5+5; #define int long long int n,m,cnt,

2026 暑期每日一题 6月25日 P4643 [国家集训队] 阿狸和桃子的游戏 观察到题目要求的是得分之差，如果我们将边权均分给两个点，会惊喜的发现对答案没有任何影响，之后就贪心即可。 代码： C++ #include using namespace std; const int N=1e5+5; int n,m,a

基环树 P2607 [ZJOI2008] 骑士 没有上司的舞会的加强版，找到基环树的环之后断开一条边，以断边的两个端点为根 dp 即可，注意原图可能是森林。 代码： C++ #include using namespace std; #define int long long const int N=1e6+5; st

P6399 [COI 2008] TAMNICA 在没有打破墙的时候，任意两点 的距离应该是 ，所以走破了的墙一定是最优的，那我们就可以把起点、终点和打破了的墙的两侧作为关键点跑一遍最短路。 现在问题在于怎么求墙的另一侧，如图： 我们把数字按 的长度分组，每一组又分为左右两个部分。 设当前数字为 ， 所在的组为 ，那就

P15729 [JAG 2024 Summer Camp #2] Add Add Add 不难发现，当前答案应该是上一个答案加上 的贡献，所以考虑求： 前缀和即可。 代码： C++ #include using namespace std; #define int long long const int N=2e5+5

P15465 [ICPC 2024 WF] Bingo for the Win! 宾果游戏的胜利！ 不难发现，对于一个号码，只有拿到这个号码的反应最慢的人才会产生贡献，贡献为 sumnk\frac{sum}{nk}，其中 sumsum 表示号码的个数，所以这启示我们在统计答案是从反应慢的开始遍历到反应快的（也就是编号从

P15889 [COCI 2025/2026 #6] 零花钱 / Džeparac 考虑枚举每个孩子总共获得的钱数 ， 根据题意知道，可以将 ii 分成几天发放，可以看成把 分成若干部分，就变成了在 i−1i-1 个空中放板子，每个空放或不放，共 2i−12^{i-1} 个方案。 再加上每个孩子都不给零花钱的方案，答案

P16112 「o.OI R-1」青蛙平衡树 一个或两个点是一定中心对称的，所以先特判掉这种情况。 对于一般情况，先尝试能不能只在一维上做。 不难发现直线上连续的点一定是中心对称的，所以第一个点直接输出 ，后面要是保持中心对称，就继续向右把线延长就行了。 对于不对称的点，直接空一个输出。接下来要是要保证中心对称，就返回

P16265 [蓝桥杯 2026 省 Python B 组] 蓝小圈 看题，很经典的并查集问题，难点在于当集合合并时怎么做到使原来集合整体操作互不干扰。 这个有很多种办法解决，这里介绍其中一种：按秩合并。 大部分时候我们使用路径压缩的方法优化并查集的合并操作，这样无法保留树的结构。 当我们使用按秩合并时，就可以保留历史

P16166 [ICPC 2015 NAIPC] Magic Checkerboard 特殊情况： 或 这个很好想，应为在这种情况下不存在两个格子只有一个公共角，所以只需要贪心地满足横向或者纵向是递增的就可以了，期间加上对已经放了数的格子的判断。 一般情况： 且 我们可以把表格按对角线染成黑白两种颜色，如下图： 黑白格

P16161 [ICPC 2016 NAIPC] Tourists 不难看出，枚举所有的点对的复杂度应为： 这时，对于每组点对我们树剖求 LCA，时间复杂度为 ，所以总复杂度为 ，可以通过此题。 代码： C++ #include using namespace std; #define int long long co

P16159 [ICPC 2016 NAIPC] Symmetry 思路 先考虑枚举所有可能的对称中心和对称点。 用两个 map 记录每个对称中心或对称轴对应了几组对称点，再用一个 map 记录点的存在情况。 我们 n2n^2 枚举每两个点。 对于对称中心，我们把两个点的中点加一次贡献； 对于对称轴，我们把两个点的连线

P4103 [HEOI2014] 大工程 先建虚树，对于最大值和最小值是很好维护的，对于总和，我们用一个标记记录当前节点作为 lca 的贡献次数，递归到子节点后在加上贡献次数。 C++ #include using namespace std; #define int long long #define lc p t[

P3834 【模板】可持久化线段树 2 模板，直接看代码： C++ #include using namespace std; #define lowbit(x) x&-x const int N=2e5+5; int n,m,cnt; int ans[N],tree[N]; int maxn=INT_MIN,minn

P2709 【模板】莫队 / 小B的询问 模板，直接看代码吧： #include using namespace std; #define int long long const int N=5e4+5; int n,m,k,siz,sum; int a[N],c[N],ans[N]; struct ask { int

根号分治 P3396 哈希冲突 一眼根号分治，小就暴力，大就预处理，没啥好说的。 代码： #include using namespace std; #define int long long const int N=1.5e5+5; int a[N],dp[1000][1000]; int n,m,x,y; char

P10872 [COTS 2022] 移位 Maliand 考虑 S,TS, T 的每个位置只会相匹配 1 次，共匹配 NN 次，产生贡献的有 K⋅LK\cdot L 次， 所以想要所有匹配中贡献最大的最小，平均分配即可，答案就应该是 ⌈KLN⌉\lceil \frac{KL}{N} \rceil。 先考虑 SS，1

分块 P2801 教主的魔法 分块即可，复制一个数组保持块内有序，然后用一个数组记录块整体的加减情况，就可以了。 代码： #include using namespace std; #define int long long const int N=1e6+5; int n,x,m,q; int a[N],b[N];

P7915 [CSP-S 2021] 回文 先考虑第一个选 L 的情况，第一个选 R 的情况是同理的。 找到与 a1a_1 相等的数 axa_x，把 [2,x)[2,x) 和 (x,2n](x,2n] 看成两个双端队列， 按照字典序分类讨论，每次取两个队列的一个顶部和一个底部， 然后往答案字符串两边加字符即可。 代码：

P3599 Koishi Loves Construction 对于 Task 1，首先 nn 肯定要放在第一个，否则会出现两个前缀和模 nn 相等。 其次考虑 nn 为奇数的情况显然是不成立的，因为总和为 n(n+1)2\frac{n(n+1)}{2}，显然模 nn 为 0，同样会出现两个前缀和模 nn 相等。 考虑

计数问题2 一些公式 吸收/提取恒等式：i⋅(i−1j−1)=j⋅(ji)i \cdot \binom{i-1}{j-1} = j \cdot \binom{j}{i} 上指标反转：(rk)=(−1)k(k−r−1k)\binom{r}{k} = (-1)^k \binom{k-r-1}{k} 范德蒙德卷积公式：∑k(

钦定 Y_1">X1>Y1X_1>Y_1，不难发现必须满足 Y_{max},\ X_{min}>Y_{min}">Xmax>Ymax, Xmin>YminX_{max}>Y_{max},\ X_{min}>Y_{min}， 再看特殊性质，不难发现直接递归求解即可，每次检查是否能达到当前的 XmaxX_{max} 或 Y

题解 - 南昌五中初一第二次阶段测试 & ooliver 的复仇 说在前面 这次题目确实有点难，但是大家要习惯信奥比赛中遇到难题时的压力，所以没有必要抱怨题目的难度，毕竟大家都不会…… 信奥分组 不难发现，偶数+偶数=偶数，所以只要 nn 是偶数就可以了？ 因为每组人数既要大于 0，也要为偶数，所以每组最少 2 人，也

P6561 [SBCOI2020] 人 考虑把 2i−1, 2i (0i≤m)2i-1,\ 2i\ (0 放在一起看，那么每组一共有三种情况： A：2i−12i-1 选，2i2i 不选。 B： 不选，2i2i 选。 C：都不选。 且有一个限制，就是不允许相邻两个组别组成 BA 的形式，因为这样前一组的第二个和后一组的第

P9915 「RiOI-03」3-2 考虑将表格逆时针旋转九十度。 首先易证得一个结论：对于一个点，竖直向上找到同颜色的，若它是从下往上数的第 kk 个（从 0 开始），那么连通块的大小就是 2k−12^k-1。 对于一个 x">2y>x2^y>x，要找的位置一定是 0，那么向上找一定是第 nn 层的 0，直接输出 2

组合数学 P3807 【模板】卢卡斯定理 / Lucas 定理 (nm) mod p=(⌊np⌋⌊mp⌋)⋅(n mod pm mod p) mod p\begin{aligned} \begin{pmatrix} n \ m \end{pmatrix} \ mod \ p = \begin{pmatrix} \lfl

P11022 「LAOI-6」Yet Another Graph Coloration Problem 用 Tarjan 求点双连通分量，找一个大小 ≥3 的分量，将其节点一半染 B、一半染 W，然后从这个分量开始 BFS 往外染色，同色向外扩展，保证不同色节点在同一个点双内，从而满足题目要求的“任意异色节点间至少有两

P11036 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题 不妨令 b=1, gcd(c,d)=gb=1,\ gcd(c,d)=g，所以 a+c+d=cdga+c+d=\frac{cd}{g}。 设 a=2p⋅k (2∤k), c=xg, d=yg (gcd(x,y)=1)a=2^p \cdot k \

P11132 【MX-X5-T4】「GFOI Round 1」epitaxy 考虑到 nn 一定会有贡献，当把 nn 放在第 mm** **个时，前 m−1m-1 个数一定没有任何贡献。 所以找到贡献最大的，作为最终的 GCD，其余从大到小放即可。 #include using namespace std; const

P11145 「SFMOI Round I」Strange Homura Game 很臭的题号…… 观察到 xx 的范围远大于 mm，询问一个很大的 x1x_1，得到回答 y1y_1，设 x1=km+y1x_1=km+y_1，则有 x1−y1=kmx_1-y_1=km， 这时令 x2=x1−y1−1x_2=x_1-y_

CDQ 分治 P3810 【模板】三维偏序 / 陌上花开 模板，没啥好说的 代码： #include using namespace std; #define int long long const int N=1e5+5; const int K=2e5+5; int n,k,m,t; int res[N]; str

P11190 「KDOI-10」反回文串 观察到两个特殊性质： 对于特殊性质 A，易证一定有 ⌊n2⌋\lfloor \frac{n}{2} \rfloor 组长度为 2 或 3 的分配方案。 对于特殊性质 A 相反的，即有一种字母数量大于 ⌊n2⌋\lfloor \frac{n}{2} \rfloor，可以先把数量小

P11277 世界沉睡童话 观察到一个性质，就是 [n,2n)[n,2n) 中每个数相互无法整除。 又观察到 1 可以带来 n−1n-1 的贡献，xx 个相同的数可以带来 x(x−1)2\frac {x(x-1)}{2} 的贡献， 所以根据这个性质模拟即可。 代码： #include using namespace s

树状数组 P3605 [USACO17JAN] Promotion Counting P 很模板的一道树上树状数组， 计算遍历子树后的变化就可以了， 代码： #include using namespace std; #define lowbit(x) x&-x const int N=2e5+5; int n,m;

P4556 【模板】线段树合并 / [Vani 有约会] 雨天的尾巴 #include using namespace std; #define int long long #define lc(x) tr[x].l #define rc(x) tr[x].r const int N=1e5+5; int n,m,id

中国剩余定理 CRT P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 中国剩余定理（CRT）证明 定理陈述 对于一组互质的正整数 ，以及任意整数 ，同余方程组： 在模 下有唯一解。 证明步骤 构造解的存在性 定义总模数： 求逆元： 由于 两两互质，所以 与 互质： 因此存在整数 使得： 这里的 是 在模 下的乘

高斯消元 P3389 【模板】高斯消元法 这里使用的是高斯消元法，即变换成上三角矩阵后回代求解。代码： #include using namespace std; const int N=55; const double eps=1e-8; int n; double a[N][N],ans[N]; double ab

线段树分治 线段树分治，顾名思义，就是用线段树进行分治。 P5787 【模板】线段树分治 / 二分图 首先，我们知道二分图的一个充要条件是没有奇数环。 所以，这道题中，线段树维护的是每个时间的区间内存在的边。 而这里使用染色法判断二分图显然时间复杂度会超， 所以需要用到可撤销并查集，即用栈维护每次并查集的操作。 根据以

#include using namespace std; #define int long long const int N=1505; const int mod=1e9+7; int T,n,p,m,k; int a[N][N],c[N][N],f[N],inv,inv1; int qpow(int x,int

主席树 P3919 【模板】可持久化线段树 1（可持久化数组） #include using namespace std; #define lc tr[p].l #define rc tr[p].r const int N=1e6+5; int n,m,idx; int a[N],rot[N]; struct tree

数学3（欧拉函数） P13880 [蓝桥杯 2023 省 Java A] 互质数的个数 看完题面后很容易想到欧拉函数， 但是 是一个很大的数， 考虑一些特殊的性质：，（ 为质数） 所以令 ， 所以 因为欧拉函数是积性函数， 所以 代码： #include using namespace std; #define int

数学2（容斥原理） P3197 [HNOI2008] 越狱 发生越狱的状态数=总状态数-不越狱的状态数， 很显然总状态数为 ， 而不越狱的状态数应该是同样宗教互不相邻， 第一个房间有 种，其他房间都是 种， 所以状态数应该是 。 答案： 代码： #include using namespace std; #define

CSP-J/S 复赛+武汉ICPC游记 2025.10.31 晚上 为什么要写前一天晚上呢？ 实不相瞒，我们把“NC站”看成了“NC西站”，导致我们到了西站之后突然发现火车是“NC站”的， 于是改签了一个晚了一个小时的火车，没有出啥事…… 2025.11.1 上午（CSP-J） 前面两题非常轻松，纯热热身。 第三题一看

2022csp复现赛 P8816 [CSP-J 2022] 上升点列 首先很容易想到对所有的点进行排序。 设 表示以第 个点为结尾，添加了 个点的点序列最大长度。 考虑从所有的 $j(0 #include using namespace std; #define int long long const int N=50

数学小组作业：探究圆的方程 一、园的标准方程 i) 圆心在原点上（特殊） 观察这个图形，不难发现它是以原点为圆心，半径为 2 的一个圆形。 那么圆上的任意一点满足什么条件呢？ 我们知道，任意一点到圆心的距离都是一定的，那就是——半径 。 那么图中圆上的每一个点都满足 ，这就是这个圆的标准方程。 此时不难发现，一个半径为

10.7 div2复现赛 P14178 「FAOI-R8」Jueves 可以发现一些性质： 当 时，显然答案为 0 否则，最短路一定是连接 与 的那条边，因为 。 所以代码非常简单： #include using namespace std; #define int long long const int N=5e5+

U610469 牢高的压轴题 题目背景 这是 ooliver 与 Deepseek 的聊天记录： —老高太强了，这怎么玩？必须削弱！ Deepseek（已深度思考114514秒）∧ 有的兄弟，有的。 —那这题咋写? Deepseek（已深度思考0秒）∨ 系统繁忙，请稍后再试。 题目描述 周清时间到了，来看看老高

CSP-J/S 2025初赛游记 上午（CSP-J） 赛前心态非常稳定，毕竟是奔着下午的提高组去的，所以没什么压力。 普及组的试卷做起来还是十分的顺利的，知道我看到了最后一题：交互题！！！ 直接给我干蒙了，想了半天才把答案填上去。 正当我惊魂未定开始检查时，突然发现第一题居然问居然有个无符号，我立马把 改成了 。 比赛

论鸡汤之文三篇 鸡汤说 夫鸡汤者，味甘而性腻，初饮可暖肠胃，久嗜则蔽灵台。今有司教向南子，日执勺釜以哺诸生，然其道渐偏，犹烹鲜而失其火候，吾窃为惑焉。 昔者齐宣王好听竽，南郭处士窃食廪粟；今班吏持册执朱，虚增分数以媚上。或篡默诵之次数，或浮洒扫之勤绩。向南子持汤勺而叹曰：“善哉！此子必怀瑾握瑜。”乃更倾浓汁以润之。及见

数学专题B2—裴蜀定理 P4549 裴蜀定理 裴蜀定理 题目思路 显然由前置知识可知： 对于当前的 和 ， 所以代码如下： #include using namespace std; #define int long long signed main(){ int n,x,ans; cin»n»ans; for(i

数学专题B1—同余 P3935 Calculating 设 ， ， 对于 ， 枚举每一个因数出现的次数，并按照次数分块， 所以可以得到以下代码： #include using namespace std; #define int long long const int mod=998244353; int L,R; i

DAY1 A. 剪切字符串 可以想到一个简单的贪心， 就是在最坏情况下，我两个字串长度都取 ， 此时 最大为 ，即每个 最大为 。 所以我们贪心地认为 ， 此时可以对字符串 中的每一个字母个数进行前缀和， 然后枚举 ，判断 的字串中能否找到一个字母异于 和 。 代码如下： #include using namespac

S+CSP2025模拟赛8 A. 输出字符串 按照题意模拟即可。 （不要用数组，要用vector，用数组直接MLE） 代码： #include using namespace std; int n,k; vector a[30]; int pnt[30]; int main(){ freopen(“zigzag.in”

S+CSP2025模拟赛7 A. 俄罗斯方块 暴力枚举。 代码： #include using namespace std; const int M=100; char g[M][M]; bool v[M][M]; int n,m; int c[5]={0}; struct B{ char clr; int p[4][

S+图论综合 A. 说谎的牛牛 枚举每一个牛作为说谎的牛是否矛盾， 再差分约束建图，跑一边SPFA就可以了， 代码： #include using namespace std; #define int long long const int N=105; const int M=1005; struct node{ i

S+CSP2025模拟赛6 A. 劫富济贫 题意可以简化为在 次操作后， 使最穷的人最富，最富的人最穷。 所以考虑二分答案两个端点，把找到的答案减一下就可以了。 注意当 特别大是，差距可以来到 以内，所以特判一下。 代码： #include using namespace std; #define int long l

S+CSP2025模拟赛5 A. 逆转 按时间模拟即可， 懒得一个一个加分数，所以把连续的得分合并了一下， 代码： #include using namespace std; const int N=3005; struct node{ int t,id; }f[N]; int a,b,x,idx; int s1,s2

S+数论，高斯消元，线性基 A. B进制数与B-1倍数查询问题 需要的前置知识：设一个 进制数为 ，数位和为 ，那么： 证明： 由此得证。 根据这一点，为了使这个数足够大，首先肯定要更多的数位， 所以我们减去一个 ， 最后在前缀和数组中二分查找 即可。 代码： #include using namespace std;

S+20250816测试 A. 回文插入 暴力找到插入位置即可， 代码： #include using namespace std; int ans; string a,b; bool check(string s){ for(int i=0,j=s.size()-1;i>a»b; for(int i=0;i `#i

S+二分图与网络流初步 A. 生成二分图 找出所有的二分图， 对于每个二分图自己，所有的连接方案肯定是两种颜色的乘积的两倍， 而单个二分图中每个点都可以与其他二分图的点相连，因为会重复计算，所以不用乘二。 最后因为 等价于 ， 所以把所有合法的边数除以 再减去已经有了的边数 就能得到答案。 代码： #include u

S+20250814测试 A. 交换序列 暴力枚举即可 代码： #include using namespace std; int n,y=1,ans; int a[55]; int main(){ cin»n; for(int i=1;i>a[i]; if(a[i] `#include using namespac

S+启发式合并，分治，扫描线 A. 集合操作2 并查集+set+二分，模拟即可， 代码： #include using namespace std; const int N=2e5+5; int n,m,o,a,b; int v[N],f[N],s[N]; long long t[N]; setst[N]; int f

S+20250812测试 A. 炫彩染色 枚举两种情况，输出最小答案即可， 代码： #include using namespace std; string s; int ans1,ans2; int main(){ cin»s; for(int i=0;i `#include using namespace std

S+图的连通性与2-SAT A. 校园网 注意到强连通分量内的点肯定是符合的，所以进行缩点， 第一问很容易能想到答案是缩点后图内无入度的点， 而第二问可以发现一定要将所有无出度的点和无入度的点相连， 所以答案就是缩点后图中无入度的点的数量和无出度的点的数量的最大值。 代码： #include using namespa

S+CSP2025模拟赛4 A. 奥数题 直接暴搜所有出现的字母可能代替的数字即可， 注意除法是正常的除法，不取整。 #include using namespace std; string a,b,c,d=“0”; map m; int t[6],tag[15]; int ans,n; int toint(strin

S+20250808测试 A. 沙漠化 暴力BFS即可。 #include using namespace std; int n,m,t,ans; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; string a[15]; struct node{ int x,y,id; }; queue q

S+字符串算法应用 A. 大厨的特色菜 这题直接分类讨论+暴力即可。 首先，当字符串长度小于 2 时，是肯定不满足条件的。 当字符串长度是偶数时，直接判断字符串前半段与后半段是否相等。 如果字符串长度是奇数，那么就枚举删除哪一个字符，再按照长度为偶数是的判断方法来判断即可。 #include using namespa

题解：CF226A Flying Saucer Segments 本蒟蒻的第一篇题解，请大家多多支持 思路 看到题的第一眼，想必大家都想到了 汉诺塔问题，可是当再次仔细查看此题，每一次只能移动到相邻的“柱子”，所以需要重新推导一遍通项。 先设人数为 时，答案为 。 众所周知，汉诺塔的通项为 ，那么此题的通项肯定与它相关