我们先来看看简单版本的想法，非常具有启发性大致的思路见这篇文章下面是对这篇文章具体操作的阐释我们先将所有区间按照左端点单调递增排序，并统计每一个区间中\(c_i=1\)的个数（这个直接用前缀和就好了，设\(sum[i][j]\)表示前\(i\)个数中\(c_k=j\)的个数），枚举其中一个区间（设为\([l,r

这道题目。。哎首先，我们对两个连通块进行连边的时候，肯定是选择编号最小的点进行连边，所以下文的\(i,j\)都指代编号最小的\(i,j\)然后我们就没有其他思路了。。但其实样例一的解释给了我们一种猜想：最终的图一定可以长成以\(1\)号点为中心的菊花图要达到这一点，我们肯定是尝试构造

题目链接：CF或者洛谷高分题，感觉挺有意思的题，值得一提的是这个题的\(1\)和\(3\)版本却是两个基础题。一开始以为跟这道差不多：P8512[YnoiEasyRound2021]TEST_152题解。后面重新读了一下发现一个有趣的点：也就是是说操作的\(val\)并不太好搞了，如果\(val\)确定就基

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

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

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

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

CF1764DDoremy'sPeggingGame你怎么连简单题也不会？考虑满足条件当且仅当有连续的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\)为满足\(l\in(j,i],r\in[i,n]\)的区间\([l,r]\)个数。显然可以考虑套

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

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