在讨论《洛谷 2025 年鉴》回复：

qp

## 思维 + 问题转化 + 结合贪心思想的二分优化求最长不下降子序列 + 记录方案 在一张巨大的网格上，只能向右和向下移动，要求从起始位置移动到终点时最多能途径的物品数，考虑到一步关键转化 trick：将这些物品按照 $x$ 为第一关键字升序排序，$y$ 为第二关键字升序排序，那么途径能获得的最多物品数就是对这物品的…

## 性质挖掘 + 前缀和 + 贪心 + STL set + STL 二分查找 首先要能手玩样例发现出一个**性质**：对于区间 $[l,r]$，若区间长度为偶数，区间 $[l,r]$ 内的数的位置奇偶互换；若为奇数，区间 $(l,r]$ 内的数的位置奇偶互换。 由于考虑区间长度为奇数时等价于修改一个区间 $(l,r]…

在讨论《求助，不会写本题滚动数组优化一维空间后的 DP 写法》回复：

@[Diaоsi](luogu://user/137242) 这个我知道呀，一般的滚动数组优化 DP 都挺好写的，可能是之前没遇到过这种相对棘手的吧，这题自己已经想了一上午了也没搞明白，佬麻烦看看我这个帖子的新补充T.T

在讨论《求助，不会写本题滚动数组优化一维空间后的 DP 写法》回复：

可能我比较不理解的地方是，当 $f_{i,j}$ 从 $f_{i-1,j}$ 转移而来的时候，说明第 $i$ 层放的是绿砖，这时候你要保证转移合法你必须要保证绿转的数量够用，所以应该加个判定吧，但是为何题解中见到的 DP 转移中没有加判定呢？ 同理，当 $f_{i,j}$ 从 $f_{i-1,j-i}$ 转移而来的时候…

在讨论《求助，不会写本题滚动数组优化一维空间后的 DP 写法》回复：

我试着在自己代码的基础上滚动数组优化，我试着写了两个滚动数组优化后的代码版本，但是都没过样例。 ### 试写版本1 ```cpp #include using namespace std; #define rep(x,y,z) for(int x=y;x =z;x--) typedef long long LL; co…

在讨论《求助，不会写本题滚动数组优化一维空间后的 DP 写法》回复：

上述未写滚动数组优化的二维空间 DP 代码，过了 CF 前六个 test，在第七个 test 超时了，因为自己 DP 空间分配开小了，说明代码整体是没问题的吧，但是将第一维 DP 数组空间优化并不理解。

```cpp // Problem: D. Red-Green Towers // Contest: Codeforces - Codeforces Round 273 (Div. 2) // URL: https://codeforces.com/contest/478/problem/D // Memory Lim…

## 推式子 + 求解线性方程组 根据题意，由于$\{b\}$ 序列共有 $n$ 项且对于每个 $b_i$ 都可以用含 $a_{1 \sim n}$ 的式子来表示，即有 $n$ 个线性方程以及 $n$ 个未知量 $a_{1 \sim n}$，显然容易想到联立线性方程求解。 对于这种问题我们应该如何考虑呢？首先光瞪眼肯定…

## STL set + 简单数学计算 本题貌似没什么难点？ 本题貌似没什么难点？ 根据样例意识到其实对于大桌和小桌玩的次数是需要自己计算出来的，这算是需要解线性方程了吗？考虑 exgcd？ 其实不需要，因为大桌和小桌的容纳人数有很明显的关系，显然可以利用取余关系解决，根据题意大桌容纳 $\lceil \dfrac{n…

## 数据结构：静态区间修改(差分+前缀和) + STL set 由于给定的 $\{a\}$ 是排列，要使得最终的序列单调递增，必然最终序列为 $a_i=i$。 那么考虑若当前的位置 $i$ 使得 $i \ne a_i$，就意味着这个 $a_i$ 应该从 $i$ 移动到 $a_i$ 处。 意味着要满足 $\forall…

## 异或前缀和 + 性质挖掘 + 递归 设 $s$ 数组为 $a$ 数组的异或前缀和，即 $s_i=\oplus_{k=1}^i a_k$。 显然当 $m \le n$ 时直接输出 $a_i$ 即可。所以本题难点自然是在于 $m \gt n$ 的部分如何求。 由题意当 $m \gt n$ 时，$\large a_m=…

## 图上 DP + 二分答案 根据本题题意，通道为单向边且每条从点 $s_i$ 移动到点 $t_i$ 的通道满足 $s_i \lt t_i$。 根据这些条件可以确定本题的图是一张 DAG 图，呈现拓扑序，因而我们可以使用图上 DP 来做。 首先本题只需要关注电池数量，电池当前状态是否为充满电的条件其实根本没用，因为每…

## 单调队列 我们先用 map 统计出每个数出现的次数，接着将 $a$ 数组排序并去重，维护一个大小不超过 $k$ 的相邻元素差值为 $1$ 的单调队列即可。 ```cpp const int N=2e5+5; int n,k; int a[N]; int q[N]; void solve(){ cin>>n>>k;…

## 转化为奇偶判定 + Lucas 定理 首先不难发现 $f_{i,j}$ 的取值只可能是 $0$ 或 $k$，不妨把 $k$ 看作 $1$。那么通过 $f_{i,j}$ 的奇偶性即可确定 $f_{i,j}$ 的值。 由于异或的本质为二进制下的不进位加法，故可以把 $f_{i,j}=f_{i-1,j-1} \oplu…

在讨论《假如说谎的人一定说假话该怎么做呢？》回复：

RT，若题意改成：每个人要么诚实，要么说谎，诚实的人总是说真话，**说谎的人总是说假话**，没有两个说谎的人站在一起。 本题该怎么做呢？

RT

在文章《题解：CF2039C2 Shohag Loves XOR (Hard Version)》发表评论：

guessforces%%%

## 数论 + 贪心构造 设最终的答案数组为 $b$。 手玩一下数据： 当 $i=1$ 时，显然对于任意的 $j \ (j \gt i)$ 都满足 $\gcd(i,j)=1$，那么要保证 $b_1 \ne \gcd(b_1,b_j)$，即保证 $\forall j \in [2,n] , b_1 \nmid b_j$。…

对于根从 $u$ 移到 $v$，耗费的价值为：$u$ 到 $v$ 的简单路径中经过的边数 $\times c$。 故用 $dist_u$ 记录结点 $u$ 到原根（即结点 $1$）的距离。 那么考虑对于每个结点作为根时，根节点到子节点的最远距离怎么确定？树的直径即可。 ```cpp #define rep(x,y,z)…

在文章《题解：CF1846G Rudolf and CodeVid-23》发表评论：

写的挺好的，不过有的地方要纠正一下：“原先得的病，和无法治好的病取个并” 应改为 “原先得的病，和无法治好的病取个交”。

## 后缀处理 + 字符串模拟 简单题，维护 $ne$ 数组，用 $ne_i$ 记录 $i$ 位置作为左端点最右能扩展到的位置。 显然 $[i,ne_i]$ 这段区间的子串是一个连续非递减子串，当该区间长度等于 $1$ 时，符合题意好串的定义；当该区间长度大于 $1$ 时，显然我们有办法将这个区间拆分成两部分，使得两部…

## 字符串哈希 + 二分 + 贪心 第一步贪心：考虑到可以删去某一段子串，且对于一段长度 $k$，若满足 $s_{1 \sim k} = s_{n-k+1 \sim n}$，即初始时前后缀已经存在一个长度为 $k$ 的回文前后缀，那么这一段保留一定不会更劣。这个过程可以用双指针维护。注意特判当不存在满足 $k \in…

## 记忆化搜索 + 图论建模 由于每次操作后是对序列的末尾插入 $0$，显然后面插入的这些 $0$ 对应的位置 $i$ 一定不满足 $a_i = |a| + 1 -i$ 这个式子，所以后面插入的这些 $0$ 对应的下标 $i$ 完全不需要纳入考虑范围。 也就是说我们只需要考虑一开始数组中存在的下标 $i \in [1…

## 字符串哈希 + 暴力枚举所有区间 + STL 维护所有可能右端点 考虑将输入的字符串 $s$ 每一位取反得到字符串 $t$。 显然若区间为 $[a,b]$ 的子串 和 区间为 $[c,d]$ 的子串满足题意条件，则 $t_{a \sim b} = s_{c \sim d}$。 由于一个“外形”相同的子串可以对应多…

## 二进制拆位 + 贡献计算 + 快写输出 int128 原式： $$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j) \times (j - i) $$ 等价于： $$ \sum\limits_{k=0}^{20} \Bigg( 2^k \times \sum\li…

## 单调队列优化 DP + 贪心 本题实际上就是给定若干条线段，要求在每个给出的线段中都至少要放一个点，求最后最小总代价是多少。 如果本题每个位置建立基站的权值都相同，则为经典贪心问题中的区间选点问题。 但本题每个位置建立基站的权值可以不同，于是不能直接按区间选点问题来处理，但是依然可以借助贪心思想。 考虑贪心：对于…

## 思维 + 贪心 题意即每次操作可以选择一个位置，将这个位置的数拆分成两个正整数，显然拆分后的每个数只会比拆分前的数更小。 由于拆分后的数会变得更小，同时我们需要保证最终数列变为单调不降。显然从前往后正序遍历数组将无法保证当前位置拆分后是否满足整个序列单调不降，因此我们考虑贪心地从后往前倒序做，对于每次枚举到的位置…

## 树形DP 由于本题的树是一颗有根树，在构建完这颗以 $1$ 为根的树后不难发现：一个点 $u$ 的父边与这个点 $u$ 的父结点 $father_u$ 的父边之间显然存在顺序关系（因为在有根树中，一个点的父节点是唯一确定的）。 具体地说，如果点 $u$ 的父边对应的编号大于点 $father_u$ 的父边编号，则…

## 找规律 + 模拟 先考虑问题的简化版：若给定的字符串只含字符 `0` 和 `1` 而无字符 `?` 的干扰时该怎么做。 根据滑动窗口的思想，模拟一下不难发现若有解则一定满足 $\forall i \in [1,n],s_i=s_{i \bmod k}$，即字符串一定存在一个长度为 $k$ 的循环节。 所以我们只需…