思路： 注意到对于每个数，其\(>19\)的质因数最多只有\(1\)个，称为大质数；对于\(\le19\)的质因数有\(8\)个，称为小质数。 设第\(i\)个数的小质数集合为\(h_i\)。 那么考虑对于所有数按照大质数从小到大排序，那么对于大质数相同的一段，只能放在两个集合中的一个。 考虑状态压缩\(dp\)，定义\(dp_{S_1,S_2}\)表示对于取完\(i\)（可以滚动数组）个数后第一/二个集合的小质数集合，\(f1_{S_1,S_2}\)表示这一段的数都放在第一个集合的方案数，\(f2_{S_1,S_2}\)表示这一段的数都放在第二个集合的方案数。 则状态转移方程为（首先要...

思路： 首先求出\(a\)的前缀和数组\(s\)。 考虑动态规划，令\(dp_{i,j}\)表示以\(i\)结尾，末尾有\(j\)个为一组的最小答案，则状态转移方程为： \[dp_{i,j}=\min[s_{i-j}-s_{i-j-k}\les_is_{i-j}]dp_{i-j,k}+(s_is_{i-j})^2\] 朴素直接转移是\(O(N^3)\)的，可以得到36pts的好成绩代码就懒的给了。 考虑优化，对于求出最小的一个\(k\)，使得\(s_{i-j}-s_{i-j-k}>s_is_{i-j}\)，那么状态转移方程为： \[dp_{i,j}=(s_is_{i-j})^...

思路： 首先发现单调性，灵活性增加\(x+1\)的答案肯定不会比增加\(x\)的答案更劣。 那么可以二分求\(g\)，则机器人每次可以移动\([\max(d-mid,1),d+mid]\)这个区间内的距离，为了方便，设为\([l,r]\)。 考虑动态规划求得能走到的最大分数，令\(dp_i\)表示走到第\(i\)个格子的最大分数，则状态转移方程为： \[dp_i=s_i+\max\limits_{j=0}^{i-1}[x_ir\lex_j][x_j\lex_il]dp_j\] 可以使用单调队列维护： 若当前队尾为\(j\)，且\(x_j<x_ir\)，则这个\(j\)无法对\(...

思路： 考虑动态规划。 定义\(dp_i\)表示若有一班车在第\(i\)个时间出发所有人等待的时间，则状态转移方程为： \[dp_i=dp_j+\operatorname{get}(j+1,i)(j\leim)\] 其中\(\operatorname{get}(l,r)\)表示等车时间在\([l,r]\)范围内的人在\(r\)处上车的等待时间，考虑\(O(1)\)求出\(\operatorname{get}(l,r)\)。 定义\(s_i\)表示等车时间在\([0,i]\)的所有人的等车时间之和，\(a_i\)表示等车时间在\([0,i]\)的人的个数，则： \[\operator...

思路： 先将时间进行离散化，设总时间为\(cnt\)，然后考虑求出\(W(l,r)\)，即在时间段\([l,r]\)内的所有节目，可以\(n^2\)前缀和，也可以\(n^3\)暴力。 然后定义\(f_{i,j}\)表示前\(i\)个时间，一号场地有\(j\)个节目时，二号场地最多的节目数量，则状态转移方程为： \[f_{i,j}=\max\limits_{k=0}^{i-1}\max(f_{k,j}+W(k,i),f_{k,j-W(k,i)})\] 那么可以得到： \[ans_0=\max\limits_{i=0}^n\min(i,f_{cnt,i})\] 则第一个问的时间复杂...

思路： 来一篇极小常数的\(O(N^3M)\)和\(O(N^2M\log^2N)\)的题解，最慢点在500ms以下但是为什么还是最劣解。 定义\(dp_{i,j,k,x\in\{0,1,2\},y\in\{0,1,2\}}\)表示对于正在画的第\(x\)个字符，目前正在画开头/中间/结尾，且当前画的矩形的右下角是\((i,j)\)和右上角\((k,j)\)。 则状态转移方程为，为了使式子不过于太丑陋，分段函数就表示取\(\max\)： \[dp_{i,j,k,0,0}=\begin{cases}\sum\limits_{I=k}^ia_{I,j}\\\sum\limits_{I=k}^ia...

思路： 注意到点对数量有\(N^2\)个，考虑丢掉一些无用的点对。 对于点对\((x_1,y_1),(x_2,y_2)\)，满足\(x_1\lex_2<y_2\ley_1\)，即区间\([x_2,y_2]\)被\([x_1,y_1]\)包含，此时满足若询问到了\([x_1,y_1]\)，则一定会询问到\([x_2,y_2]\)。 若满足\(\operatorname{dis}(x_1,y_1)\ge\operatorname{dis}(x_2,y_2)\)，那么此时可以将\((x_1,y_1)\)舍弃，因为若要用\((x_1,y_1\))的贡献，不如直接去看\((x_2,y_2)\)的贡...

思路： 首先令\(nxt1_i\)表示右侧最近的城市距离（\(id1_i\)为编号），令\(nxt2_i\)表示右侧第二近的城市编号（\(id2_i\)为编号）；可以使用set找出离这个城市最近的\(4\)个城市（前面两个，后面两个）。 定义： \(f_{i,j}\)表示从\(i\)点出发走\(2^j\)轮最后到达的位置。 \(dp1_{i,j}\)表示从\(i\)点出发走\(2^j\)轮最后A走过的距离。 \(dp2_{i,j}\)表示从\(i\)点出发走\(2^j\)轮最后B走过的距离。 初始化： \[f_{i,0}=id1_{id2_i}\] \[dp1_{i,0}=nx...

思路： 对于插入操作，设插入\(\{t,p\}\)： 若当前\(1\simt\)有空位，那么就放进去。 否则，\(1\simt\)是被塞满了的： 首先容易想到的是找到\(1\simt\)中贡献最小的那个工作，若贡献比\(p\)还小，可以与之替换掉。 但是假了，考虑这样一种情况：在\(1\simt\)外有一个更小的值，可以跟\(1\simt\)中的某个工作换一个位置，然后再将这个替换过来的工作替换掉，这样无疑是更优的。 考虑如何快速维护这个东西，使用两棵线段树： 第一棵线段树维护所有截止时间在区间\([l,r]\)的时刻完成的任务的截止时间的最大值。 第二棵线段树维护所有截止时间在区间\(...