CF1773H - Hot and Cold \(\text{diff:}2600\)
询问 \((x, y)\) 和 \((x + 1, y)\) 和 \((x + 1, y + 1)\) 即可将 \(x,y\) 坐标的范围减半，然后可以在 \(3\log _ 2 10^6 = 60\) 次询问左右解决这个问题。
CF725F - Family Photos \(\text{diff:}2900\)
发现有些东西 \(A,B\) 都不会选，扔掉，有些东西只有 \(A\) 或者 \(B\) 会选，直接加上权值。
此外的东西都是两者想要争取的，将其按照 \(a + b\) 排序，那么从前向后取就是最优的，证明考虑临项交换。
重在简化题意，从而套用经典的贪心。
二分中位数，求最大字段和即可。
gym104768G - Hard Brackets Problem
小细节题，发现前面大多数都是照抄，唯一的区别在于如果后面的一组括号是匹配的，那么可以省去一些右括号。
gym104768K - Randias Permutation Task
从 \(nm \le 180\) 入手数据点分治一下。
\(m \le 18\) 的时候，直接 \(\mathcal{O}(n^2 2^m)\) 暴力搜索即可。
\(m > 18\) 的时候 \(n < 10\)，那么排列数量很少，直接 DP 即可。
转化为求区间种类数 - mex 的最大值。
直接扫描线加上势能线段树即可，先计算 \([1, i]\) 的答案，然后删去 \(a_1\)，变成 \([2, i]\)，依此类推。
发现把最大值对齐就好了，然后为了在 \(n-m\) 次内做好，需要一些冗余操作，这个可以通过每次选最小值得到，可以线段树上二分（可能有更简单的做法）。
感觉现在缺乏的是思维上的方向和技巧，NOIP 前还是专心这一块。
CF1375G - Tree Modification \(\text{diff:}2800\)
考虑弱化性质。
题目给的是树，但是操作改变了树的形态，不方便 DP 之类，但是树是二分图，从二分图染色的角度分析容易发现答案就是黑白点个数的最小值减一。
这种思想在 CF1149C 也有提到，不考虑要求的直径，只是考虑所有的链。
CF461D - Appleman and Complicated Task \(\text{diff:}2800\)
首先观察到第一行确定就能确定整个图，那么每个限制都映射到第一行上的一个区间内的奇（偶）数，分开奇偶，利用并查集统计答案即可。
CF1408G - Clusterization Counting \(\text{diff:}2700\)
题目给了一个很怪的限制，组内边小于组外边，按值从小到大加入边，思考一下可以得到一个东西能被划分出来当且仅当这是个团。
计数的话考虑上述过程还可以求出其 Kruskal 重构树，那么就是一个子树。
CF1767E - Algebra Flash \(\text{diff:}2500\)
最小权点覆盖等于总和减去最大权独立集。
然后使用 Meet-in-Middle 求解即可。
CF1422F - Boring Queries \(\text{diff:}2700\)
对于小于根号的数字直接稀疏表维护最大值即可。
对于大于根号的情况，一个数字至多有一个这样的因子，那么相当于区间内不同数字的乘积，使用主席树区间乘法，单点查询即可。
区间乘法用标记永久化代替。
CF580E - Kefa and Watch \(\text{diff:}2500\)
字符串 \(s[l,r]\) 循环节长度为 \(x\)，等价于 \(s[l,r-x]=s[l+x,r]\)。
CF1371F - Raging Thunder \(\text{diff:}2800\)
线段树维护反转的简单方法是对于正反各自维护信息，操作时交换即可。
标签：二分,text,笔记,即可,区间,diff,2800 From： https://www.cnblogs.com/z-t-rui/p/18541366