Educational Codeforces Round 181 (Div. 2) 题目讲解 ABCDE (CF2125)

合集 · 题目讲解 (117)

Parts

Description

C: 容斥原理 https://www.bilibili.com/video/BV1PZ421a75t
D: DP动态规划基础 https://www.bilibili.com/video/BV1PF4m1M7sH
取模大数ModInt https://www.bilibili.com/video/BV194421F7na
E: DP动态规划基础 https://www.bilibili.com/video/BV1PF4m1M7sH
取模大数ModInt https://www.bilibili.com/video/BV194421F7na

Comments

SSSSliver丶 2025-07-23

E这个题目我看别的up讲，从a数组考虑，我都能看懂，但是不知道后面为什么是一个完全背包的板子，想了挺久，最后想明白了，分享一下 a数组最差就是1~n，因为Q要有n个不同的数字，而且Q最大数字就是 Sa - 1 那么 Sa - 1 > x 就是无解观察得到：我们a数组从小到达排序，Q从大到小排序，差分数组的对应位置相同，a若是+1，Q就是-1 所以我们a数组只要差分数组不同，Q就是不同的在第i个差分数组中+1，那么在原来的a中就要从ai 到 an全+1 那么对于第i个差分位置，我们的代价就是 n - i + 1 所以这个问题就变成了：给定n - 1个物品，物品无限多（因为差分的位置你可以一直加），每个物品的体积是n - i + 1，求最后的不同装入物品的方法数这就是个完全背包的板子了由于我们a数组接受重复元素，所以对于体积为j的情况下，我们还可以加入（n - j + 1)个1，每一次多加一个1就有新的一种方案例如： a = 【1, 2, 3】 -> Q = 【3, 4, 5】; a = 【1, 1, 2, 3】 -> Q = 【4, 5, 6】; a = 【1, 1, 1, 2 ,3】 -> Q = 【5, 6, 7】; 最后就吧dp【n】【j】 * (n - j + 1) 全部加起来即可这里n = 1要特判，因为我们第一个数就是1，所以直接输出x即可若有错误，感谢指正

♥ 11

乄折纸乄 2025-07-23

前排[吃瓜]

♥ 4

Clownker 2025-07-23

饭老师[星星眼]

♥ 1 ↩ 1

巴图工程师的榔头 2025-08-02

催更cf1039[打call]

♥ 1

吃粑粑的孩子 2025-07-26

E题我有个思路，假设原集合的数总和为sum，原集合的最小为min。因为新集合的元素要<=x。所以就要满足sum-min<=x。求出sum的上界为min+x，然后因为要有n个不同的数，原集合sum的下界就是n*min+（(n-1)*n)/2。然后我枚举min从1开始,直到下界超过上界结束。然后因为取相同的一定不优，然后我就做完全背包初始容量就是（上界-下界)，可拿取的物品就是1-(n-1）。我知道时间复杂度不对，但是为什么答案也不对啊。[大哭]

♥ 1 ↩ 2