目录
- 写在前面
- CF1992F 贪心，数学 1900
- CF2008G 贪心，数学 1800
- CF2009G1 数据结构 1900
- CF 1891D 数学 1900
- CF1996F 二分，简单数学 1900
- CF1985G 数学 1600
- 写在最后
写在前面
简单题们。
以后可以用来搬。
唉唉现在 2000 及以下都能直接秒了真没意思。
CF1992F 贪心，数学 1900
显然直接贪心划分即可，主要问题是如何判断区间内子序列乘积恰好为 \(x\)。
发现 \(x\le 10^5\)，考虑对 \(x\) 质因数分解，在枚举区间时维护 \(x\) 中各质因数的数量即可。
CF2008G 贪心，数学 1800
发现给定过程即辗转相减，则最优的构造一定是 \(0, \operatorname{gcd}, 2\operatorname{gcd}, \cdots\)。然后就能直接算 \(\operatorname{mex}_k\) 了。
CF2009G1 数据结构 1900
首先套路地令 \(a_i:= a_i - i\)，则令区间变为公差为 1 的等差数列即令区间相等。
显然对于一个长度为 \(k\) 的区间应该调整成其中的众数，于是直接枚举所有长度为 \(k\) 的区间，记录区间内权值出现次数预处理即可。
CF 1891D 数学 1900
一眼题，发现 \(f\) 和 \(g\) 都是有非常显然的分段性质，\(f\) 至多只有 \(\log_2 v\) 段，在此基础上可知 \(g\) 至多只有 \(\log^2 v\) 段，大力枚举很容易就能处理出每一段的边界。
\(q=10^5\) 但是只有 1s，\(O(q\log^2 v)\) 不好跑，考虑预处理一下 \(1\sim 2^k - 1\) 的答案，则每次询问仅需考虑最后至多 \(\log v\) 段即可。
总时间复杂度 \(O\left(\log^2 v + q\log v\right)\) 级别。
会爆 LL 呃呃调红温了。
CF1996F 二分，简单数学 1900
看完题就想直接搞棵权值线段树，插入等差数列，然后在线段树上二分前 \(k\) 大之和即可。然而数据范围并不允许建树，失败！
虽然没法建树，但是发现二分权值区间是可以的。考虑从权值区间 \([L, R]\) 取前 \(k\) 大之和的答案，仅需检查左右子区间中数的个数与和再递归解决即可。
检查权值区间中数的个数与和显然能通过直接枚举每个元素 \(O(n)\) 直接算，则总时间复杂度为 \(O(n\log v)\) 级别。
CF1985G 数学 1600
发现给的限制 \(D(k\cdot n) = k\cdot D(n)\) 非常严格，当且仅当所有位均不出现进位才可满足。则可知对于 \(k\ge 10\) 答案一定为 0。
保证不进位则每位就是独立的了，可以计算出每位填的数的范围为 \(\left[0, \left\lfloor\frac{9}{k}\right\rfloor + 1\right]\)，又询问的区间端点均为 10 的幂，转化成前缀相减的形式就能非常简单地计算了。
写在最后
唉唉马上退役了。
标签：10,log,2000,数学,区间,杂题,1900,贪心 From： https://www.cnblogs.com/luckyblock/p/18411801