A 略。 #include<bits/stdc++.h> using namespace std; #define ll long long #define uint unsigned long long #define PII pair<int,int> #define MP make_pair #define fi fi…

$\text{Solution}$ 在 7 月 20 日写下这篇有纪念意义题解。 初读不知题面意，再读早已成素批。 何时一个区间可以被重排为回文串？ 所有字母成对出现。 在上一种情况的基础上添加一个字母。 因为要考虑每一个子区间，所以不能直接计算，必须差分掉。 如何差分？不难发现我们只考虑每个字母出现次数的奇偶性，同时字母只有26个，所以可以用一个…

先放题，有时间再整理。 其实也就那回事，理解了思想之后就没啥特殊性了。 luogu6647 [CCC2019] Tourism 不难发现 $t =\lceil \frac{n}{k} \rceil$，然而并没有什么用，我们只要在转移时对取值区间进行限制即可。 具体地，第 $i$ 天的取值左端点是 $L_i = \max(0,i-k)$，右端点是 $…

区间形态的扩展 luogu3205 [HNOI2010] 合唱队 队列的形成方式是不断往左或往右扩展。 考虑区间 DP。发现对于一个区间 $[i,j]$，最后一个元素的来源会对转移产生影响，所以设 $f(i,j,0/1)$ 为考虑区间 $[i,j]$，其中最后一个元素是从左边还是右边加入的方案数。 转移很简单$$f(i,j,0) = [a_i &l…

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

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

树形 DP 计数。 luogu8867 建造军营 对于图中一条非割边，看守与否都相同，因此可以用 Tarjan 算法求出边双再缩点，把非树边单独拿出来，讨论每一条树边。 然而貌似不是很好做，子树外是否建造会影响子树内。考虑设 $f_x$ 为军营只在以 $x$ 为根的子树中出现，且至少存在 $1$ 个军营的方案数。 转移时对于边 $(x,y)$，如果…