强连通分量一般对有向图而言，点双边双割点割边一般对有向图而言。 [强连通分量]() ```cpp void tarjan(int u){ low[u]=dfn[u]=++timestamp; stk[++top]=u;in_stk[u]=true; for(int i=h[u];i!=-1;i=nxt[i]){ int…

在文章《P14523-solution》发表评论：

%%%

```cpp int stk[N],top; string find(string t,int k){ top=0;int len=t.size(); for(int i=0;i =k && x<stk[top]) top--; stk[++top]=x; } string ans; for(int i=1;i<=k;…

[题目](https://www.mxoj.net/problem/P130142?trainingNumber=T1954) 在一场为期 $M$ 天的梦熊竞赛中，有 $N$ 名选手，编号从 $0$ 到 $N-1$。每天恰好举行一场比赛。整个竞赛共颁发 $M$ 枚奖牌，每场比赛颁发一枚新奖牌。 在第 $i（0 \leq…

对于一个已经求完最短路的图，现向其中加入若干条边想求新图的最短路，只需要对于每个点 $u$ 连一条 $root \to u$，长度为 $dis_u$ 的边，加入新边跑最短路即可。 同理：对于一个已经求完最小生成树的图，现向其中加入若干条边想求新图的最小生成树，只需要保留之前最小生成树上的边，对新图跑最小生成树即可。 最…

此 trick 旨在对于具有特殊单调性的数据，通过两个队列归并的方式线性模拟堆的功能。 如果对于加入堆中的数据，可以简单地将其分成 $k$ 种类型，并且满足每种类型的插入元素在时间上都有单调性，则我们可以开 $k$ 个队列分别存储这 $k$ 种元素，每次需要弹出时，比较这 $k$ 个队列的对首元素弹出即可，复杂度 $O…

不要先枚举 $(ab)^k$ 的最后一个点，再枚举因数（即使是nlogn预处理的），这样常数很大。 应先枚举循环节长度，再向后寻找可能的 $(ab)^k$。 即将 ```cpp for(int i=2;i<n;i++){ int len=i-nxt[i],lim=fr[i+1]; if(i%len) len=i; in…

重复计算 考虑贡献 正难则反 等价转换 分离变量 局部最优 应用算法 数据结构

在讨论《找题》回复：

P4653 原题机搜到的 赞美 @TLE

在讨论《进食后人/If you WA on #7 8 9 10 11 13》回复：

%%%

在讨论《站外题悬关求助》回复：

@[Stardust_Mirage](luogu://user/966300) 已关 /bx/bx

[原题](https://www.acwing.com/problem/content/description/148/) 我突发奇想，能不能不用优先队列，每次枚举可能作为答案的数的范围，把所有可能产生的数全塞到数组里，排序后取前 $n$ 个，为什么WA了awa 代码： ```cpp #include #define…

当check函数的复杂度和需要被check的区间长度有关，切需要被chek的区间的总长度一定时，二分并不能很好地利用这一性质，所以可以用倍增。 定义 $p$ 为每次要增加的区间长度。 - 若 check(l,r+p) 则```r=r+p,p*=2;``` - 否则，```p/=2```，并且以后执行第一个操作的时候也将…

在文章《whk 是我们最后的防线》发表评论：

上了生活的贼船，就做快乐的海盗

Linux虚拟机 呼出命令行：win+alt+T 编辑文档：nano text.cpp 编译程序：g++ text.cpp -o text.exe 运行程序：.\text.exe text.out 编译环境： ```cpp -O2 -Wl,--stack=114514 -std=c++14 -static ``` ##…

在文章《别样的 O(1) LCA》发表评论：

提供一种O(n)的排序方法：离散化后桶排

[P4170 [CQOI2007] 涂色](https://www.luogu.com.cn/problem/P4170) 如果一个区间左右端点颜色相同，那么可以用跨越整个区间的一次涂色解决，所以 $dp_{l,r} \gets dp_{1,r-1}$

[题目链接](https://hydro.ac/p/spoj-KPSUM) ### 题面 将 $1 \sim N (1\le N \le 10^{15})$ 写在纸上，然后在相邻的数字间交替插 ```+``` 和 ```-```，求最后的结果。 这道题的细节是十分多的，虽然代码并不长，但那是考虑所有情况后合并压缩的结果…

在讨论《建议升紫》回复：

@[what_can_I_do](luogu://user/658973)已反馈

RT

在讨论《警示后人》回复：

qpzc

题目链接：[P9180](https://www.luogu.com.cn/problem/P9180)。 ### 思路 初始思路：设 $dp_{i,l,r}$ 表示区间 $[l,r]$ 能否完成前 $i$ 个操作。 复杂度明显是螺旋炸飞的。 观察发现，dp 状态的第一维和存储的信息本质上是在描述一个东西，考虑将第一维…

[P9180](https://www.luogu.com.cn/problem/P9180) ### 思路 初始思路：设 $dp_{i,l,r}$ 表示区间 $[l,r]$ 能否完成前 $i$ 个操作。 复杂度明显是螺旋炸飞的。 观察发现，dp状态的第一维和存储的信息本质上是在描述一个东西，考虑将第一维放入dp数组存…

在讨论《只有开O2才过，否则TLE on #11》回复：

qpzc

[冰火战士](https://www.luogu.com.cn/problem/solution/P6619) 树状数组上二分，从左侧开始，每次枚举 $2^i$ 的长度，是否能往右跳，如果可以就另 $l=newl$，同时更新左右两侧累加的答案。 另外，当遇到这种“重一位”的问题时，可将其中一个数组离散化后整体向右移动一…

在讨论《警示后人》回复：

%%%

[等差子序列](https://www.luogu.com.cn/problem/P2757) 多个布尔值的判断可以用哈希维护 从前往后遍历，向值域数组里填数，$a_i$ 可以作为一个三元组的中项当且仅当存在 $k$，使得 $a_{i-k}$ 和 $a_{i+k}$ 种只有一个出现过，转化为权值数组上的回文判断问题，线…

在文章《题解：P11646 【MX-X8-T5】「TAOI-3」蓝宝石的存在证明》发表评论：

qpzc

https://www.luogu.com.cn/problem/P1450

RT