今日推歌：
神っぽいな/ピノキオピー
歌词
今天除了 T1 都不会，打完暴力分就开始发呆
T1：
考场上一眼原，虽然之前没做过，但是很快就搞出来了
设 \(f_i\) 为目前有 \(i\) 张邮票，要买到 \(n\) 张邮票的期望次数，写一个逆推套路式子：
\[f_i=\frac{n-i}{n}(f_{i+1}+1)+\frac{i}{n}(f_i+1) \]简单解一下得：
\[f_i=f_{i+1}+\frac{n}{n-i} \]然后设 \(g_i\) 为目前有 \(i\) 张邮票，要买到 \(n\) 张邮票的期望钱数，发现钱数和期望次数其实是一个东西，当在买第 \(i\) 张邮票时，其期望钱数为 \(h_i=f_0-f_{i+1}\)，然后仿照 \(f\) 列一个式子：
\[g_i=\frac{n-i}{n}(g_{i+1}+h_i)+\frac{i}{n}(g_i+h_i) \]解得：
\[g_i=g_{i+1}+\frac{n}{n-i}h_i \]线性递推求解即可
T2：
树形 DP，一车人场切
设 \(f_i\) 为满足当前结点权值大于 \(x\) 的叶子结点数目最小是多少，那 \(k-f_1+1\) 即为答案，考虑如何转移
- 如果当前点为 \(\max\)，说明只要有一个儿子满足即可，对所有儿子的 \(f\) 取 \(\min\)
- 如果当前点为 \(\min\)，说明所有儿子都要满足，对所有儿子的 \(f\) 求和
发现根节点的 \(f\) 与 \(x\) 无关，所以 \(x\) 的最大值为 \(k-f_1+1\)
T3：
题意：
每个方格有一种颜色，一共有四种颜色：黑色，白色，粉色，绿色
合法的正方形，可以等分为四个正方形，左上角的正方形必须都是黑色，右上角的正方形必须都是白色，左下角的正方形必须都是粉色，右下角的正方形必须都是绿色
所以合法的正方形是这个样子：
BW
PGBBWW
BBWW
PPGG
PPGG回答q次询问
每次给定一个矩形，你需要正确的回答出这个矩形中最大的合法正方形的面积
\(f_{i,j,k}\) 为 \((i,j)\) 点是否为边长为 \(2k\) 的满足条件的矩形右上角，然后把这个东西二维前缀和一下，二分答案查找不越界的矩形内的二维前缀和是否为 0 即可
但似乎 xuany 有个卡不掉的暴力做法，放在这里供大家 hack，如果 hack 不掉这个的话是否存在复杂度上界
T4：
题意：
一个大小为 \(n\) 的包，有 \(n\) 种物品，其中第 \(i\) 种物品的大小为 \(i\)，数量为 \(i\) 个 ，他想知道装满这个背包的方案数是多少
首先发现只有 \(i\le \sqrt{n}\) 的情况物品能用完，所以 \(1\le i\le\sqrt{n}\) 的范围内为多重背包， \(\sqrt{n}+1\le i\le n\) 的情况下为完全背包
\(f_{i,j}\) 表示于第一种情况正在选第 \(i\) 件物品，容量为 \(j\) 的方案数，它有如下转移：
\[f_{i,j}=f_{i-1,j}+f_{i,j-i}-f_{i-1,j-i(i+1)} \]表示不拿 \(i\) 物品，再拿一个 \(i\) 物品，最多拿 \(i\) 个，所以对于 \(f_{i-1,j-i(i+1)}\) 是在 \(f_{i,j-i^2}\) 时多加上的，是多拿了的，所以要除去
\(g_{i,j}\) 表示拿了 \(i\) 个 \(\sqrt{n}+1\sim n\) 中的物品，占了 \(j\) 容量，转移有两个：
\[g_{i,j+i}=g_{i,j+i}+g_{i,j}\\ g_{i+1,j+\sqrt{n}+1}=g_{i+1,j+\sqrt{n}+1}+g_{i,j}\]第一个表示将所拿的 \(i\) 个物品的容量都加 1，所以这种情况没有 \(\sqrt{n}+1\) 的物品
第二个表示拿第 \(\sqrt{n}+1\) 个物品
发现这种转移巧妙地覆盖了所有情况
对于答案，将 \(f\) 和 \(g\) 所对应的相乘求和即可
标签：邮票,12,frac,闲话,sqrt,正方形,le,物品 From： https://www.cnblogs.com/Rolling-star/p/17475018.html