先处理函数 $f_i$，有 $f_i = \sum \limits _{j = i - m}^{i - 1} f_j$，这个递推式显然可以通过矩阵乘法进行优化。设 $F_i$ 表示通过递推函数 $f_i$ 得到的矩阵，则有以下矩阵的递推（以 $m ...

有一个显然的贪心结论，就是先完成任务截止时间考前的，若在前面的都无法完成，那么后面的更加不可能完成。题目十分良心，$a_i$ 已经在输入时升序给出。 对于每个任务，需要用尽可能少地耗时完成尽可能多的百分比，每个计划的状态均为选或不选，这不就是 $0-...

部分参考了 这篇 xianggl巨佬的博客。 由于 $d \le 20$，考虑将不等关系的信息存放在数组中，转换为最大距离 $d$ 时的信息。考虑单独处理每一个点时，直接暴力修改与某一点 $x$ 距离为 $[0,d]$ 的点，此时不难分析出时间复杂度...

首先提醒一下不要读错题目，因为题目并没有要求旋转 $90$ 度是顺时针还是逆时针。 将 $dx,dy$ 分开考虑，题目转换为 $dx = A_1,dy = 0$，然后 $A_{2i + 1},A_{2i} (i > 0)$ 分别对 $dx,dy...

第一问很好求，相当于是所有点到 $s$ 或 $t$ 中较近的点的最短路径之和。换句话说，把 $s$ 与 $t$ 分别作为起点，跑两遍最短路后得到 $diss,dist$ 分别表示最短路，则答案即为 $\sum\limits_{i = 1}^{n} \...

看到题目，有三个变量，首先想到消参。由辗转相减法可知 $\gcd (a,b) = \gcd (a,a + b)$，又因为 $a + b + c = n$，所以 $a + b = n - c$，即 $\gcd (a,b) = \gcd (a,n - c...

所有操作均建立在二维平面上，容易想到 STL 库的 set。将点的 $y$ 坐标放入到对应的集合 $x$ 中进行相应的操作。插入操作为 s[x].insert (y)，删除操作为 s[x].erase (y)，而查询操作需要从小到大遍历下标大于 $x...

第二种操作是从 $1$ 开始修改的，也就是修改一段前缀，考虑递推。由于操作可逆，所以我们可以转换为将读入的串变为全 A 串所需的最小变换次数。 设 $f_{i,0}$ 表示前 $i$ 个字符均为 A 时的最小变换次数，设 $f_{i,1}$ 表示前 ...

这是一道区间 dp，思维难度与实现难度都不小，主要的瓶颈在于如何不重不漏地转移（这要求仔细地读题）。 和题目一样，A 表示一个符合规范的超级括号序列，S 表示任意一个仅由不超过 $k$ 个字符 * 组成的非空字符串，即 *...*。以下就不再赘述字符...

本题是 P4302 [SCOI2003]字符串折叠 的强化版。 不难看出这是一个区间 dp，令 dp[i][j] 表示区间 $[l,r]$ 的最小长度。考虑两种操作： 合并两个小区间后变为一个大区间 将某个区间进行折叠 第一个操作，显然就是区...