在讨论《大家一定要相信自己 会赢的》回复：

最想赢得一集

在讨论《大家一定要相信自己 会赢的》回复：

NOIP RP++

在文章《Fate》发表评论：

%%%

## 引入 原本我对容斥原理的了解一直停在求若干集合的并集大小，但那只是容斥原理的一种应用，它既然叫**原理**，自然不只是一个公式。 ## 介绍 容斥原理的基本思想是利用带有**容斥系数**的求和来**修正**原本会算重或算漏的统计。是一项用**钦定**算**恰好**的技术。 ### 举例：P11563 【MX-X7…

## 引入 子集反演又叫容斥原理的一般化，但我之前一直不知道怎么用子集反演推导容斥原理，现在终于会了。 ## 推导 **子集反演（补集形式）**： $$ f(S) = \sum_{T\supseteq S} g(T) \Leftrightarrow g(S) = \sum_{T\supseteq S} (-1)^{|T…

```cpp chrono::system_clock::now().time_since_epoch().count() ```

### P14362 [CSP-S 2025] 道路修复 / road 我们可以发现有很多边是用不到的。然后 $2^k$ 枚举，一边归并一边做 Kruskal。 ### P14363 [CSP-S 2025] 谐音替换 / replace 意外的简单。 注意到能否替换可以等价于“复合串”（二元组一个字符）的匹配，这个匹…

在文章《题解：P14363 [CSP-S 2025] 谐音替换 / replace（暂无数据）》发表评论：

是用map存aca，然后转移的时候直接跳fail吗？

在文章《题解：P14363 [CSP-S 2025] 谐音替换 / replace（暂无数据）》发表评论：

这个log是怎么带上的？

一个人类，不应该在一共只有 4 道题的情况下读错 2 道题。

### 一 ```cpp fac[0] = 1; rep(i, 1, n) fac[i] = fac[i - 1] * i % P; ifac[n] = qpow(fac[n], P - 2); per(i, n - 1, 0) ifac[i] = ifac[i + 1] * (i + 1) % P; ``` 这样可以…

### 介绍 边双缩点得到树，强连通缩点得到 DAG，而点双与之对应的就是圆方树。 我们这里将**点双**定义为**不存在割点的图**，在点数 $> 2$ 的时候等价等价于**任意两点间存在点不重合的两条路径**。 单点不定义是否为点双，根据题意特判。 在圆方树中我们有**圆点**和**方点**，原点对应原图的点，而方…

在讨论《一个诡异的现象》回复：

@[bsdsdb](luogu://user/790188) 话说我之前也有类似问题。我是用高版本编译器在编译完后立马运行就会卡一下，如果过一会再运行就不会卡。但是用 DEV 里带的就不卡。

在讨论《一个诡异的现象》回复：

@[Steve_xh](luogu://user/639198) 学到了

在讨论《一个诡异的现象》回复：

@[潘德理2010](luogu://user/572133)@[_Ad_Astra_](luogu://user/317622) wc有用

这一段代码在我的 DEV 5.11 中运行会在读入之前卡 5 秒钟，但使用同一个编译器，在命令行编译运行则不会卡顿。同样使用 DEV 5.11，不开 O2 也不会卡顿。 可能的原因是什么？ ```cpp #include #define int long long #define rep(i, l, r) for (i…

在讨论《ATCODER怎么炸了》回复：

@[Miracle640](luogu://user/1557225)梯

### 前言 基本承袭 gcx12012 大佬的思路，但删除部分显然有更简洁的做法。另外代码并不会多一次操作。 ### Solution 我们考虑维护当前构造的集合 $S$，记目标集合为 $T$。初始时我们令 $S=A_n$，其实可以令其为任意的 $A_i$。 枚举 $i=1,\dots,n$，用 $A_i$ 去更新…

### 前言 看着 [rui_er 的笔记](https://www.cnblogs.com/ruierqwq/p/kruskal-reconstruction-tree.html) 学的。 ## 简介 在 Kruskal 执行过程中，每次合并两个并查集的时候，建立一个虚拟节点表示合并后的并查集，其两个儿子为合并前两个…

### CF2146E Yet Another MEX Problem 经过一定尝试，我们发现区间快速求 mex 并不好做，因为 mex 本身的含义太复杂了，我们尝试解构 mex，即考虑其定义：不包含于 $a$ 的最小自然数。我们尝试考虑所有不包含于 $a$ 的自然数。 对于数列 $a$，以及 $x \notin a$…

转移时候拿个除法的常数比较大，可以预处理存下来。于是 TLE --> 400ms。

上午被热身赛 A 随机构造给整蒙了。 茶点好吃。 中午饭菜不错，看同学打音游，喝了一杯糖水（埋下伏笔）。 下午正式赛窜了三次。 M 题拼尽全力无法战胜，第二天发现有个 `i + 1` 打成 `i` 了。明明我还专门检查了这种错误。。。 出来后被 wj 的气球束吓雍了。 得知 K 经过线性变换面积比不变，于是转化成直线截…

在文章《2025 CityUCPC 游寄》发表评论：

以为你这么高效（

会有 `/ 0` 错误。 现在理解为什么通过率这么低了。

## R14 ### T1 略。 ### T2 通过一些观察，我们发现操作序列一定形如 `C P C P P P C P P ...`。 我们将每一段长度记为 $a_i$，有 $k$ 段，则字符串长度为 $\prod_i{a_i}$，花费为 $\sum_i{a_i}$。 我们需要在满足 $\prod_i{a_i} \g…

## 介绍 Boruvka 算法相当于多源的 Prim。我们维护若干个块。 刚开始 $T$ 中没有边，每个点都是一个块。 在每轮算法中： 1. 找到每个块的**最小边**（最小的向外连的边）。 2. 一次尝试连接每个最小边。 算法进行 $O(\log n)$ 轮。 算法的具体复杂度取决于求最小边的方式，这是根据题目而定…

汇总一些离线方法和相关题目。 ## 扫描线 十分脍炙人口的技巧。 一般枚举查询的某一维，同时维护一些信息，以便在恰当的时机可以快速更新查询的答案。 ### P4211 [LNOI2014] LCA **技巧 1**：差分，$[l,r]$ 转换为 $[1, l - 1]$ 和 $[1, r]$。 **技巧 2**：离线技…

### 简介 利用根号平衡的思想对问题进程分治解决。 ## 例题 ### CF506D Mr. Kitayuta's Colorful Graph 依次考虑每个颜色 $c$，用并查集合并，我们有两个算法。 **算法 1**：扫描 $q$ 个询问并更新，单次 $O(q)$。 **算法 2**：考虑同一颜色的点对，对答案的…

### 题意 给定若干区间，每个区间有概率存在或不存在，问区间覆盖 $[1, m]$ 的概率。 ### 分析 考虑 DP。 用 $f_i$ 表示 $[1,m]$ 被恰好覆盖一次的概率。利用区间进行转移，我们用一个 `vector` 记下，以每个位置为结尾的区间编号。那么 $$ f_i = \sum_{j:r_j = i…

[为什么改写法之后在LOJ上更快了，在洛谷上T了](https://www.luogu.com.cn/discuss/1135518)