简单规划学

显然答案是 $n-最大匹配$。

从下往上 $dp$，设 $dp_u$表示 $u$ 子树内最多能有多少对匹配，$sz_u$ 表示 $u$ 子树的大小，考虑怎么转移。

设 $M=\max_{v\in son}sz_v,S=\sum_{v\in son}sz_v,D=dp_{\arg\max_{v\in son}sz_v}$。（也就是说 $D$ 是最大的子树对应的 dp 值）。

然后转移就是： $$dp_{u}=\begin{cases} \lfloor S/2\rfloor&,M\le S-M\\ S-M+\min(\lfloor(M-(S-M))/2\rfloor,D)&,M>S-M \end{cases}$$ 第一部分没啥好说的，肯定可以取到这个上界。然后第二部分就相当于是首先其他子树和最大的子树配对，然后最大的子树内部配对。

时间复杂度 $\mathcal O(n)$。

然后出题人发现这样太简单了。于是加了个输出方案。你怎么构造就怎么输出方案就行了吧。就算你不想写也有 $80$ 分。

简单遗传学

以下 $K=\max k$。

我会 $\mathcal O(n^2 K)$！设 $f_{i,j}$ 表示第 $i$ 代有 $j$ 只公兔子为灰色的概率（显然当 $i\ge 1$ 时灰色的母兔子也是这个数量），那么转移就是： $$f_{i,j}\times \binom{n-j}k^2\binom jk^2(j-k)!k!^2(n-j-k)!/n!\to f_{i+1,j+k}$$ 这个就是说灰色的公兔子中选出 $k$ 只去和 $k$ 只白色的母兔子繁殖，灰色的母兔子中选出 $k$ 只去和 $k$ 只白色的公兔子繁殖，$j-k$ 只灰色的公兔子和 $j-k$ 只灰色的母兔子繁殖，$n-j-k$ 只白色的公兔子和 $n-j-k$ 只白色的母兔子繁殖。

可以拿到 $30$ 分。

我会 $\mathcal O(Tn^3\log K)$！上面的转移写成矩阵的形式就可以转移了。

我会 $\mathcal O(n^3\log K+Tn^2\log K)$，你只需要处理好 $M,M^2,M^4,\dots$，然后每次询问的时候只需要做向量乘矩阵就可以了。

可以拿到 $60$ 分。但是好像卡卡常就能过了，大受震撼。

我会 $\mathcal O(n^3+Tn^2\log K)$！设 $g_{i}$ 表示第 $i$ 代灰兔子的期望只数，大胆猜测 $g_i$ 是一个 $n$ 阶常系数齐次线性递推。也就是： $$g_i=\sum_{j=1}^na_jg_{i-j}$$ 求系数可以用 BM。但是这个不能考（也许），所以直接用高斯消元求系数即可。

然后知道递推式求一项是众所周知的了。也许吧，应该没有超纲（逃

简单畜牧学

首先第一个子任务只要输出： $$\left|\sum_{i=1}^n (x_i-x_{i\bmod n+1})y_i\right|$$ 即可。

然后第二个子任务可以变成一个不超过 $1000\times 1000$ 的网格图，暴力 bfs 判断哪些区域是在内部即可。

然后就是把这个东西的外轮廓线顺时针画下来，毛估估边数就不会太多对吧。一个上界是说不超过 $\mathcal O(n\alpha(n))$，不知道有没有高论。

反正就是不多，所以我们可以暴力走一圈。

但是也不能太暴力，至少你每次不能只走 $1$ 的距离，至少要走到下一个交点。于是我们要做的有两样东西，一是从一个点出发往某个方向走可不可以走，二是从每个点出发往某个方向走走到的第一个交点。

这两个都是简单的。第一个就相当于有若干条线段，询问线段 $[a,a+1]$ 是否被覆盖。第二个就相当于是有 $10^6$ 个集合，$v$ 会在 $l\sim r$ 出现，然后询问一个点在指定集合里的前驱后继。

然后把这两个东西写好之后就可以绕一圈计算面积了。到这里就是子任务一了。

大概就是这么个东西。可以自己画一画就清楚了。