题单
我也不知道为什么下划线一多 Latex 就要崩掉，我已经不想管了。
动态规划好题。
解法一（recommend)
定义 $F(i, j, k)$ $1$ 表示在 1 到 $i$ 的排列中，满足有 $j$ 对相邻的 $<i$ 的差为 $1$，$k = 1$ 或 $0$ 分别对应 $i$ 和 $i - 1$ 是否相邻的排列个数，易得 $F(1, 0, 0) = 1$，$F(2, 0, 1) = 2$。设当前已经处理完了前 $i$ 个排列的情况，我们考虑 $i + 1$ 放置的位置。
至此，我们已经分析完了所有的情况，最终的所求答案为 $F(n, 0, 0)$ ，时间复杂度 $O(n^2)$。
解法二 ❓
这玩意是有规律的，详见 OEIS - A002464 ，怎么推出来的等我去问问大佬。
我拿到大佬的答复了，但好像没有看太懂，我先放原话在这里。
AC code by CYR
总结
一开始做这道题的时候并没有想出来这道题是动态规划，我还以为是数学题，甚至都已经发现了前后两种状态之间的关系，若有很明显的关系，首先要考虑的就是动态规划或组合递推。
关于状态的设计，需要找到多个会影响的维度，大概就是以下几点：
- 前 $i$ 个元素所求得的答案。
- 会对后续内容产生影响的 $j$ 。
- 以及是否存在某些特殊情况会导致规律不适用的布尔值 $k$ 。
CSES-1077 Sliding Window Cost
题目大意
给定一个包含 $n$ 个整数的数组。你的任务是计算每个由 $k$ 个元素组成的窗口，从左到右，使所有元素相等的最小总成本。
你可以用成本为 $x$ 增加或减少每个元素，其中 $x$ 是新值和原始值之间的差值。总成本是这些成本的总和。
解题思路
是滑动窗口，我们定义两个集合 $lq$ 和 $rq$ 分别代表小于等于和大于中位数的元素，其中 $lq$ 的最后一个元素就是区间内的中位数。定义 $m$ 表示区间内第 $m$ 个数为中位数。
在进行窗口滑动时，考虑如何更新 $lq$ 和 $rq$：
- 若 $|lq| < m$ ，应当先在 $rq$ 中插入当前元素，接着将 $rq$ 中最小的元素转移到 $lq$ 中。
- 否则，应当在 $lq$ 中插入当前元素，接着嫁给你 $lq$ 中的最大元素转移到 $rq$ 中。
为了计算当当前区间的最小成本，我们定义：
- $ls$ 代表 $lq$ 中元素的总和。
- $rs$ 代表 $rq$ 中元素的总和。
- $med$ 代表中位数，也就是 $ls$ 中最大的元素。
那么可以得到区间最小总成本为：$(med\cdot lc - ls) + (rs - med\cdot rc)$ 。
AC code
总结
对于区间滑动窗口中位数问题，可以考虑建立两个集合，来进行求解。对于滑动窗口问题，set 是一个很好的选择。
定义 $F(i, j)$ 代表删除区间 $[i, j]$ 的方案数，考虑经典区间 DP，我们需找一中间点 $k$，其满足 $s[i] == s[k]$， 想要删除 $[i, j]$ 中的元素，就要先删除 $[i, k]$ 之间的元素，也就是要删除 $[i + 1, k - 1]$ 的元素，因为有两个环节，故应使用乘法原理，状态转移方程如下：
$$F(i, j) = F(i + 1, k - 1) \times F(k + 1, j) \times \binom{\frac{j - i + 1}2}{\frac{k - i + 1}2}$$
由于删除 $k$ 左右的元素是有序的，故乘上 $\binom{\frac{j - i + 1}2}{\frac{k - i + 1}2}$ 。
首先考虑无解的情况，记 $N = \sum_{1}^{n}$，易得若 $2|n$ 则一定有解。
这 $n$ 个数的和为 $\frac{n(n +1)}{2}$ ，那么每一部分的的和为 $\frac{n(n +1)}{4}$，题目中 $n$ 的范围较小， 这暗示了用 01 背包来解决问题。
我们令 $\texttt{dp}{[i][j]}$ 代表在前 $1-i$ 个数中，组成和为 $j$ 的数量，可以得到转移方程为 $\texttt{dp}{[i][j]} = \texttt{dp}{[i-1][j]} + \texttt{dp}[i-1][j - i]$，增添或者不增添的情况。
AC code
定义 $F(i, j)$ 代表 $[i, j]$ 中先手的最大值，$S(a, b)$ 代表区间$[a, b]$ 的元素和。
有 $F(i, i) = X_i, F(i, j) = \max(S(i + 1, j) - F(i + 1, j)+ X_i, S(i, j - 1) - F(i, j - 1) + X_j)$ 。
以上式子代表了先手的两种决策，分别是选左端或右端，接着减去对手（由于对手在上一轮算作先手，所以依然是 $F$ 数组）在剩余区间的最大得分。
无关
我隐约记得还有一道题类似于这种从两端开始取，但是那道题我是记录上一次取的是左侧还是右侧。
总结
取数游戏，经典的区间 DP，常规做法就是拿 DP 数组记录左右端点。
AC code
由于天数很大， 所以考虑离散化。
令 $dp_i = 在第 i天之前我们可以赚到的最大金额$，若现有一任务 $i$，其开始时间为 $l_i$，结束时间为 $r_i$，所获得的奖金为 $v_i$。第 $i - 1$ 天所赚的钱会迁移到第 $i$ 天，则 $dpi = dp{i - 1}$。
则状态转移方程为：$dp_i = \max{dp_l{j} + v{j},dp_i}$ ，其中 $r_j$ 应等于 $i$。
总结：数值过大的可以考虑离散化，这一类某段时间单个问题可以考虑差分数组解决。
这道题很明显用 BFS，问题在于迷宫中出现了怪物，我们的勇士不能和怪物接触，转换一下就是，勇士不能到达怪物可能所在的区域。
在转换一下，怪物永远比勇士先走一步，勇士不能走到怪物所走过的面积，考虑把怪物和勇士在一起进行 BFS，将怪物先入队，这保证了怪物总是比勇士先走。
注意：不要忘记特判边界条件！
总结：调试优先检查边界条件，做题时可以考虑不同的入队顺序达到所需要的结果
AC code
双向最短路和大数判断相等操作，
若一个点 $i$ 一定处于 $1$ 到 $n$ 的最短路上，那么：
- $dis(1, i) + dis(i, n) = dis(1,n)$。
- $way(1,i)\times way(i, n) = way(i ,n)$ 。
其中我们定义 $dis(u, v)$ 代表节点 $u$ 致节点 $v$ 的最短距离， $way(u, v)$ 代表节点 $u$ 到 $v$ 的最短路数量。
考虑令起点分别为 $1$ 和 $n$ ，跑两次 Dijkstra，接着就能解决以上的判断。但是会有一个问题，最短路的数量可能会超过 long long 所承受的，又因为此不要求输出最终的数值，只需要判断是否相等，我们可以挑选两个大质数，分别对两个数组进行操作，若最后结果相同的概率是非常小的。
这种方法是用于判断大数是否相同的常用套路，我们应当积累常用质数：
- 998244353、1e9 + 7、1e8 + 7、1e9 + 9
由于这道题卡 9982444353 不能用。
AC code
一道非常好的搜索题
朴素算法
我们简单的使用回溯法进行爆搜，并计算这样的路径数量。
运行时间：483s
递归调用次数：760亿
优化1
如果在访问了所有的方格前就到达了终点，又或者是步数已经达到了指定步数却还没有到。满足任意一个就可以退出搜索。
运行时间：119s
递归调用次数：200亿
优化2
如果碰到了方格边缘，则会把整个地图分成两个部分，若其中包含还未访问过的方格，则一定无解，退出递归即可。
运行时间：1.8s
递归调用次数：2.21亿
优化3
考虑对优化 2 进行拓展，若在搜索时无法继续前进，需要向左或者向右转，网格就会分成两个部分，若两者中包含未被访问过的方格。很明显，此时一定无解。
运行时间：0.6s
递归调用次数：6900万
经过了优化三的优化之后，我们已经可以通过本题，为了达到优化三，我们需要提前将方格的边缘包围起来，俗话说就是将边缘的 vis 数组标记为 true 。
In backtracking, the search tree is usually large and even simple observations can effectively prune the search. Especially useful are optimizations that occur during the first steps of the algorithm, i.e., at the top of the search tree.
在进行回溯算法时，搜索树通常会非常庞大，即使是进行简单的观察也能有效的剪枝。尤其是在回溯算法的前几步非常有效果，也就是搜索树的顶端。
——USACO Guide
AC code
互相有先后关系，连边跑拓扑排序的经典问题，本质上属于贪心。
注意：
- 需要注意边与边之间的方向，注意输出的方式，可以考虑通过优先队列来维护
AC code
图论
考虑在进行 DFS 生成树时直接贪心构造。
错：
- 在进行度数修改时把复杂操作直接过于简单化，直接将度数的标记直接规 0，并没有考虑多个儿子对答案造成的影响。
总结：
-
图论题可以先去一般化，先转换成树上问题，菊花图，链条来分析题目。
-
边处理边操作，贪心局部解转化为全部解，对于还需要判断有没有解决方案的问题，往往可以从局部到全局，若局部合法但是全局不合法，那么就是无解的。所以说在考虑贪心的时候往往不需要太在意无解的情况，自然而然的就能冒出来无解的情况。
-
但是这并不代表我们不分析无解情况，往往无解的情况会是一些题目的突破口可以帮助我们解题，但不应该被无解情况限制了思路，从而不敢考虑贪心
AC code
插头 DP 入门模板题。 插头 DP 入门引子题目。
考虑使用记忆化搜索，由于状态十分的多，考虑使用状态压缩。
对于每一列，由于它的长度最长为 10，考虑使用 long long 来储存每一种状态，若第 $i$ 位为 1 则代表 $i$ 这个位置上有砖块，反之亦然。
直接进行记忆化搜索很明显太慢了，对于一个状态，下一个可能的状态可能有非常多种，考虑预处理出每一个状态的下一个状态。
预处理时考虑在当前空位能不能竖着放和能不能横着放，如果可以横着放，则需要在下一行中替换为 1，如果可以竖着放，则在下一行无需在意，它依然是空的。参考资料里面有图，看完一下就理解了，至少我是这样子的。
时间复杂度 $O(我不知道)$。
AC code(带注释)
首先不考虑题目中的限制条件，方案数应该为：$k^n$，那么如果只缺了一个数字呢？如果缺了一个数字所构成的方案为：$(k - 1)^n \times \binom 1k$ 。
如何理解？乘号左边代表的剩下的 $k - 1$ 个数字填入 $n$ 个空位的方案数，而乘号右边则代表着，从 $k$ 个数字中挑选 1 个所需要的方案数。
我们类比，如果缺了 $i$ 个数字，构成的方案数为$(k - i)^n \times \binom ik$ ，但是呢，由于一定缺少一个数字的情况，已经包含了一定缺少两个数字的情况，所以说我们要用容斥原理。
最终的答案为：
$$k^n - \sum_{i = 1}^{k - 1} (k - i)^n \times\binom ik$$
总结：对于方案数问题可以优先考虑容斥原理；并从没有限制往有限制进行思考。
AC code
考虑序序列 A 是单调递增，将 B 从小到大排序。我们可以推出以下结论：
- $A_0 + A_1 = B_0$
- $A_0 + A_2 = B_1$
那么我们可以得到：
考虑 $A_1 + A_2$ ，它的值一定是 $B_i,i \in [2, n]$，这个说明了， $A_0$ 只有 $n - 2$ 种可能。
我们可以得到：$A_1 = \frac{B_i - B_1 + B_0}{2}$ ，$A_0 = \frac{B_1 + B_0 - B_i}2$，那么我们就可以便利每一个 $A_0$ 然后判断它能不能使 B 成立，如何测试？
对于每一轮测试，$Ai$ 就等于 $B{\min} - A_i$，之后从 B 中判断 $A_j + A_i(j < i)$ 是否在 B 中并删除。
AC code
俗话说“正难则反”，因为直接求合法的情况很明显非常难，所以考虑反着来。我们将一个字符串分成若干个区间，使得每个区间里面的字母都相同。
将所有的字母分成 $x$ 个区间的方案数为 $A(x)$，则对于初始字符串全部重新排列的情况数为 $A(n)$，一定有两个相邻字符重复的数目就是 $A(n - 1)$，此时一定有一个长度为 2 的区间中字母相同，剩余的 $n - 1$ 个区间任意排列
相似的，一定有 $i$ 个字母连续相同的数目是 $A(n - i)$，因为 $A(n)$ 中已经包含了 $A(n - 1)$ 的情况，而 $A(n - 1)$ 中，同样也包含了 $A(n - 2)$ 的情况，所以说考虑容斥原理，最终的答案为:
$$\sum_{i = 0}^{n} A(n - i) \times(-1)^n$$
但是该如何计算 $A(x)$ 呢？定义 $D(i, j)$ 代表前 $i$ 种字符，分成 $j$ 个区间的方案数，那么 $A(n) = D(26,n)$，显然 $D(0, 0) = 1$，记第 $i$ 种字符出现的次数为 $c$，显然当 $c = 0$ 时，$D(i, j) = D(i - 1, j)$。否则，这 $c$ 个字符就要分成 $k \in [1, c]$，个部分和已有的 $j$ 个区间混合，可以得到：
$$D(i, j + k) \gets D(i - 1,j)\cdot \binom {j+k}{k}\cdot \binom{c - 1}{k - 1} $$
如何理解以上的式子呢？其中 $\binom {j+k}{k}$，表示将 $k$ 个区间插入原来的 $j$ 个区间中，就是在 $j + k$ 个区间中选择 $k$ 个，而 $\binom{c - 1}{k - 1}$ 可以通过插板法理解，其代表着从 c 个字符里面划分 k 个区间的方案数。
总结：
- 对于正着求比较困难的组合数学题目，可以考虑反着求解。
- 对于题目性质进行分析，构造出现不同情况的概率，并考虑容斥
- 找到当前步骤和上一步骤的关系，进行递推。
AC code
某位高人曾经说过：对于找充要条件的题目，那就把它所有的必要条件全部列出来。
那么我们就考虑列出充分条件，经过大量的演算算我们发现：
- 如果堆 1 的重量大于堆 2 的重量，那么 $\forall i \in [1,n]$ ，定义 $l_i$ 表示堆 1 编号大于 $i$ 的砝码数，$r_i$ 代表堆 2 编号大于 $i$ 的砝码数，都有 $l_i > r_i$。
对于堆 2 同理，问题就转化成了求解能否在某一时刻，堆 1 、堆 2 都能满足以上条件。
可以通过记录前缀和来快速判断条件是否成立：
- 若最小值不小于 0，则堆 1 一定重于堆 2
- 最大值不大于 0，则堆 2 一定重于堆 1
- 若以上条件均不满足，返回你寄了
可以考虑通过线段树进行区间最大最小值维护，其他数据结构应该也可以，但是我太菜了不会。
时间复杂度 $O(n \log n)$ ，应该没有错吧。
AC code
普通的枚举时间复杂度 $O(n^2)$ 会超时，考虑用贪心优化。
将每个人按照 $x - y$ 递减排序，考虑维护两个数组 $suf[i]$ 和 $pre[i]$，分别表示后 $i$ 个人进行的贡献和前 $i$ 个人进行的贡献。枚举时就考虑 $pre[i] + suf[i + 1]$，好像可以称作中途相遇？
[CSP-S 2021] 廊桥分配 也是一道类似的题目，把每一种可能情况枚举出来，接着通过中途相遇来做。
总结:
AC code
构造神题，依然是经典的反着来，我们先考虑正着推，记 $x$ 和 $y$ 分别代表以 0 结尾和以 1 结尾的子序列个数，如果接下来又是 0，则 $ x = x + y + 1$，如果下一位是 1 那么 $y = x + y + 1$。
由于 $x + y = n$ ，我们可以依次枚举 $x$ 和 $y$，然后反推出对应的 01 串，有点类似于辗转相除法。
均摊时间复杂度 $O(n\log n)$
AC code
定义 $si$ 代表 $\sum{i=1}^{n} a_i$ ，若 $N|s_i$ ，则输出 $a_j,\forall j[1,i]$ 即可。
若 $s_i\equiv s_j\mod{N}(i<j)$ ，则输出 $a_k,\forall k\in[i,j]$ 即可
考虑使用区间 DP 完成问题。
记忆化搜索。
解题思路
定义 $DP[i][j]$ 代表在区间 $i$ 到 $j$ 中屌丝值最小的解，显然最终答案为 $DP[1][n]$。
对于一个区间 $[l, r]$ ，枚举 $a_l$ 放在第 $k$ 位，对应到原序列上的下标为 $m$，$al$ 对答案产生的贡献为 $(k -1) \times l$。由于栈的特性，第 $[l + 1, m - 1]$ 个元素必须在 $m$ 之前弹出，造成的贡献为 $DP[l + 1][m - 1]$。剩下的 $[m, r]$ 个人造成的贡献为 $k\times \sum{i = m}^r a_i + DP[m][r]$。
总结
没有想出来的原因：
- 最开始把 DP 的类型都想错了，以为此题是线性 DP，后来觉得不对劲改成了区间 DP，但因为对栈的一些特性了解的不熟就挂了。
区间 DP 的特征：
-
涉及到区间变换。
-
一个序列的区间可以由子区间变化而来。
而且值得注意的是：当一个数字被弹出时，则它之前的序列必须已经被弹出了，但是什么时候入栈什么时候弹出都是不确定的。
AC code