Doremy

Problem - C2 - Codeforces Doremy's Drying Plan (Hard Version) - 洛谷 很好的一道 \(dp\) 题，无论是 \(dp\) 状态还是优化都很思维 我们设 \(dp_{i,j}\) 表示考虑了前 \(i\) 个城市，第 \(i\) 个城市干 ......

题目链接 先断环成链，由于对于多组询问不好一起处理，我们先考虑单组询问的处理方式。 一个很暴力的想法是每次模拟题目要求的操作并且最后数颜色，我们这是在通过下标进行操作最后再数颜色，而很多对于下标的操作都是不必要的，考虑直接枚举颜色进行判定。 对于每种颜色，它对于最后答案有贡献当且仅当它可以存活到那个 ......

题意： 思路： \(i*j*c 越小越有利， 可以让i为1 ，即都与节点1建边， 1节点集合拥有的人越多越有利于于别的集合相连， 对别的点按照，最小要求人数-现有人数=需要人数排序，按顺序连接即可。\) 代码： 点击查看代码 #define int long long using namespace ......

或许赛时根本不需要证明贪心的正确性。 我们发现 \(c\) 对于问题的影响不大，我们可以将每个 \(a_i\) 除以 \(c\)，就转化为了 \(c=1\) 的情况。 一个自然的贪心是用 \(1\) 作为中心点去连接其他的所有点，这需要两条结论保证其正确性： 结论一： 如果当前图中还可以连边，点 \ ......

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 ......

传送门 先考虑\(E1\) 只需要删除两条线使得不被覆盖的点数最多。 观察到点数只有\(200000\) 那么我们完全可以先将被至少\(3\)条线覆盖的点删掉。 考虑枚举一条线，枚举这条线覆盖的点寻找另外一条线覆盖这些点中的最大值，然后再找没覆盖这些点之外的线的最大值即可。 复杂度容易证明是线性的。 ......

考场上不会做。 如果考虑删掉哪些区间实际上不太可做。正难则反，转化贡献，考虑哪些点可以有贡献。 显然一个点如果可能有贡献，那么当且仅当覆盖它的区间 \(\le K\) 个。 于是我们记一个状态 \(f_{i,j}\) 表示前 \(i\) 个点中， \(i\) 是最后一个贡献的点，已经删除了 \(j\ ......

Description 有 \(n\) 个点和 \(m\) 条线段，你可以选择 \(k\) 条线段删除，最大化未被线段覆盖的点的数量，输出最大值，\(n, m \le 2 \times 10^5, k \le \min(m, 10)\) Solution 一道比较好玩的 dp 题。建议评级紫。 单独 ......

CF1764D Doremy's Pegging Game 你怎么连简单题也不会？ 考虑满足条件当且仅当有连续的n/2向下取整段被删除。 考虑最终状态一定是一次删除联通了两个连续段，然后结束。 我们枚举这个连续段的长度 i 。 最后一个删除的位置有 n/2下取整*2-i 种方案，设另外删除了 j 种 ......

容易想到 dp：设 \(dp_{i,p}\) 表示前 \(i\) 天，强制第 \(i\) 天 dry，并且一共消除了 \(p\) 个区间的答案。 转移时可以考虑枚举前面的决策 \(j\)，此时有转移方程： \[dp_{i,p}=\max(dp_{j,p-w})+1 \]其中 \(w\) 为满足 \( ......

一开始不会先跳 C 了！差点满盘皆输！ 设 \(i<j\)，则 \(i,j\) 合并可以看作 \(a_i\leftarrow a_i+a_j\) 后删掉 \(j\)！此时和初始局面本质相同！所以不妨先只看初始局面！ 不等式右侧和下标有关！显然若右侧 \(i,j\) 中只要有一个是 \(1\)，就会让 ......

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. ......

Problem - 1890D - Codeforces 这个式子左边是加法，右边是乘法，很不好算 但其实是降智题，不过同时也是我不擅长的找性质 因为式子左边是加法而不是乘法，因此像类似于并查集那样求出当前每个联通块内 \(\sum a_i\) 等价于固定一个点从这个点的联通块向外扩展。 \(i\) ......

给一个元素个数为 $n$ 的正整数集合 $S$ ，可以做以下操作任意次： * 选择 $S$ 中的两个元素 $x$ $y$ 满足 $x > y$ 且 $x - y$ 不在集合内。 * 加入 $x - y$ 到集合。 经过若干次操作后，集合中最多能存在多少元素。 性质一：两个数 $x$ $y$ 辗转相减 ......

首先我们可以假设最后一个删除的peg编号是x，那么可以发现每个编号结尾的方案数是一样的，可以只专注计算最后删1号peg的方案数，然后乘一下就好 然对于1来说，我们需要找到一个(x, y) 的组合，x和y之间允许剩pegs，但是1到x，以及y到1之间的pegs都被移除，这个状态在此时依然没有触碰blu ......

题解 CF1764G Doremy's Perfect DS Class (Extra) 题意 交互库有一个 $1\sim n$ 的排列 $p$，你每次可以想交互库给定三个整数 $l,r,k(1\le l\le r\le n,1\le k\le n)$，交互库会返回 $\lfloor p_l/k\r ......