在讨论《Only AC 最后一个点求调》回复：

现在 AC 了 ```c++ #include #include #include #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; const int N=2e6+5; struct Segment_…

[我的帖子](https://www.luogu.com.cn/discuss/1206944)

```c++ #include #include #include #define int unsigned long long #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; struct Segm…

如果你 AC 样例但是 MLE， 那么在 Dfs 找合法边的时候，以下写法是正确的： ```c++ void Check(int u) { if(can[u]) return; can[u]=true; arrive++; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; Edg…

在讨论《莫队求问》回复：

没有

应该是退役前的最后一篇题解了吧。 ## 简要题意 对于长度为 $n$ 的排列 $p$，对其构建大根笛卡尔树后断掉每个节点与右儿子的连边形成森林 $T(p)$，求有多少个排列 $p$，满足指定节点 $x,y$ 属于同一连通分量。 ## 思路 当 $x=y$ 时答案显然为 $n!$，下面考虑 $x #define IOS…

## 思路 删边操作显然离线倒序后做加边操作，答案则是所有连通块直径的最大值。对于新加入一条边连接起来的两个连通块，通过枚举两端点暴力维护直径显然是单次 $\mathcal O ( n ^ 2 )$ 的。考虑优化，需要知道的一个性质是两棵树通过一条边连接后新树的直径两端点必定来自于原树直径端点。 证明也很简单，假设 $…

在文章《P10238 [yLCPC2024] F. PANDORA PARADOXXX》发表评论：

tql%%%

## 思路 直接判断哪些边能不能变成 $0$ 是不对的，因为它可能会经过两条不可能在同一条最短路中的边。 发现一定有一组最优解满足 $U$ 到 $V$ 中的最短路恰有连续的一段是变成的 $0$。然后把每个点拆成三个点，表示未到这一段、正在这一段和已过这一段三种情况，然后再跑最短路就可以了。 ## Code ```c++…

在讨论《40 pts WA 求条》回复：

@[WanderFreeFish](luogu://user/831588) 唐

在讨论《40 pts WA 求条》回复：

stO Orz 附 AC 代码 ```c++ #include #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; const int N=3005; int n,m,minn[N],maxx[N]; i…

如题，为什么说会被卡。 ```c++ #include #include #include #include #include #include #include #include #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using…

## 题意简介 给定一棵 $n$ 个节点的带权树，根节点为 $1$，每条边有一个容量和单位容量的花费，选择任意多条从根节点出发的路径，求最大容量和此时的最小花费。 ## 思路 考虑贪心，对每个点求 $dis_i$ 表示从 $1$ 到 $i$ 的边权和，显然每次应该尽量满足 $dis_i$ 更小的点的要求。这个思路很好证…

## 题意简介 初始数对 $( a , b )$，每次可将其一替换为二者之差或和，判断能否在保证任意时刻 $a , b \geq k$ 的前提下得到数对 $( x , y )$。 ## 思路 注意到取和操作可通过两次取差操作抵消，故只进行取差操作。$( a , b )$ 直接向 $( x , y )$ 靠拢复杂度过高，…

## 思路 这个形式很容易联想到 Fibonacci 数列通项公式： $$a_n = \frac{1}{\sqrt{5}} \Big( (\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n \Big) $$ 令 $x = \frac{1 + \sqrt{5}}{…

## 思路 删掉 $(r_1,c_1)$ 位置上值为 $val$ 的棋子相当于再在原处放置一个相同的棋子使之异或后为 $0$，故只需考虑放置新棋子后的影响。 显然一个棋子无法被攻击的充要条件是其所在行的异或和等于所在列的异或和，故使用 $rval,cval$ 维护行和列的异或和，$rcnt,ccnt$ 维护异或和为 $…

在文章《P12693 BZOJ3589 动态树》发表评论：

%%%

## 简要题意 给定 $n$ 个点的带权树，对每个点可选择 $\leq k$ 条边清零边权，求最小化的以根节点为起点的所有链的边权和。 ## 思路 令 $dp_u$ 表示 $u$ 子树内的最小边权和，首先会取到 $\max \limits_{v \in son_u} dp_v$，然后贪心地删去前 $k$ 大的 $dp_…

## 题意简介 给定一个长度为 $n$ 的环状数组，每次询问给出 $l,r,x$，依次遍历 $i = l , \cdots , r$（如果 $l > r$，从 $l$ 遍历到 $n$，再从 $1$ 遍历到 $r$），若 $a_i > x$，则交换二者的值，输出最终 $x$ 的值，询问之间不互相独立。 ## 思路 每次询…

## 思路 注意到重要性质：每确定一对帐篷，那么这对帐篷所在行和列不能放置其他帐篷，这将解释后来的方案之间为什么不会互相冲突。 考虑设计 $dp_{ i , j }$ 表示营地大小 $i$ 行 $j$ 列时的方案数，逐行计算，对于每一行的放置： - 若第 $i$ 行不放，直接转移 $dp_{ i , j } = dp_…

## 思路 首先要观察出一个结论：虽然不限制同时持有雨伞的数量，但最优解中 Polycarp 一定不存在某一时刻同时持有两把伞。 考虑设计 $dp_{ i , j }$ 表示在点 $i$ 处持有第 $j$ 把伞的方案数，其中 $j = 0$ 时不持有任何一把雨伞。对于 $dp_{ i , j }$ 往后的转移： - 如…

## 前言 这道题的题号于我比较有意义，于是就来写了。 ## 思路 如果暴力枚举所有排列，时间复杂度为 $O ( n ! )$，显然不能通过本题。 考虑贪心的做法，特别地，若 $1 \leq a_i \leq 9$，直接从大到小排序即是最优。但对于 $\forall a_i \in [1,10^9]$，如果还是采用同样…

## 思路 当 $k = n$ 时，我们只需要用树上权值加和减去 $s$ 到 $t$ 的路径长度即可。 考虑对 $s,t$ 是否在关键点组成的最小连通块内分类，记块内边权和为 $sum$。 若 $s$ 和 $t$ 都在连通块内，由特殊性质，当 $s = t$ 只需恰经过每条边两次就可以走完，答案为 $2 \times…

在文章《P9638 「yyOI R1」youyou 的军训》发表评论：

orz%%%

## 题意简介 对于一个带权无向图，给出 $Q$ 次操作，删除原图上边权小于 $val$ 的边，查询某点所在连通块大小，在保证相对大小不变的情况下修改边权。 ## 思路 考虑对原图建立最大生成树重构树，由于修改时不改变相对大小的特殊性，重构树的结构不会发生变化，故修改操作只需 $O ( 1 )$ 修改此边对应点的点权。…

## 思路 首先观察到要么每一行都有车或每一列都有车，否则没有的的行与列交点的格子将不会被攻击。我们只需求到每一行都有车的放置方案数，就可以对称地得到答案。 要使恰好 $k$ 对互相攻击，需要使用的列数为 $n - k$，选择的方案数为 $\binom{n}{n-k}$。再将 $n$ 个车分配到 $m$ 列，方案数 $…

在文章《CSP-S 2025 游记》发表评论：

这个赞，是给数据删除的

在文章《CSP-S 2025 游记》发表评论：

羡慕

在文章《题解：P7098 [yLOI2020] 凉凉》发表评论：

%%%

在文章《CSP-S 2025 游记》发表评论：

%%%