烂题分享

· · 个人记录

[ARC104D] Multiset Mean

求可重集合 S 的个数，满足 [1,n] 中每个数出现 [0,k] 次且 S 中各个元素的平均数为 x\in [1,n]。

对于每个 S，和显然是 cnt\times x，cnt 为集合内元素个数。

将每个数都减去 x，那么就是要让集合内的所有数和为 0。

然后就可以计算最终答案为 $$ (k+1)\times \sum_{i=1}^{n} \sum_{j} f_{i-1,j}\times f_{n-i,j} -1 $$ ## [ABC299G] Minimum Permutation 从 $a$ 中选出一个长度为 $M$ 的字典序最小的排列并输出。 很明显的贪心，也很容易结合栈的思想，但是有一些小的性质需要去分析。 对于排列中的每个元素，除非该元素是在序列 $a$ 中最后一次出现，否则都必须满足单调递增的性质，然后想到用单调栈维护即可。 ## [ABC337F] Usual Color Ball Problems 把小球排成一个环，从每个位置起顺时针取 $n$ 个球按“同色优先、能开新盒就开，否则吃掉”的规则依次放入最多 $m$ 个、每盒容量 $k$ 的单色盒子里，问每种起点最终盒子中球的数量。 把序列复制成长度 $2\times n$，从右往左滑动窗口，同时按颜色维护“被放入盒子的出现前缀”和“开盒顺序栈”，遇到新球要么平移该颜色前缀要么新开盒并必要时踢掉最晚开的盒子，实时记录每个起点的总放入数作为答案。 ## [ABC389F] Rated Range 想到是不是线段树板子，对每个区间加一，然后每次询问查询单点的值。 但是这样肯定错，因为单点的值在加的过程中肯定会发生改变。 正难则反，可以直接把所有询问离线下来排个序，成为一个序列建一颗线段树。 **可以证明无论如何修改序列的值，元素之间的相对大小关系不变！** 然后就可以线段树上二分。 ## P5579 [PA 2015] Siano 思路类似 [ABC389F] Rated Range，先将所有的草排序之后发现每次剪掉不会改变草的相对高度大小关系，因此先排序，然后建线段树，每次二分出第一个大于等于 $b_i$ 的节点，线段树维护最大最小值（线段树二分）、区间和即可。 ## [ARC107D] Number of Multisets 想到了和二进制拆分有关的东西，但是感觉非常不可做，然后开始考虑 dp。 可以把目标取倒数，似乎变得可做了很多。 设 $f_{i,j}$ 表示前 $i$ 个数和为 $j$ 的方案数，考虑如何转移。 对于每个 $j$，应该有 $f_{i,j\times 2} \to f_{i,j} $，因为 $\frac{1}{2^i}=1\times (\frac{1}{2})^i$，其本质就是将若干个数缩小一半，成为下一级。 ## [ABC358C] Popcorn 二进制暴力即可。 ## [ABC411E] E [max] 期望值的答案其实就是每个骰子的每个点数乘上其成为最大值的概率。 题目就转化为求对于每个点数，其成为最大值的概率。 它。 可以把所有骰子出现的所有点数全部放到 vector 里，然后先想到二分，然后就发现可以用双指针处理出这个东西，然后计算答案即可。 一个点数成为最大值，那么其他骰子上的点数都小于等于 时间复杂度是 $O(n\log n)$。 ## 【旧题重做】[ABC317F] Nim 之前学的一道数位 dp 题，看到一年半前写的十维状态设计，畏惧了。 使用记忆化搜索，状态设计中分别维护数的二进制位、模 $a1,a2,a2$ 余数、与 $n$ 的前缀是否相同，以及是否全是前导 $0$。 与 $n$ 的前缀是否相同用于剪枝，是否全是前导 $0$ 用于满足 $x,y,z > 0$ 的条件。 ## [ABC273G] Row Column Sums 2 因为 $0 \le R_i,C_i \le 2$，所以矩阵中的所有元素也一定是在 $[0,2] $ 的范围内 `。` 考虑一个三维的 dp，设 $f_{i,j,k}$ 表示前 $i$ 行有 $j$ 列和为 $1$，有 $k$ 列和为 $2$ 的方案数。 第一维应该可以滚动数组掉，但是时间复杂度就是 $O(n^3)$ 的，显然不可接受。 发现 $k$ 其实是可以通过 $j$ 推导出来的，因此其实可以实现一个一维的 dp。 设 $f_{i,j}$ 表示前 $i$ 行有 $j$ 个“列的和为 $1$” 的要求待满足的方案数，可以滚动数组滚掉一维，然后就可以直接状态转移了，这个状态转移方程是好推导的。时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。 但为什么我的代码 WA 了两个点啊（恼。 注意最后如果 $sum=j+k\neq 0$ 的话要输出 $0$，否则会 WA 两个点。 ## P2724 [IOI 1998 / USACO3.1] 联系 Contact 注意到字串长度的上限很小，所以可以枚举 $k=B-A$ 次遍历 $i=[1,n]$ 记录下每个字串然后塞到 map 里排序。 但是这样显然不优，考虑 $B\le 12$，所以可以将每个字符串压成二进制数，然后写一个结构体进行排序即可。 本题难点在于正确地输入和输出。 ## P2874 [USACO07FEB] Building A New Barn G 根据曼哈顿距离的定义，$ans=\sum |Dx-x_i|+\sum |Dy-y_i| $，其中 $(Dx,Dy)$ 是曼哈顿距离最小的点。 根据小学奥数可以知道，对于一个一维的序列，若要让 $\sum |x-a_i|$ 最小，那么 $x$ 就一定是序列 $a$ 的中位数。 这一点也可以扩展到二维上，然后就做完了。 但是这道题不能取输入数据中的点，直接对答案微调一下即可。 ## 【旧题重做】[ABC398F] ABCBA KMP模板，以前还写过题解，借此机会复习一下 KMP 算法。 ## P2977 [USACO10JAN] Cow Telephones G 首先找一个非叶子节点作为这棵树的根节点，然后考虑后序遍历贪心。 设 $s$ 为节点 $u$ 的来自子树的所有配对请求数，该节点可以组成的配对数 $m=\min(\lfloor \frac{s}{2} \rfloor,K)$。 如果还有剩余且 $m<K$，则 $u$ 节点可以再往上多上传一个请求 $f=1$ ，否则 $f=0$。 最后的答案就是 $ans=\sum_{u\in T} m(u)$。