本来前面还有一点内容的，但是今天手残把文件从U盘里误删了，费了好大功夫恢复出来的时候发现前面一点内容已经被一段不知名且缺胳膊少腿的代码覆盖了，所以就只能这样了。这启发我没事多备份备份以防悲剧发生。
\(\color{red}{\text{CF1661F *2600}}\) 可以推广到许多函数上。所以可以二分斜率，假设为 \(k\)，那么把所有斜率大于 \(k\) 的点拿进来算代价，然后根据这个来移动左右指针，大概的思想是考虑两个位置选择的数量相同时如何调整分配。最后剩余部分用得到的斜率去做即可，有点细节。
\(\color{cornflowerblue}{\text{CF1658F *2700}}\) 为什么评分那么高呢。看样例猜想答案只可能是 \(1\) 或者 \(2\)，暴力验证就可以了。证明上考虑首尾相接成一个环，一定存在一段使得 \(1\) 的个数为给定值，因为由于题目给定的限制不可能都是正的或者都是负的，而这玩意的变化是连续的，所以一定存在，但是这段可能被边界割开所以就有了 \(2\) 的情况。
\(\color{red}{\text{CF1654F *2800}}\) 不会后缀排序怎么办。更准确地来说这道题用了后缀排序中倍增排序的思想，你会发现对于基准为 \(x\) 的排序可以分成两个子问题，即使得 \(x\) 和 \(x\oplus2^k\) 拼起来，其内部顺序在之前已经处理好了不用管，我们要做的就是找到最优的字典序最小的二元组，暴力排序就可以做到 \(O(n\log^2n)\)。更加书面地表达是我们进行 \(n\) 轮排序，每次用 \(\text{rk}_x\) 表示以 \(x\) 为基准排序后前 \(2^k\) 个字母最小的情况下在所有位置中的排名，下一轮借用这个值继续排序就可以了。
\(\color{red}{\text{CF1647F *3100}}\) 为什么呢。显然答案一定包含一个全局最大值，所以考虑枚举另一个顶点在哪里然后考虑 check。如果单纯来的话发现可能需要考虑 \(114514\) 种情况非常难受，此时需要用 \(f_{x,0/1}\) 表示一个点在第一个或者第二个序列中时另一个序列结尾的最值，然后就可以方便转移了，复杂度甚至的线性的。这种思路在把整个序列分成两个单调序列时很有用。但是感觉有些地方稍微有点绕，我是蛤蟆。
\(\color{cornflowerblue}{\text{CF1641D *2700}}\) 算是做出来的。按照 \(w\) 排序，对于每个值贪心地取最小的，判断上可以用 CDQZ 联考一样的方法容斥哈希去做，大概可以做到一些 \(\log\)。但是还有一个比较巧妙的点在于可以按 \(w\) 从小到大考虑，如果当前的决策点比上一次更靠右的话那么本轮是无效的，所以决策点具有单调性，借助 unordered_map 可以做到线性。
\(\color{red}{\text{CF1638F *3100}}\) 为什么呢。感觉有种说不出来的奇怪。枚举二者重合的区域，然后发现有效的区域只有 \(O(n)\) 种，对于每种进行一次 \(O(n)\) 的判定即可。感觉考的更多的是基本素养。可以这么认为。
\(\color{cornflowerblue}{\text{CF1650F *2200}}\) 水一个题。发现就是一个裸的背包问题，懒得写了。
\(\color{red}{\text{CF1654G *2900}}\) 太愚蠢了。考虑整个滑雪的过程，由于初始的机械能（也就是势能）是确定的，而且观察图发现一定存在一条路线使得势能可以完全转化成动能，所以我们要做的就是找个地方尽量消耗这些动能，显然这个地方应该尽量低，记为 \(h'x\)，那么一个点的答案应该是 \(2h_x-h'x\)。可以消耗动能的地方应该是个类似于平台的位置，而分析得到高度不同的平台数量不会太多（因为一个平台意味着两条不短的不交链的存在），所以可以对于每个高度求出哪些点可以合法地滑到这个地方，可以跑一个类似于最短路的东西，用 \(d_x\) 表示要从 \(x\) 到当前平台所需要的最少势能，分层用队列转移即可做到线性（是不是线性其实我不会分析，反正能过）。
\(\color{red}{\text{CF1637G *3000}}\) 当时打表已经得到了结论，即最后数列中的元素就是不小于 \(n\) 的 \(2\) 的整次数幂，但是构造的时候出了大问题，一开始想的是进行 \(k\) 轮，每轮通过一些操作使得每个数都是 \(2^k\) 的倍数，但是这样会在 \(n=65\) 的时候寄掉，想了一些奇怪的方法优化但是都没有什么结果。题解确实很巧妙，考虑尽量凑一些 \(2^t\)，那么会剩下两个部分，一个是小的未使用的数，一个是使用过的留下来的数，二者都构成了子问题，于是可以递归解决，但是感觉写起来像被撅了一样。多头给了一个很好的写法是说每次找最大的数，然后尝试凑整次数幂，这样也可以解决问题。要好写不少。
\(\color{red}{\text{CF1637F *2500}}\) 太愚蠢了，一开始纠结于初始的两个叶子的确定问题，结果方向压根就是错的。只需要更加形式地描述限制即可，以最大值为根，那么对于非根的点限制等价于子树内有不小于自己的叶子，而根的限制等价于子树内有至少两个不小于自己的叶子。非根的转移是容易的，如果孩子中已经有合法的叶子那自然很好，如果没有就考虑钦定一个叶子到自己的权值，显然钦定最大的那个孩子即可，所以维护 \(f_x\) 表示子树内最大的叶子就可以了。根同时维护次大即可。
\(\color{cornflowerblue}{\text{CF1628C *2300}}\) 炸鱼。黑白染色然后顺着染色即可。
\(\color{red}{\text{CF1635F *2800}}\) 说不定是可以想出来的，但是今晚时间实在不够了。钦定一个顺序，考虑让一对数在 \(w\) 更大的地方产生贡献，思考这样是否有什么性质。发现只有两边第一个比自己 \(w\) 小的位置才可能产生贡献，简单分析一下大小关系就能证明，于是离线排序树状数组维护即可，这不是和那个 U R wrong 场的重题一个路数吗。
\(\color{red}{\text{CF1637H *3500}}\) 牛逼炸了。
\(\color{cornflowerblue}{\text{CF1627F *2700}}\) 板子题。就考虑割开某条线所需要的代价，显然就是跨这根线的骨牌数量。由于所有中心对称的线都过正方形的中点，所以只需要每条线的代价算上对称点的代价后从中心点向边界点跑最短路即可。
\(\color{red}{\text{CF1611G *2500}}\) 事实证明我完全不会贪心。就有的时候贪心就是钦定一个顺序，由于当前的点只能在当前阶段选择，所以我们只需要在满足当前阶段合法的前提下尽量利好后面的阶段，经典的区间点覆盖贪心就是这样的。具体到这道题，阶段就是一条一条的左斜线，如果当前阶段不解决问题后面就无法解决了，所以只能一步步走下去；如果当前没有点了就可以考虑右拐了，然后贪心地解决后面阶段的问题即可。用 set 维护点的集合就好啦。
\(\color{red}{\text{CF1534F2 *3000}}\) 感觉还是很综合的一个题，我写了 6k 因为我是蛤蟆。建图，每个沙子向可以导致其掉落的沙子连边，稍微优化一下就能做到 \(O(n)\) 的边数。然后缩点，一个选择的沙子集合合法等价于选择的强连通分量可以通往所有包含恰好第 \(a_x\) 个沙子的强连通分量。去除那些无用的（可以被选中沙子到达的选中沙子）的强连通分量之后呢，发现每个点可以到达的选中沙子是一个区间，证明上考虑从扰动沙子的连续性思考。于是问题变成了给定一些区间，希望选出最少的区间覆盖整个数轴，按左端点排序之后贪心维护右端点的位置就可以了。
\(\color{red}{\text{CF1372E *2900}}\) 你好。观察到我们希望一些点尽量地在同一列，于是用 \(f_{l,r}\) 表示所有完全包含在 \([l,r]\) 中的区间能产生的最大贡献是多少。转椅上枚举中间点，然后找有哪些区间跨这个点，设数量为 \(a\)，那么此时的答案就是 \(f_{l,p-1}+f_{p+1,r}+a^2\)，随便优化一下就能做到 \(O(n^4)\) 的复杂度。有些贪心需要大胆猜想，比如这道题。
\(\color{cornflowerblue}{\text{CF1461F *2700}}\) 你好。不大不小的分类讨论题目。乘号和加号不同时出现的情况显然是平凡的，忽略掉。如果乘号和加号同时存在，那么显然会使用这两个符号。以零为界分段之后呢对于每一段进行考量，发现如果不存在 \(1\) 的话直接用乘号连接所有数就可以了，但是 \(1\) 的存在使得结论可能不成立。分析发现结论不成立的原因在于一堆 \(1\) 和某个数乘起来的结果还没有这堆 \(1\) 加起来的贡献大，而如若答案足够大，那么 \(1\) 把两边分开一定不优，所以只需要把除了两边的其它位置全部填上乘号即可；如果答案不够大，那么说明非 \(1\) 的数不够多，暴力 DP 即可。
\(\color{cornflowerblue}{\text{CF1209E2 *2500}}\) 隔座送钩春酒暖，分曹射覆蜡灯红。这就是前两天 ygg 让做的一个 T2，只不过那道题是搜索题这道题可能要用一点 DP。说回来，直接状压可以做到比较好的复杂度，然后贪心发现只需要取最前面一些数就可以做到最优解，所以复杂度就降到了一个可以接受的水平。
\(\color{red}{\text{CF1329E *3300}}\) 你需要有一定的观察力。对于一段长度为 \(x\) 的区间，如果指定其分成 \(c\) 段，那么一定会分出来 \(\lfloor\frac{x}{c}\rfloor\) 和 \(\lceil\frac{x}{c}\rceil\) 的一些段，而二者其实都是可以二分的。也就是说假如我们当前希望分出来的那些段中最大值不超过 \(R\)，最小值不超过 \(L\)，那么等价于对于每一段来说 \(\lfloor\frac{x}{c}\rfloor\ge L,\lceil\frac{x}{c}\rceil\le R\)，反过来描述限制就是 \(c\le\lfloor\frac{x}{L}\rfloor,c\ge\lceil\frac{x}{R}\rceil\)。发现二者的限制是独立的，所以可以二分得到一个可能不合法的粗略边界 \(L_0,R_0\)。如果 \(L_0\ge R_0\)，那么可以构造出一组答案为 \(0\) 的方案；如果 \(L_0<R_0\)，那么可能存在一些段无法被正确划分的情况，也就是 \(\lfloor\frac{x}{L_0}\rfloor<\lceil\frac{x}{R_0}\rceil\)，由于分子相同分母左小右大，只可能是右边比左边恰好大 \(1\)，只需要一边退让一个就可以了。问题转化成了有一些形如 \(l'\ge L\Rightarrow r'>R\) 的条件，排序即可。
\(\color{red}{\text{CF1257G *2600}}\) 你需要有更强的观察力，联考也考到了，也算是心有灵犀一点通了。问题变成了希望构造一些集合 \(p\) 使得不存在两个集合使得其中一个是另一个的子集。画图发现这是一个最长反链问题，转成最小链覆盖之后发现中间最宽的地方是无法优化的，所以答案应当就是 \(\binom{n}{n/2}\)。分析发现可重集也应当沿用这个结论。最后就是方案统计，暴力地直接分治加上 NTT 是可以通过的，而且跑得比较快。复杂度不明。
\(\color{red}{\text{CF1736E *2600}}\) 不完全做出来的。显然每轮产生贡献的位置是单调不降的，而且每轮的贡献很有可能和上一轮是一样的。然后需要做的就是用更加明晰的方式去描述这件事情，于是令 \(f_{x,p,k}\) 表示第 \(x\) 轮贡献位置为 \(a_p\) 并且用掉了 \(k\) 次机会的最大收益，考虑当前这一轮显然只有两种决策，一种是沿用上一次的贡献，这样会消耗一次机会；一种是从后面再找一个拎到当前位置来，会消耗距离次机会，列出方程发现可以简单地优化，复杂度是 \(O(n^3)\) 的。
\(\color{red}{\text{CF1844F2 *2800}}\) 结论大师。对于 \(c\ge 0\) 的情况显然直接一个升序的序列是最优的而且字典序最小；对于 \(c<0\) 的情况画图可知倒序的序列是一个数值上的最优解，于是有了 \(n^2\) 的做法，具体就是每次从小往大填，每次检查后半部分贪心填的情况下是否可以达到最优解；优化上考虑什么样是合法的，分析画图发现等价于不应该存在两个相邻的数落差大于给定的 \(|c|\)，否则在固定的 \(a_1-a_n\) 的基础上再多出一些代价显然不优，于是用 set 维护这个东西，每次找到合法（即删掉这个数之后两边的数不会因此变得落差过大）的最小的数，用链表维护修改即可。
\(\color{red}{\text{CF1428G2 *3000}}\) 诈骗大师，当时看了一下，什么 Div1+2 的 G2，还是个 \(3000\) 分黑题，完全不像是自己能想出来的。结果是个傻逼题。蛤蟆。如果取消所有限制的话只需要对比每个方案的性价比然后贪心地从高到低取就可以了，这启发我们可以拆贡献；如果加上一个最多选 \(t\) 个的限制的话等价于每个方案最多只能取 \(3t\) 次，做一次多重背包就可以了；如果再加上一个和恰好为 \(x\) 的限制，那么按照上面的方式选出来的答案可能不合法，所以提出来一次用于保证合法，然后每个方案按照 \(3(t-1)\) 的上界做背包就可以了。二进制拆分就可以了，跑得飞快。
\(\color{cornflowerblue}{\text{CF1827D *2800}}\) 终于遇到一个简单题了，你需要做的就是分析重心的一些性质。显然答案是一条边两边子树大小差的绝对值，这条边自然是连接树的重心和另一个点的。所以我们需要做的就是动态地维护重心的位置以及这个重心重儿子的大小，这是简单的，因为大多数时候重心并不会发生变化，如果发生变化重心只会朝着添加节点的方向移动一条边并且之前的重心一定是重儿子。于是用树状数组维护子树和就可以啦。
\(\color{cornflowerblue}{\text{CF1534E *2300}}\) 论洛谷的评分系统有多混乱。无解情况大概是容易的，考虑如何构造有解的情况。等价于每个位置被选中的次数都是奇数，所以初始地给每个位置一次选择的机会，然后顺次调整每个位置两次直到总和是 \(n\) 的倍数并且最大的数不超过理论取的次数。猜想这样的最优解，然后就可以通过这道题了。
\(\color{cornflowerblue}{\text{CF1391E *2600}}\) 还好。
\(\color{red}{\text{CF1993D *2800}}\) 有的时候应该勇于分治。
\(\color{cornflowerblue}{\text{CF1394D *2800}}\) 还好。
\(\color{red}{\text{CF1481F *3100}}\) 要会猜结论。
\(\color{cornflowerblue}{\text{CF1584F *2600}}\) 摆了。
\(\color{cornflowerblue}{\text{CF1539F *2600}}\) 完全没有写的欲望，甚至连解法都懒得描述了，放在这里只是为了尽快完成 kpi 凑数的。
\(\color{red}{\text{CF1292D *2700}}\) 甚至只需要暴力。
\(\color{red}{\text{CF1420E *2500}}\) 大脑停止思考了。
\(\color{red}{\text{CF1710C *2500}}\) 大脑不能用了。
\(\color{red}{\text{CF1764E *2500}}\) 缺乏贪心的基本素质。
\(\color{cornflowerblue}{\text{CF1697E *2400}}\) 为什么有紫啊。
\(\color{red}{\text{CF1776M *3000}}\) 比较震撼。
\(\color{red}{\text{CF1738G *2900}}\) 还是想到了一些东西的，但是由于基本素养不够没搞出来而且调了很久。
\(\color{red}{\text{CF1699E *2600}}\) 被撅惨了，脑子彻底锈住了。
\(\color{cornflowerblue}{\text{CF1428E *2200}}\) 菠萝吹水。
\(\color{cornflowerblue}{\text{CF1735E *2400}}\) 菠萝吹水。
\(\color{red}{\text{CF1693F *3400}}\) 比较牛。
\(\color{red}{\text{CF1700F *2600}}\) 贪心素养还是严重不够。
\(\color{red}{\text{CF1776I *2500}}\) 贪心素养仍然严重不足。
\(\color{cornflowerblue}{\text{CF1809F *2500}}\) 大菠萝吹水。
标签：cornflowerblue,color,text,可以,greedy2309,red,贪心 From： https://www.cnblogs.com/Feyn/p/17750968.html