\textsf{思维训练}
eg1: 最大公约数
要求在 [l, r] 内寻找两个数 x, y, 使得 l \le \gcd(x, y) \le r
solution :
x, y 均为 \gcd(x, y) 的倍数
那么考虑 极限情况
x = \gcd(x, y), \ y = 2 \times \gcd(x ,y)
故只需考虑 2l 是否小于等于 r 即可
eg2: P9345 夕阳西下几时回
夕阳可以被视作由 n 种不同颜色组成的一副图，其中第 i 种的颜色为 a_i ，满足 a 是长度为 n 的排列。
定义一个排列的乡愁度为：
- 对于所有 1\le i \le n ，记 b_i=\gcd(a_i,a_{i+1}) 。特别地，我们认为 a_{n+1}=a_1 。
- 排列 a 的乡愁度为序列 b 中不同元素的个数。
求是否有一个长度为 n ，乡愁度为 k 的排列 p 。若有解，请输出任意一个排列。
对于 100\% 的数据， 1\le T\le 10^5 ， 3\le n\le 3\times 10^5 ， 1\le k\le n ， \sum n \le 6\times 10^5 。
solution :
在 [1, n] 任取两个数 x, y, \gcd(x, y) 最大为 [\frac{n}{2}]
{1, 2, 4, ...} {3, 6, 12, ...} {5, 10, 20, ...}
- 我们可以使每个数挨着它的两倍， 直到 [1, k] 均被取到
- 对于剩下 [2k + 1, n] 放在 1， 2 之间
eg3. P3566 [POI2014] KLO-Bricks
sulution :
- 简单想到这是一个贪心。
- 每次取当前数目最多的那个数，将它放在当前位上。
- 如果有多个数目相同的数，那优先取最后一个数。（避免重复）
- 那这就好做了。数目可以用堆来维护。
eg4: CF1217D Coloring Edges
solution :
- 拓扑排序， 取出的所有边标 0
当不存在入度为 0 的点， 任取一个入度为 1 的点将其入边标1
-
dfs, 树边标 0, 返祖边标 1, 横向边任意
图上的环一定由树边和返祖边组成
-
给所有点编号， 从大到小的标 1, 从小到大的标 0.
eg5: CF1304D Shortest and Longest LIS
solution :
- 首先考虑构造最短的 \operatorname{LIS} 。
容易发现此时答案的下界是连续相邻 < 的长度的最大值。现在我们尝试达到这个最大值。
我们可以这么构造：首先让这个排列等于 n, n - 1, ... 2, 1
然后对于一段连续的 < ，我们直接把对应的位置翻转。
这样对于任意两个位置 i < j ，
除非这两个位置位于一段连续的 < 对应的区间之内，
否则一定满足 a_i > a_j 。可以发现这样构造出的 \operatorname{LIS} 一定是最短的。
- 然后我们考虑构造最长的 \operatorname{LIS} 。
有了上面的思考过程，这次我们只需要让这个排列初始等于 1, 2, 3 , ..., n
然后翻转所有连续的 > 对应的区间。
这样对于任意两个位置 i < j ，
除非这两个位置位于一段连续的 > 对应的区间之内，
否则一定满足 a_i > a_j 。
因此这样构造出的 \operatorname{LIS} 一定是最长的。
eg6: P7428 [THUPC2017] 母亲节的礼物
solution :
调整构造
-
首先，将颜色编号为 0 - 3 ，
-
然后，找出所有不满足要求的点，加入队列。
每次从队首取一个点。如果这个点已经满足要求就不去动它，
- 否则，将它的颜色改成所有与它直接相连的点的中最稀有的颜色。
依据容斥原理，我们可以证明，
这个颜色在周围只有 1 个或者 0 个点拥有。
-
改完颜色后，要判断所有与之相连的点有哪个或哪些不满足要求，压入队列。
-
队列为空时，答案就出来了。
eg7 :[AGC017B] Moderate Differences
-
范围转化为最值
-
枚举加号数
-
得到等式， 两边同减若干个 C
-
得到 LHS 值的范围
-
查看 RHS 值在不在这个范围
eg8. [ARC113D] Sky Reflector
solution :
A_i \le G_{i,j} \le B_j
即 A_i\le B_j
即 \max(A) \le \min(B)
设 A 中最大值为 t
A : t ^n + (t - 1) ^ n \ \ B : (k - t +1) ^ n
ans = (t ^n + (t - 1) ^ n ) \times (k - t +1) ^ n