各题型题解[updating]

4FGR2025-10-182025-11-20

各题型题解

算法基础

贪心

模拟

枚举

分治

排序

二分

P1182 数列分段 Section II - 洛谷

二分答案

构造

倍增

前缀和/差分

1526. 形成目标数组的子数组最少增加次数 - 力扣（LeetCode）

题目大意

问对初始全为0的序列，如果每次仅允许对[l,r]区间的所有元素加1，那么求出得到target数组的最少操作次数

我们知道对差分数组作前缀和能得到原数组。由于 target 是通过 $[l,r]$ 区间元素加 $1$ 得到的，target 的差分数组 diff 显然记录了这样的过程：

每次 $[l,r]$ 操作对应 $diff[l]+1$ 、 $diff[r+1]-1$
在操作结束后，对 diff 作前缀和操作，得到 target

我们要做的显然就是 “溯源”。

事实上，最少操作次数为其差分数组中正整数之和。

证明

显然正整数是操作的痕迹，想要做一次区间操作就不得不在 $diff[l]$ 加上 $1$ ，在 $diff[r+1]$ 处减去 $1$ ，显然差分数组每个正整数 $a$ 都代表有 $a$ 次操作从该位置开始。那么，负数，不会对这些产生影响吗？我们能保证绝不会有一次操作加在负数上，否则绝不会是最少操作解。因为要想加在负数上，只有对 $[l,r]$ 和 $[r+1,t]$ 分别做一次操作才能实现，显然只对 $[l,r]$ 做一次操作更为有效。

离散化

数据结构

堆

单调栈/队列

ST表

跳表

并查集

线段树

珂朵莉树

动态规划

背包DP

区间DP

树上DP

DAG的DP

状压DP

数位DP

插头DP

计数DP

图论

DFS

BFS

拓扑排序

最短路

二分图

哈密顿图

网络流

树链剖分

多项式与生成函数

快速傅里叶变换

快速数论变换

数论

素数/筛法

质因数分解

gcd/lcm

欧拉函数

费马小定理

模逆元

线性同余方程

中国剩余定理

莫比乌斯反演

其他

打表

2048. 下一个更大的数值平衡数 - 力扣（LeetCode）

由于 $n\leq 10^6$ ，数据较小，可直接枚举。为了实现更快的速度，我们枚举并同时记录每个平衡数，直到得到第一个大于 $10^6$ 的数值平衡数。然后二分打表即可。

int nextBeautifulNumber(int n) {
    vector<int> v = {1,22,122,212,221,333,1333,3133,3313,3331,4444,14444,22333,23233,23323,23332,32233,32323,32332,33223,33232,33322,41444,44144,44414,44441,55555,122333,123233,123323,123332,132233,132323,132332,133223,133232,133322,155555,212333,213233,213323,213332,221333,223133,223313,223331,224444,231233,231323,231332,232133,232313,232331,233123,233132,233213,233231,233312,233321,242444,244244,244424,244442,312233,312323,312332,313223,313232,313322,321233,321323,321332,322133,322313,322331,323123,323132,323213,323231,323312,323321,331223,331232,331322,332123,332132,332213,332231,332312,332321,333122,333212,333221,422444,424244,424424,424442,442244,442424,442442,444224,444242,444422,515555,551555,555155,555515,555551,666666,1224444};
    return *upper_bound(v.begin(),v.end(),n);
}