图论这一块内容比较多，而且题目涉及的 Trick 也很多，因此分若干篇。 本文略去所有算法本身性质的证明过程。 最短路 Dijkstra和SPFA \(\text{Dijkstra}\) 算法基于一个重要的性质：全局最小值不可能再被任何边更新。这样，在边权为非负数的最短路问题中显然满足，在存在负边时不满足。同时，保证了最多从每个节点处扩展 \(1\) 次，从而有了稳定的复杂度。 这也

状压DP做法 字符串长度不大，考虑刻画 \(T\) 的每一位。 设 \(f(i,S)\) 表示考虑了 \(T\) 的前 \(i\) 位，匹配了 \(S\) 内的字符串的方案数。 枚举下一位的字符，然后把能匹配上的字符集合设为 \(S_0\)，这样就能转移到 \(f(i+1,S \cap S_0)\)。 #include<bits/stdc++.h> using namespa

luogu8551 Bassline 题目的限制翻译过来就是 \([x,y]\) 中任意位置都被覆盖了相同次数。 用差分求出每个点被覆盖的次数，双指针求极长的满足条件的位置即可。 #include<bits/stdc++.h> using namespace std; #define int long long #define uint unsigned long long #

题意很复杂，我们要从中提取关键信息。 增加等级、嘲讽能力都是为了怼大佬服务，而怼大佬最多使用 \(2\) 次，我们尝试把这个操作单独拿出来，这样要考虑的就只剩下了还嘴和做水题。 考虑这样一个东西：由于我们保证自己不死，所以除了做水题回血之外，剩下的时间都可以空出来，在我们需要的时候手动添加具体操作。 设 \(f_{i,j}\) 为考虑前 \(i\) 天，空出来了 \(j\) 天，所剩下的最

注意到区间异或可以差分成端点异或，所以把序列差分了，并且能发现差分之后最多有 \(2k\) 个需要修改的位置。 又因为当一个序列的首项与差分序列确定时，这个序列也被唯一确定了，所以我们可以提取出那些需要修改的位置，压成一个整数 \(S\)，并且处理它们之间的距离。 反转长度为 \(b\) 的区间提供了两种在差分序列上的操作： 干掉 \(S\) 中距离为 \(b+1\) 的两个 \(

聊聊状态压缩。 顾名思义，就是把一个状态压成一个整数，从而使得问题的所有状态可以度量。 一般都是用二进制状态压缩来表示子集与全集的关系，对应着二进制每一位都是 \(0\) 或 \(1\)。更高的进制能表示更多的信息，但状态的数量也会随之增加，并且实现的时候要自己手写位运算，较为复杂，本文不会涉及。 信息的表示 luogu7076 [CSP-S2020] 动物园 题意比较绕。 一个 \

搜索剪枝 纯搜索剪枝题很少，早就融入各种搜索之中了。 但是在各种多项式时间的搜索里，剪枝仍然是重要的。 目前只有一道题，以后看情况加。 luogu1120 小木棍 能注意到长度一定是所有木棍总和的倍数，并且至少是 \(\max\{a_i\}\)，所以只对这部分搜索就行。 设dfs(cnt,len,lst)表示当前还剩下 \(cnt\) 根木棍要拼接，当前木棍剩余长度为 \(len\)

上古时期写的，那时候竟然还会期望…… 分析 是上一题的加强版。 由于每个台阶都多了若干出边，所以不能采用上题第一种状态了。 参考了洛谷第一篇题解的推式子方式。 设 \(E(x,y)\) 为线性生物从 \(x\) 爬到 \(y\) 的期望步数，\(\operatorname{deg}_x\) 表示 \(x\) 节点的入度，不包含 \((x-1 \rightarrow x)\)。 此时有

上古时代写的题解了。 分析 先不考虑美食节的影响。 考虑到节点数和边权都很小，不妨拆点。将每个点拆为 \(5\) 个点，其中第 \(5\) 个点是起始点，第 \(1\) 个点是终点。这样边权就变化为了经过的节点数。也就是说，到达节点 \(x\) 转化为到达 \(x\) 的第 \(5\) 个节点，而从 \(x\) 到达 \(y\) 权值为 \(z\)，转化为从 \(x\) 的第 \(6-z\

22 年某模拟赛。 本人也没有参加，为了造福大众就公开题面了。 反正也没什么人看这个博客。 会选择性略去一些部分分条件。 简单题 \(\text{Time Limit: 2 s}\) \(\text{Memory Limit: 256 MB}\) 给定 \(n,x,y\) 和 \(a,b,c,d\)，求有多少个长度为 \(n\) 的正整数序列 \(\{s\}\)，满足 \(\fo