各题型题解[updating]

4FGR2025-10-182026-05-25

各题型题解

算法基础

贪心

模拟

枚举

分治

排序

二分

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表

跳表

并查集

线段树

珂朵莉树

P4979 矿洞：坍塌 - 洛谷

题目大意

对于给出的一字符串s，仅存在三种三种元素：{A,B,C}，对于此字符串，我们想要做如下两种操作： 1. 当flag = A时，给出x,y,op,修改区间[x,y]的所有元素为op。 2. 当flag = B时，给出x,y,查询区间是否"合法" 一个区间合法的标志是：[x,y]区间的元素均相同，且第x-1号元素和第y+1号元素并不相同

这里给出珂朵莉树的解法，实现上采用 std::set ，保留经典操作 split 和assign ，此时如果直接暴力查询，则能得到90分，剩下10分考虑算法优化。

显然，珂朵莉树适用于数据集随机的情况，但此题显然B型操作过多。我们知道当存在大量不同区间时，珂朵莉树从理想下的 $O(m\log \log n)$ 趋近于平方级。考虑题重要的一点：元素仅存在三种。说明大量不同区间实际上是可以合并的，比如assign 操作后可能新区间能与邻居区间合并，于是选择在assign 采用 union 操作。虽然时间仍差了一步，但 union 带来的惊喜是，显然相同值的连续区间一定能被一个结点表示，那么就可以优化查询操作（这是最重要的），即得到大于 x 的第一个结点的前驱 itl，大于 y 的第一个结点的前驱 itr ，那么显然itl 和 itr 是一定包含 l 和 r 的。于是我们知道:

itl!=itr ，说明 $[l,r]$ 区间值不全相同，返回 $false$
itl-l < l && itr>r 说明 $x-1$ 和 $y+1$ 的值相同，非法，返回 $false$
如果结点只包含 $[l,r]$ 检查 $prev(itl) == next(itr)$ ，如果成立，非法，返回 $false$
其余返回 $true$

#include<bits/stdc++.h>

using namespace std;

struct node{
    int l,r;
    mutable char v;
    node(const int &il,const int &ir,const char &iv): l(il),r(ir),v(iv){}
    bool operator<(const node &o) const{return l<o.l;}
};

set<node> odt;

void initial(int N){
    odt.insert(node(1,N+1,'#'));
}

auto split(int x){
    auto it = odt.lower_bound(node(x,0,0));
    if(it!=odt.end()&&it->l==x) return it;
    it--;
    int l=it->l,r=it->r;char v=it->v;
    odt.erase(it);
    odt.insert(node(l,x-1,v));
    return odt.insert(node(x,r,v)).first;
}

auto find(int x){
    return odt.upper_bound(node(x,0,0));
}

void merge(set<node>::iterator a){ //查看是否能合并周围结点，如果能就合并
    auto l = a,r = next(a);
    if(prev(a)->v == a->v){
        l = prev(a);
    }
    if(next(a)->v == a->v){
        r = next(r);
    }
    if(next(l) != r){
        int il = l->l,ir = prev(r)->r,iv = l->v;
        odt.erase(l,r);
        odt.insert(node(il,ir,iv));
    }
    
}

void assign(int l,int r,char v){
    auto itr = split(r+1);
    auto itl = split(l);
    odt.erase(itl,itr);
    auto it = odt.insert(node(l,r,v)).first;
    merge(it);
}

bool isLegal(int l,int r){
    auto itr = prev(find(r)),itl=prev(find(l)); // 左端点<=r 和<=l的区间 

    if(itr != itl) return false; //[l,r]区间里不止一个区间（值）
    else{
        if(itl->l < l && itr->r > r) return false; //两边值一样
        else if(itl->l == l && itr->r == r){
            if(prev(itl)->v == next(itr)->v) return false;
            else return true;
        }
        return true;
    }
}



int main(){
    int N;
    cin >> N;
    initial(N);
    char a[N+1];
    for(int i=1;i<=N;i++) {
        cin >> a[i];
    }
    for(int i=1;i<N;i++){
        int l = i;
        while(a[i] == a[i+1]){
            i++;
        }
        assign(l,i,a[i]);
    }
    int k;
    cin >> k;
    while(k--){
        char flag;
        cin >> flag;
        if(flag == 'A'){
            int x,y;
            char op;
            cin >> x >> y >> op;
            assign(x,y,op);
        }else{
            int x,y;
            cin >> x >> y;
            bool flag = isLegal(x,y);
            if(flag) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

K-D树

动态规划

背包DP

0-1/完全/混合背包

分组背包

二维费用背包

依赖背包

区间DP

树型DP

树上背包

换根DP

DAG的DP

状压DP

数位DP

插头DP

计数DP

图论

DFS

BFS

拓扑排序

最短路

最小生成树

二分图

哈密顿图

网络流

树链剖分

组合数学

错位排列

P1595 信封问题 - 洛谷

假设考虑到第 $n$ 个信封，初始时暂时把第 $n$ 封信放在第 $n$ 个信封中，然后考虑两种情况的递推关系 $D_n$：

前面 $n-1$ 个信封全部装错，这种情况的出现次数为 $D_{n-1}$
前面 $n-1$ 个信封仅有一个没有装错，这种情况的出现次数为 $C_{n-1}^{1}D_{n-2}$

对于第一种情况，前面 $n-1$ 个信封全部装错，所以第 $n$ 封只需要与前面任一一个位置交换即可，总共有 $D_{n-1}\times (n-1)$。

对于第二种情况，只要将那个没装错的信封和第 $n$ 封交换位置即可。

其他情况，不可能通过一次操作来把它变成一个长度为 $n$ 的错排。

于是可得，错位排列数满足递推关系： \[ D_n = (n-1)(D_{n-1}+D_{n-2}) \] 这里也给出另一个递推关系： \[ D_n=nD_{n-1}+(-1)^n \] 其中，$D_0=D_1=0$ ，$D_2=1$ 为递推边界。

容斥原理

数论

素数/筛法

质因数分解

欧拉函数

模逆元

线性同余方程

中国剩余定理

数论分块

Pollard Rho 算法

莫比乌斯反演

码蹄集OJ-惊马示警擒义士

设 $f(d)$ 为 $\gcd(B)=d$ 时，满足 $B\subseteq A$ 的集合 $B$ 个数，即 \[ f(d) = \sum_{B\subseteq A} [\gcd(B)=d] \] 不妨设 $F(d)$ 为 $d\mid \gcd(B)$ 时，满足 $B\subseteq A$ 的集合 $B$ 个数，则有 \[ F(d) = \sum_{d|c} f(c) \] 不难发现，当 $A$ 中出现了 $d$ 的倍数的个数为 $cnt_d$ ，由于使得 $d|\gcd(B)$ 的集合只能包含 $d$ 的倍数，排除空集，则有： \[ F(d)=2^{cnt_d}-1 \] 利用莫比乌斯反演，得到 \[ F(d)=\sum_{d\mid c}f(c)\Leftrightarrow f(d)=\sum_{d\mid c}\mu(\frac{c}{d})F(c) = \sum _{d\mid c}\mu(\frac{c}{d})(2^{cnt_c}-1) \] 带入 $d=\gcd(A)$ 即可

#include<bits/stdc++.h> 

using namespace std;
#define int long long
const int P = 1e9+7;
const int N = 1e6+10;
int a[N];
int mu[N]; // Mobius
int isprime[N];
vector<int> prime;
int n;
int cnt[N]; // A中被d*i整除的个数

void euler(){ // 欧拉筛预处理Mobius函数
    mu[1] = 1;
    for(int i=2;i<N;i++){
        if(!isprime[i]){
            prime.push_back(i);
            mu[i] = -1;
        }
        for(auto &j:prime){
            if(i*j>=N) break;
            isprime[i*j] = 1; // 标记非素数
            if(i%j==0){
                mu[i*j] = 0;
                break;
            }else{
              mu[i*j] = -mu[i];
            }
        }
    }
}

int qpow(int a,int p){ // 快速幂a^p
    int res = 1;
    while(p){
        if(p&1) res = res*a%P;
        a = a*a%P;
        p>>=1;
    }
    return res;
}

void solve(){
    int d = a[0]; // 计算集合A的最大公约数
    int p = 0; // A中被d整除的最大倍数
    for(int i=1;i<n;i++){
        d=gcd(d,a[i]);
    }
    for(int i=0;i<n;i++){ // 统计被d*t整除的元素个数
        p = max(p,a[i]/d);
        cnt[a[i]/d]++;
    }
    int ans = 0;
    // Mobius反演
    for(int c=1;c<=p;c++){
        if(!mu[c]) continue;
        int total = 0; // A中被d整除的个数
        for(int j=c;j<=p;j+=c){ // 类调和级数，实际总循环次数不大
          total += cnt[j];
        }
        ans = (ans+(mu[c]*(qpow(2,total)-1)%P+P)%P)%P;
    }
    cout << ans;
}

signed main( )
{
    euler();
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    solve();
    return 0;
}

字符串

后缀函数

计算几何

其他

打表

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);
}