在文章《CSP-J/S 2025 游寄（真寄了）》发表评论：

我都没看ST4

在文章《CSP-J/S 2025 游寄（真寄了）》发表评论：

不感谢我：（

# 用途 线段树是一种常用来维护**区间信息**的数据结构，可以在 $O(\log n)$ 内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 ~~总之很有用~~ # 基本结构 线段树将每个长度区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区…

这是一个介绍 ~绿卓航~ ST表的博客。 # 题目大意 给定 $n$ 个数, $m$ 次询问，每次给定一个区间 $[l,r]$ , 求最大值。 # 思路 ## 预处理 首先建一个二维数组 $f_{i,j}$ , 表示从第 $i$ 位开始的 ${2^i}$ 个数中的最大值。 按照定义, 可以得知 $f_{i,0}=a_i…

# Bellman–Ford ## 思路 在前一篇博客中，我们提到了松弛操作。 Bellman–Ford算法就是一种基于松弛操作的最短路算法。 Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。…

# 思路 先来看一张图：  首先将结点分成两个种点：已确定最短路长度蓝点的和未确定最短路长度的点集白点。一开始所有的点都属于白点。 然后重复这些操作：从白点中，选取一个最短路长度最小的结点，移到…

一道有意思的区间DP。 题目：http://sdfzoj.top/contest/341/problem/6 # 思路 首先因为开始要删掉一条边，所以要用破环成链的方法，在数组后复一个的数组。 ## 如何DP？ 开始可能会想到用 $f[i][j]$ 来表达第 $i$ 个点到第 $j$ 个点的最大数，但发现乘法不符合，两…

一道有意思的DP。 题目：http://sdfzoj.top/contest/343/problem/5 # 思路 首先可以发现，这个问题可以转化成求方案数的01背包。此时背包的容量就相当于 $\sum_{i = 1}^{n} a_i \div2$ ,每件物品的价值和体积都相当于 $a_i$。 其中 $f_i$ 表示和…

一道有意思的背包。 题目： http://sdfzoj.top/contest/343/problem/6 ## 思路 这道题在题面上与01背包完全一样，不同的只有数据范围。 直接按01背包做会超时，所以我们要考虑其他方案。 注意到 $n$ 和 $v_i$ 都比较小，所以可以从这方面考虑。 我们可以让 $f_i$ 表示…

# 多重背包 题目：http://sdfzoj.top/contest/343/problem/3 ## 思路 首先可以想到在二维01背包的基础上增加一个循环，用来枚举物品的个数，于是就有了这段代码 ```cpp for (int i = 1; i j) break; f[i][j] = max(f[i][j], f[…

今天做了一道有趣的题，记录一下。 # 思路 仔细想一想可以发现，这题可以开4个变量，每一个记录到当前字母的情况个数，最后再输出 $E$ 的情况个数就行啦。 注意字符串的长度不超过 $10^5$ ,要开 $int128$。 # 代码 ```cpp #include using namespace std; string…

在文章《CSP-JF模拟赛4T3-基础深搜》发表评论：

这是T3吧

```cpp #include using namespace std; int n,a,b,t[205],vis[205]; struct node{ int pos,cnt; }; queue q; void bfs(){ q.push(node{a,0}); vis[a] = 1; while(!q.empty(…

在文章《BFS基础T7-基础广搜》发表评论：

orz