在讨论《洛谷管理组春节休假安排 (2026)》回复：

qp

**解题思路** --- 通过观察 $N$ 的数据范围，我们不难想到状压 dp。 首先我们来考虑 dp 状态。首先，我们需要一维代表的是那些数字被选了，然后因为我们需要考虑目前状态下的尾巴上的那一个数放的是什么（因为我们要放一位进去，我们要考虑这一位和当前状态下的最后一位的关系）。所以我们需要两维，$f_{i,j}$，…

直接 dfs，然后每次跑到顶点 n 的时候纪录一下答案即可。 具体看代码 ```cpp #include using namespace std; #define pb push_back #define pf push_front #define m_p make_pair #define str string #d…

**解题思路** --- 不难发现，当我们处理横坐标查询的时候，我们只需要考虑当前，有多少个在这一行中的垃圾的纵坐标被占用了，处理纵坐标则反之。 知道这个就好做了，我们可以纪录当前有多少个横坐标以及纵坐标被记录了。然后，每次查询，遍历当前行/列的所有垃圾，判断此垃圾的列/行是否被占用即可。 复杂度 $O(n)$ **代…

请求修改时限。SPOJ和DMOJ都过了，但你谷过不去

**解题思路** --- 不难发现，我们其实只要考虑 $S$ 的排列方式，答案就是这个数的 $l$ 次方。那如何去求 $S$ 中的排列方式呢？ 我们可以从后往前算，不难发现，在 $S$ 中最后一个 M 的可选 O，就是 $n-p$ 个（这里假设最后一个 M 的位置就是 $p$），从这里往前推，那倒数第二个 M 的可选…

在文章《OI 重开模拟器》发表评论：

%%%%%%%

**题目意思** --- 给你一个数组 $A_1,\dots,A_n$。 求一对整数 $(i,j)$ 的以下三个值的最大和： $(A_1, A_2, \ldots, A_i)$ 中的不同整数计数， $(A_{i+1},A_{i+2},\ldots,A_j)$ 中的不同整数计数， $(A_{j+1},A_{j+2},\l…

在讨论《洛谷网校正式进驻小红书了！》回复：

恭喜！

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

支持

**解题思路** --- 观察第一个样例可以发现一种构造如下。 $$1,\dots,n-2,1,1$$ 有 $2\times(n-2)$ 个最大回文串，即 $g(a)=2\times(n-2)$。 满足题目条件。 构造 Tips: 如果要求构造的是子序列的回文时，尽量要让最大回文的数量尽可能小。 **代码** ```c…

**解题思路** --- 若 $p_i$ 和 $p_j$ 连边了，则 $p_i$ 要排在 $p_j$ 的前面，以及 $p_i p_j$，第二种是 $p_i > n; for (int i = 1; i > s[i]; s[i] = '$' + s[i]; in[i] = 0; } std::vector e[Maxn]…

**解题思路** --- 设每一行每一列和的值为 $x$，则 $nx=mx$，若 $n=m$，则 $x$ 有无数个解，否则，$x=0$。 由于题目要求输出任何一个即可，所以我们不妨令 $x=0$。 知道这个后我们就可以直接按照路径更新，更新的时候判断如果下一个是 D，则我们就用行来更新，否则就用列。（因为如果下面一个是…

**解题思路** --- 不难发现，我们如果要知道 $i$ 和 $j$ 有没有连边，其实等价于 |$i$ 到 $j$ 的路径不包含 $i$ 直接到 $j$ 的路径| 的奇偶是否与 $c_{i,j}$ 相等。 知道这个后，我们就可以直接枚举在 $i$ 到 $j$ 的路径中的第一个点（不包含 $i$），令其为 $t$，则…

**解题思路** --- 首先，看到数据范围不难想到区间 dp. 令 $g_{i,j}$ 代表让区间 ${a_i,a_{i+1},\dots,a_j}$ 变成 ${1,2,\dots,j-i+1}$，则 $g_{i,j}$ 可用 $O(n^3)$ 暴力求出。 在设 $f_{i,k}$ 代表目前考虑到 $i$，有 $k$…

**解题思路** --- 分两种情况讨论。 1. 存在一个元素不等于 $-1$ 或 $1$ 的情况。 2. 所有元素都等于 $-1$ 或 $1$。 先来讨论第二种情况，由[介值定理](https://baike.baidu.com/item/%E4%BB%8B%E5%80%BC%E5%AE%9A%E7%90%86/10…

**解题思路** --- 考虑贪心，每个保留的树要发挥最大作用，即为每个保留的树在尽可能多的区间。 则我们可以讲每个区间按照右端点排序，则如果要让每个被保留的树有最大的贡献，即使让这颗树的位置尽量往后排，这样被后面的区间包含的可能更大。 用一个树状数组维护一下每棵树的状态即可。 **代码** --- ```C++ st…

**解题思路** --- 不难发现，Elsie 选择的蛋糕为 $[1,i]$ 和 $[n,n+i-\frac{n-1} 2]$ 这两个区间。（不考虑 Bessie 的操作） 则如果 Bessie 在这两个区间内合并，则此操作只会让 Elsie 最终吃掉的蛋糕更多，因为合并一下等价于 Elsie 两次操作。 则 Bess…

**解题思路** --- 考虑如何取到最大值，不难发现，取到最大值等价为每个数有最大贡献。下面分别考虑 $1,\dots,n$ 的贡献。 若数字 $i\ (1\le i \le n)$ 在一个集合有贡献，则此集合只能包含大于等于 $i$ 的数，由此可以推出：要让 $i$ 最大贡献，则 $n,n-1,\dots,i$ 必…

**解题思路** 枚举第一位，后面 dfs 的时候每次从比前一位大 $10$ 的位置开始枚举，上界为 $m$。 具体细节看代码注释。 **代码** --- ```cpp int n,m; int loc=0; vector ans[Maxn]; vector v; inline void sve(){ ans[++lo…

### 解题思路 --- 不难发现一个结论：每头奶牛领头的时间为一段连续的时间。（具体证明见楼上） 从这里可以推出，每头牛领头的时候，最优方案是直接让他~~凉~~。因为一头牛对车队的贡献为其在领头的时候，若其在领头之后每~~凉~~，则其在后面的时间只能跟着跑（由上述结论推出其不可能在一次领头），对车队无贡献。换句话说，…

在讨论《今年CSP考kmp的概率大吗？》回复：

@[microchip](/user/241838) oo orz

在讨论《今年CSP考kmp的概率大吗？》回复：

@[wzj0829](/user/1028403) 哦噢 好的 谢谢dalao

在讨论《今年CSP考kmp的概率大吗？》回复：

@[heyx0201](/user/768951) s

今年CSP考kmp的概率大吗？

在讨论《noilinux中vscode有自动补全吗？》回复：

@[pigeonteam](/user/1042306) 哦哦 好的 谢谢dalao

在讨论《noilinux中vscode有自动补全吗？》回复：

@[ZnPdCo](/user/560700) 哦哦好的 谢谢大佬

NOI linux 中vscode有自动补全吗？

在讨论《【注意第二轮缴费】CSP-J/S 2024 第一轮信息收集汇总》回复：

RP++

在讨论《如何训练这种题》回复：

@[qi__](/user/758896) 好的喵，谢谢大佬