题意有 $N$ 个小球，每个小球的坐标为 $(x_i,y_i)$ ，即水平为 $x_i$ ，高度为 $y_i$ ， 每秒会以 $v_i$ 的速度下落。人所在的初始位置为 $x_0$ ，每秒可以移动一个单位。当人移动到小球下面的时候就可以接住这个小球并获得分数，分数为小球当前高度的 $\dfrac{1}{1000}$ 。要求接住所有小球，求最高分数。$N\le 1000$ 。题解比较容易想到区...
题意可以用 $x(s)$ 来表示有 $x$ 个字符 $s$ ，可以在括号内嵌套和拼接。求一个字符串的最短折叠长度。字符串长度 $N\le 100$ 。题解设需要处理的字符串为 $S$ ，用 $f[l][r]$ 表示折叠 $S_l..S_r$ 的最短长度。显然可以从两个字符串拼接而来。枚举断点 $k$ ，$f[l][r]=\min(f[l][r],f[l][k]+f[k+1][r])$ 。也可...
最难受的事情莫过于比赛还剩20min，你锁了题，然后叉了自己。锁题有风险，叉人需谨慎。A. Choose Two Numbers题意从两个序列中各选取一个数，要求这两个数的和不属于这两个序列。序列长度 $N\le 200$题解水题，$N^2$ 枚举。#include<bits/stdc++.h>
using namespace std;
inline int read()
{...
题意给一个长度为 $N$ 的木板染色，木板有初始颜色，要求染成一种颜色。每次可以选择一段连续的格子染色，颜色可以被覆盖。求至少要染多少次。$N\le 50$ 。题解用 $f[l][r]$ 表示将 $[l,r]$ 染成一种颜色的最少次数。当 $S_l=S_r$ 时，可以在染一边时顺便把另一边染了，即 $f[l][r]=\min(f[l+1][r],f[l][r-1])$ 。否则可以枚举中间点 ...
题意有 $N$ 座城堡和 $S$ 个玩家，每个玩家有 $M$ 个士兵。能占领城堡要求自己驻扎的兵力严格大于对方的两倍，玩家之间两两都会有独立的城堡争夺，占领第 $i$ 个城堡的收益是 $i$。现在已知 $S$ 个玩家的驻军情况，求如何分配兵力，可以获得最大收益。$S,N\le 100 \ \ \ \ M\le 20000$ 。题解很显然的背包问题，只是需要预处理一下重量。用 $v[i][j]...
题意有一个只有 $-1,0,1$ 的序列，每次操作可以使 s[i]+=s[i-1] ，求最少要操作几次使得序列单调不降。无解输出 BARK序列长度 $N\le 1000000$ 。题解用 $f[i][j]$ 表示前 $i$ 个数，$s[i]=j-1$ 时的最少操作次数。然后对于每一位的值分类讨论即可。代码里很显然了，我懒得再写一遍了。#include<bits/stdc++.h>...
题意有一个序列，要求修改尽可能少的数，使得这个序列变成单调上升序列。输出最少需要修改多少个数，以及在修改最少的前提下，每个数改变的绝对值之和的最小值。序列长度 $N\le 35000$ 。题解子问题1如果只是单调不降就很简单，但这题要求单调上升。假设可以保留 $S_i,S_j \ (i < j)$ ，则需要满足 $S_j - S_i \geq j-i$ ，即 $S_j - j\geq ...
题意有 $A,B$ 两个字符串，要从 $A$ 中选出 $k$ 个子串，按原顺序排列后形成 $B$ 。求方案数。$A,B$ 的长度为 $N,M$ ，$N\le 1000 \ , \ M\le 200$ 。题解用 $f[i][j][k]$ 表示取到 $A_i,B_j$ ，选了 $k$ 个子串的方案数。可以枚举当前子串的长度 $l$ ，这样要求 $A_{[i-l+1,i]}$ 和 $B_{[j-l...
双倍经验：洛谷1868 饥饿的奶牛题意从 $N$ 个区间中选取一些不重叠的区间，使得总长度最大。$N\le 10000 \ \ L,R\le 30000$ 。题解用 $f[i]$ 表示前 $i$ 个数选取区间的最大总长度，答案即为 $f[n]$ 。如果存在一个区间 $[y,x]$ ，那么 $f[x]$ 就可以从 $f[y]$ 转移过来。方程式为：$$f[x] = \max \begin{ca...
题意自动刷题机每秒会增加或删除 $x$ 行代码。存在一个长度 $N > 0$ ，当 某一秒后累积的代码长度 $\geq N$ ，就会提交这个程序，并新建文件。已知刷题机交了 $K$ 道题，求 $N$ 的最值。秒数 $L\le 100000$ 。题解显然 $N$ 越小，交的题目就会越多，所以可以通过二分验证，不过只有刚好 $K$ 道的时候更新答案。唯一麻烦的就是最小值最大值都要求，而 最...
题意有 $N$ 天，每天剩余教室为 $R_i$ 个。有 $M$ 个人要借教室，从 $S_i$ 借到 $T_i$ 。问能否满足所有人，如果不行则输出第一个不满足的人。$N,M\le 10^6$ 。题解本来还想写线段树查询最小值的，然后发现二分+差分就能解决。做法就是二分答案，然后差分修改后验证是否有 $<0$ 的。#include<bits/stdc++.h>
using ...
题意有 $N$ 个矿石，价值和重量为 $V_i,W_i$ 。需要选择一个值 $W$ ，对于区间 $[l,r]$ ，校验值为$$\sum_j 1 \times \sum_j V_j \ \ (j\in [l,r] \ , \ W_j > W) $$总校验值为 $M$ 个区间校验值的总和。求最小总校验值。$N,M\le 200000$ 。题解我纠结了半天 $\sum_j 1$ 到底是啥，直...
这次我只过了三道，D题因为最后统计答案时越界而 Wrong answer on pretest 12 ，结束后把两个 n 改成 n-k+1 就过了，我真是傻逼。代码都是考场代码，所以很丑，凑合看吧。A. Hotelier题意有 $10$ 个房间，客人可能从左边或右边进来，进来后给客人安排最近的房间。可能有人离开。给出 $N$ 个操作，要求输出操作后每个房间是否有人。$N\le 10^5$题解...
题意把 $N$ 个数分成 $M$ 段，要求每段和的方差尽可能小，求最小值。$N\le 3000$ 。题解我这个辣鸡的错误解法方程还是比较容易想到的，用 $f[i][j]$ 表示当前是第 $i$ 段，分到第 $j$ 个数的最优解，方程为：$$f[i][j] = \min_{k=0}^{j-1} (f[i-1][k] + \sum_{p=k+1}^j M\times (X_p - \overli...
题意有 $N$ 个工厂，每个工厂与第 $1$ 个工厂的距离为 $X_i$，有成品 $P_i$ 件。需要修建一些仓库，在每个工厂修建的成本为 $C_i$ 。修建完成后要将成品全部运到仓库里，且只能往序号较大的工厂里运输。运输的成本为 $P_i\times (X_j-X_i)$ 。求成本的最小值。$N\le 10^6$ 。题解用 $f[i]$ 表示最后在 $i$ 修仓库的最小成本，枚举上一次修仓...