题意给出$n$个数，从中选出一些，求选出的数能分成相等的两份的方案数数据范围：$2 \le n \le 20$题解对于每个元素，无非$3$种状态：$0$ 不选$-1$ 左$1$ 右但直接搜索复杂度达到$O(3^n)$考虑折半搜索将组合二进制压缩，前半搜索记录下可能的$sum$，后半搜索从前半中找到相等的$sum$（其实是找$-sum$，但是是等价的），则此种选择方案成立由于$sum$较大，需...

题意给出小写字母组成的字串，要求增删字母使其变为回文串，增删不同字母的花费不同，求最小花费数据范围：$1 \le L \le 2000$题解用$f[i][j]$表示将区间$[i,j]$修改为回文串的最小花费，显然有$$f[i][i]=0$$当$s[i]=s[i+1]$时有$$f[i][i+1]=0$$因为要从小区间转移到大区间，$f[i][j]$可以从$f[i+1][j]$或$f[i][j-...

题意：司令部的将军们打算在 $N \times M$ 的网格地图上部署他们的炮兵部队。一个 $N \times M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署...

题意从数列$a$中选出若干数，但不能有超过$k$个连续的数字被选择，求选出数字的最大和数据范围：$1 \le n \le 10^5,1 \le a_i \le 10^9$题解用$f[i]$表示选到第$i$个时的最大值，显然，在$j \in [i-k,i]$一定存在至少$1$个断点，否则存在超过$k$的连续段，所以枚举该断点$$f[i]=max(f[j-1]+a[j+1]+ \dots +a[...

题意求$c=\frac{a}{b} \bmod 19260817$的值数据范围：$0 \le a,b \le 10^{10001}$题解$$ \begin{aligned} \frac{a}{b} &= a \cdot b^{-1} \\ & \equiv (a \bmod p) \cdot (b^{-1} \bmod p) \end{aligned} $$转化为$a \ti...

题意：求基环树最大带权独立集。数据范围： $N \le 1000000$题解：算法：树形dp分析题意：由“每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己）”建立有向图，将每个人 $x$ 最厌恶的人 $y$ 记为其父节点 $fa[x]=y$ ，可得每个节点有且仅有一条出边，且无自环。由于共有 $N$ 条边，所以该图为基环树。考虑到基环树的性质，删边后必定构成一棵树。分别以删去的边连接的...

题意对于一个$01$序列，有$5$种操作：$0 \ a \ b$ 把$[a,b]$区间内的所有数全变成$0$$1 \ a \ b$ 把$[a,b]$区间内的所有数全变成$1$$2 \ a \ b$ 把$[a,b]$区间内的所有数全部取反$3 \ a \ b$ 询问$[a,b]$区间内总共有多少个$1$$4 \ a \ b$ 询问$[a,b]$区间内最多有多少个连续的$1$对于每个询问，输出答...