Doremy
CF1889C2 Doremy's Drying Plan (Hard Version)
Problem - C2 - Codeforces Doremy's Drying Plan (Hard Version) - 洛谷 很好的一道 \(dp\) 题,无论是 \(dp\) 状态还是优化都很思维 我们设 \(dp_{i,j}\) 表示考虑了前 \(i\) 个城市,第 \(i\) 个城市干 ......
CF1764H Doremy's Paint 2 题解
题目链接 先断环成链,由于对于多组询问不好一起处理,我们先考虑单组询问的处理方式。 一个很暴力的想法是每次模拟题目要求的操作并且最后数颜色,我们这是在通过下标进行操作最后再数颜色,而很多对于下标的操作都是不必要的,考虑直接枚举颜色进行判定。 对于每种颜色,它对于最后答案有贡献当且仅当它可以存活到那个 ......
5-1889B - Doremy's Connecting Plan
题意: 思路: \(i*j*c 越小越有利, 可以让i为1 ,即都与节点1建边, 1节点集合拥有的人越多越有利于于别的集合相连, 对别的点按照,最小要求人数-现有人数=需要人数排序,按顺序连接即可。\) 代码: 点击查看代码 #define int long long using namespace ......
CF1890D Doremy's Connecting Plan
或许赛时根本不需要证明贪心的正确性。 我们发现 \(c\) 对于问题的影响不大,我们可以将每个 \(a_i\) 除以 \(c\),就转化为了 \(c=1\) 的情况。 一个自然的贪心是用 \(1\) 作为中心点去连接其他的所有点,这需要两条结论保证其正确性: 结论一: 如果当前图中还可以连边,点 \ ......
E1. Doremy's Drying Plan (Easy Version)
E1. Doremy's Drying Plan (Easy Version) The only differences between the two versions of this problem are the constraint on $k$, the time limit and th ......
Codeforces Round 906 (Div. 2) Doremy's Drying Plan E1.&E2
传送门 先考虑\(E1\) 只需要删除两条线使得不被覆盖的点数最多。 观察到点数只有\(200000\) 那么我们完全可以先将被至少\(3\)条线覆盖的点删掉。 考虑枚举一条线,枚举这条线覆盖的点寻找另外一条线覆盖这些点中的最大值,然后再找没覆盖这些点之外的线的最大值即可。 复杂度容易证明是线性的。 ......
《CF1889C2 Doremy's Drying Plan (Hard Version)》 解题报告
考场上不会做。 如果考虑删掉哪些区间实际上不太可做。正难则反,转化贡献,考虑哪些点可以有贡献。 显然一个点如果可能有贡献,那么当且仅当覆盖它的区间 \(\le K\) 个。 于是我们记一个状态 \(f_{i,j}\) 表示前 \(i\) 个点中, \(i\) 是最后一个贡献的点,已经删除了 \(j\ ......
CF1889C2 Doremy's Drying Plan (Hard Version) 题解
Description 有 \(n\) 个点和 \(m\) 条线段,你可以选择 \(k\) 条线段删除,最大化未被线段覆盖的点的数量,输出最大值,\(n, m \le 2 \times 10^5, k \le \min(m, 10)\) Solution 一道比较好玩的 dp 题。建议评级紫。 单独 ......
CF1764D Doremy's Pegging Game 组合数学
CF1764D Doremy's Pegging Game 你怎么连简单题也不会? 考虑满足条件当且仅当有连续的n/2向下取整段被删除。 考虑最终状态一定是一次删除联通了两个连续段,然后结束。 我们枚举这个连续段的长度 i 。 最后一个删除的位置有 n/2下取整*2-i 种方案,设另外删除了 j 种 ......
CF1889C2. Doremy's Drying Plan (Hard Version)
容易想到 dp:设 \(dp_{i,p}\) 表示前 \(i\) 天,强制第 \(i\) 天 dry,并且一共消除了 \(p\) 个区间的答案。 转移时可以考虑枚举前面的决策 \(j\),此时有转移方程: \[dp_{i,p}=\max(dp_{j,p-w})+1 \]其中 \(w\) 为满足 \( ......
CF1889B. Doremy's Connecting Plan
一开始不会先跳 C 了!差点满盘皆输! 设 \(i<j\),则 \(i,j\) 合并可以看作 \(a_i\leftarrow a_i+a_j\) 后删掉 \(j\)!此时和初始局面本质相同!所以不妨先只看初始局面! 不等式右侧和下标有关!显然若右侧 \(i,j\) 中只要有一个是 \(1\),就会让 ......
D. Doremy's Connecting Plan
D. Doremy's Connecting Plan Doremy lives in a country consisting of $n$ cities numbered from $1$ to $n$, with $a_i$ people living in the $i$-th city. ......
CF1890D Doremy's Connecting Plan
Problem - 1890D - Codeforces 这个式子左边是加法,右边是乘法,很不好算 但其实是降智题,不过同时也是我不擅长的找性质 因为式子左边是加法而不是乘法,因此像类似于并查集那样求出当前每个联通块内 \(\sum a_i\) 等价于固定一个点从这个点的联通块向外扩展。 \(i\) ......
Codeforces Global Round 24 B. Doremy's Perfect Math Class
给一个元素个数为 $n$ 的正整数集合 $S$ ,可以做以下操作任意次: * 选择 $S$ 中的两个元素 $x$ $y$ 满足 $x > y$ 且 $x - y$ 不在集合内。 * 加入 $x - y$ 到集合。 经过若干次操作后,集合中最多能存在多少元素。 性质一:两个数 $x$ $y$ 辗转相减 ......
Codeforces Global Round 24 D. Doremy's Pegging Game
首先我们可以假设最后一个删除的peg编号是x,那么可以发现每个编号结尾的方案数是一样的,可以只专注计算最后删1号peg的方案数,然后乘一下就好 然对于1来说,我们需要找到一个(x, y) 的组合,x和y之间允许剩pegs,但是1到x,以及y到1之间的pegs都被移除,这个状态在此时依然没有触碰blu ......