普及+/提高

CF2182E New Year’s Gifts 思路 题目中提到必须给 $i$ 号朋友买价值为 $y_i$ 的礼物，则这部分开销是不可避免的，直接从初始资金中减去。 此时对于朋友 $i$，他的贡献可以被形式化地表达为： 消耗 $\Delta=z_i-y_i$ 的剩余金钱产生 $1$ 的贡献。 消耗一个至少为 $x_i$ 美观度的礼盒产生 $1$ 的贡献。 且这两种操作不可重复计算。 我们可以贪心的将所有 $\Delta$ 按照大小排序，从小到大遍历所有礼盒，对于每个礼盒，找到它可以产生贡献的最大 $\Delta$，再使用这个礼盒，删除掉对应的 $\Delta$。 看到这里，我们需要一个可以支持插入、排序和删除的数据结构。 set 就非常合适。 但注意到这里面可能会出现相同元素，所以使用类似的 multiset。 还有一些细节，见代码中注释。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162...

CF2182D Christmas Tree Decoration 思路 手玩样例后发现这个拿装饰品的机制和班上轮换做清洁有点像啊。 不难发现在合法情况下，最少的拿取次数最多比最多的拿取次数少 $1$ 次。 那我们先判断是否合法，方法如下： 找到对应装饰品最多的一个人，设他的对应盒子中有 $mx$ 个装饰品。 将其他人的对应装饰品补足至 $mx-1$，不够的部分从 $p_0$ 中减掉。若在某一步 $p_0$ 不够了，则方案数为 $0$。 然后此时一定存在合法情况，我们考虑如何计算合法排列数。 首先这个排列中每个人的挂装饰品次数应当形如 $mx,\cdots,mx,mx-1,\cdots,mx-1$。 先扫描一遍整个数组，找到 $mx$ 有多少个，设它有 $a$ 个，则 $mx-1$ 有 $n-a$ 个。 此时分类讨论： 若 $p_0\le n-a$，则 $p_0$ 无法将所有 $mx-1$ 补到 $mx$，那么在补足后将会有 $a+p_0$ 个 $mx$，$n-a-p_0$ 个 $mx-1$，则答案为 $C_{n-a}^{p_0}\cdot A_{a+p_0}^{a+p_0...

CF2170D Almost Roman 思路 首先我们对每个数字进行分析： $I$ 权值最大为 $1$，最小为 $-1$， $V$ 权值为 $5$， $X$ 权值为 $10$。 注意到无论在何种情况下，$X$ 的权值和造成的影响一定比 $V$ 多 $5$。 可以把原字符串中的所有 $X$ 替换成 $V$，每替换一次就给总权值加 $5$。 又发现对于任意位置，填 $I$ 一定比填另外两个更优。 所以我们先将所有问号的位置都填上 $I$，如果不够就再替换成另外两个。 对于每一次替换，有以下三种情况： 增加了权值为 $-1$ 的 $I$ 的个数， 权值为 $-1$ 的 $I$ 的个数不变， 减少了权值为 $-1$ 的 $I$ 的个数。 显然我们应先替换第一种，再替换第二种，最后选第三种。 那代码就很好实现了。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707...