CSP 考前膜拜模版

0. 重要提示#

0.1 重定向输入输出#

1
int main(){
2
  freopen("decode.in","r",stdin);
3
  freopen("decode.out","w",stdout);
4
    // ...
5
    return 0;
6
}

0.2 文件目录#

0.3 试题#

CSP-J 2023

1. P3865 ST 表 #

题目描述#

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

输入格式#

第一行包含两个整数 $N,M$ ，分别表示数列的长度和询问的个数。

第二行包含 $N$ 个整数（记为 $a_i$ ），依次表示数列的第 $i$ 项。

接下来 $M$ 行，每行包含两个整数 $l_i,r_i$ ，表示查询的区间为 $[l_i,r_i]$ 。

输出格式#

输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。

样例 #1#

样例输入 #1#

1
8 8
2
9 3 1 7 5 6 0 8
3
1 6
4
1 5
5
2 7
6
2 6
7
1 8
8
4 8
9
3 7
10
1 8

样例输出 #1#

提示#

对于 $30\%$ 的数据，满足 $1\le N,M\le 10$ 。

对于 $70\%$ 的数据，满足 $1\le N,M\le {10}^5$ 。

对于 $100\%$ 的数据，满足 $1\le N\le {10}^5$ ， $1\le M\le 2\times{10}^6$ ， $a_i\in[0,{10}^9]$ ， $1\le l_i\le r_i\le N$ 。

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
inline int read()
4
{
5
  int x=0,f=1;char ch=getchar();
6
  while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
7
  while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
8
  return x*f;
9
}
10
const int maxn=1e6+5;
11
int n,m;
12
int a[maxn];
13
int st[maxn][(int)log2(maxn)+1];
14
int l,r;
15
int solve(int l,int r){
16
    return max(st[l][(int)log2(r-l+1)],st[r-(1<<int(log2(r-l+1)))+1][(int)log2(r-l+1)]);
17
}
18
int main(){
19
    n=read(),m=read();
20
    for(int i=1;i<=n;i++){
21
        a[i]=read();
22
        st[i][0]=a[i];
23
    }
24
    for(int j=1;j<=log2(n);j++){
25
        for(int i=1;i+(1<<(j-1))<=n;i++){
26
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
27
        }
28
    }
29
    while(m--){
30
        l=read(),r=read();
31
        cout<<solve(l,r)<<"\n";
32
    }
33
    return 0;
34
}

2. P4779 【模板】单源最短路径（标准版）#

题目背景#

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

$100 \rightarrow 60$ ；

$\text{Ag} \rightarrow \text{Cu}$ ；

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

题目描述#

给定一个 $n$ 个点， $m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

输入格式#

第一行为三个正整数 $n, m, s$ 。第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$ ，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

输出格式#

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

样例 #1#

样例输入 #1#

样例输出 #1#

1
0 2 4 3

提示#

样例解释请参考数据随机的模板题。

$1 \leq n \leq 10^5$ ；

$1 \leq m \leq 2\times 10^5$ ；

$s = 1$ ；

$1 \leq u_i, v_i\leq n$ ；

$0 \leq w_i \leq 10 ^ 9$ ,

$0 \leq \sum w_i \leq 10 ^ 9$ 。

本题数据可能会持续更新，但不会重测，望周知。

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
int n,m,s;
4
struct node{
5
    int a,val;
6
    bool operator < (node b) const{
7
        return val>b.val;
8
    }
9
};
10
vector <node> G[100010];
11
priority_queue <node> q;
12
int dis[100010];
13
int main(){
14
    cin>>n>>m>>s;
15
    int a,b,c;
16
    for(int i=1;i<=m;i++){
17
        cin>>a>>b>>c;
18
        G[a].push_back({b,c});
19
    }
20
    q.push({s,0});
21
    memset(dis,0x3f,sizeof dis);
22
    dis[s]=0;
23
    while(!q.empty()){
24
        node now=q.top();
25
        q.pop();
26
        if(now.val!=dis[now.a])continue;
27
        for(int i=0;i<G[now.a].size();i++){
28
            node nxt=G[now.a][i];
29
            if(dis[nxt.a]>dis[now.a]+nxt.val){
30
                q.push({nxt.a,dis[now.a]+nxt.val});
31
                dis[nxt.a]=now.val+nxt.val;
32
            }
33
        }
34
    }
35
    for(int i=1;i<=n;i++){
36
        cout<<dis[i]<<" ";
37
    }
38
    return 0;
39
}

3. P3366【模板】最小生成树 #

题目描述#

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式#

第一行包含两个整数 $N,M$ ，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$ ，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$ 。

输出格式#

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

样例 #1#

样例输入 #1#

样例输出 #1#

1
7

提示#

数据规模：

对于 $20\%$ 的数据， $N\le 5$ ， $M\le 20$ 。

对于 $40\%$ 的数据， $N\le 50$ ， $M\le 2500$ 。

对于 $70\%$ 的数据， $N\le 500$ ， $M\le 10^4$ 。

对于 $100\%$ 的数据： $1\le N\le 5000$ ， $1\le M\le 2\times 10^5$ ， $1\le Z_i \le 10^4$ 。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$ 。

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
int n,m;
4
int x,y,z;
5
const int maxn=5010;
6
struct ed{
7
    int val,x,y;
8
};
9
vector <ed> edges;
10
bool cmp(ed x,ed y){
11
    return x.val<y.val;
12
}
13
int numberOfEdges=0;
14
int fa[maxn];
15
int find(int x){
16
    return fa[x]==x?x:fa[x]=find(fa[x]);
17
}
18
void merge(int x,int y){
19
    int fax=find(x),fay=find(y);
20
    if(fax!=fay){
21
        fa[fax]=fay;
22
    }
23
}
24
int main(){
25
    cin>>n>>m;
26
    for(int i=1;i<=n;i++){
27
        fa[i]=i;
28
    }
29
    for(int i=1;i<=m;i++){
30
        cin>>x>>y>>z;
31
        if(x==y)continue;
32
        edges.push_back({z,x,y});
33
    }
34
    int ans=0;
35
    sort(edges.begin(),edges.end(),cmp);
36
    for(auto i:edges){
37
        int fax=find(i.x),fay=find(i.y);
38
        if(fax!=fay){
39
            numberOfEdges++;
40
            merge(i.x,i.y);
41
            ans+=i.val;
42
        }
43
    }
44
    if(numberOfEdges!=n-1){
45
        cout<<"orz"<<endl;
46
        return 0;
47
    }
48
    cout<<ans;
49
    return 0;
50
}

4. 【模板】树状数组 1#

题目描述#

如题，已知一个数列，你需要进行下面两种操作：

将某一个数加上 $x$
求出某区间每一个数的和

输入格式#

第一行包含两个正整数 $n,m$ ，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

1 x k 含义：将第 $x$ 个数加上 $k$
2 x y 含义：输出区间 $[x,y]$ 内每个数的和

输出格式#

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

【数据范围】

对于 $30\%$ 的数据， $1 \le n \le 8$ ， $1\le m \le 10$ ；
对于 $70\%$ 的数据， $1\le n,m \le 10^4$ ；
对于 $100\%$ 的数据， $1\le n,m \le 5\times 10^5$ 。

数据保证对于任意时刻， $a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $[-2^{31}, 2^{31})$ 范围内。

样例说明：

故输出结果14、16

代码#

1
#include<cstdio>
2
#include<iostream>
3
using namespace std;
4
const int maxn=5e5+10;
5
int n,m;
6
int a[maxn];
7
int bit[maxn];
8
int k,x,y;
9
int lowbit(int x){
10
    return x & -x;
11
}
12
void change(int x,int y){
13
    while(x<=n){
14
        bit[x]+=y;
15
        x+=lowbit(x);
16
    }
17
}
18
int query(int x){
19
    int ans=0;
20
    while(x>0){//边界条件x>0!
21
        ans+=bit[x];
22
        x-=lowbit(x);
23
    }
24
    return ans;
25
}
26
int main(){
27
    cin>>n>>m;
28
    for(int i=1;i<=n;i++){
29
        scanf("%d",&a[i]);
30
        change(i,a[i]);//一开始都是0，要初始化加上a[i]
31
    }
32
    for(int i=1;i<=m;i++){
33
        scanf("%d%d%d",&k,&x,&y);
34
        if(k==1){
35
            change(x,y);//将第x个数加上y
36
        }else{
37
            printf("%d\n",query(y)-query(x-1));//求出区间和
38
        }
39
    }
40
    return 0;
41
}

5. 【模板】树状数组 2#

题目描述#

如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 $x$ ；
求出某一个数的值。

输入格式#

第一行包含两个整数 $N$ 、 $M$ ，分别表示该数列数字的个数和操作的总个数。

第二行包含 $N$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $M$ 行每行包含 $2$ 或 $4$ 个整数，表示一个操作，具体如下：

操作 $1$ ：格式：1 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$ ；

操作 $2$ ：格式：2 x 含义：输出第 $x$ 个数的值。

输出格式#

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

样例 1 解释：#

故输出结果为 6、10。

数据规模与约定#

对于 $30\%$ 的数据： $N\le8$ ， $M\le10$ ；

对于 $70\%$ 的数据： $N\le 10000$ ， $M\le10000$ ；

对于 $100\%$ 的数据： $1 \leq N, M\le 500000$ ， $1 \leq x, y \leq n$ ，保证任意时刻序列中任意元素的绝对值都不大于 $2^{30}$ 。

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int maxn=5e5+10;
4
int a[maxn];
5
int bit[maxn];
6
int n,m;
7
int cmd,x,y,k;
8
// 差分思想，用bit[x]表示第i个数
9
int lowbit(int x){
10
    return x&-x;
11
}
12
void add(int x,int y){
13
    while(x<=n){
14
        bit[x]+=y;
15
        x+=lowbit(x);
16
    }
17
}
18
int query(int x){
19
    int ans=0;
20
    while(x>0){//边界条件x>0!
21
        ans+=bit[x];
22
        x-=lowbit(x);
23
    }
24
    return ans;
25
}
26
int main(){
27
    cin>>n>>m;
28
    for(int i=1;i<=n;i++){
29
        cin>>a[i];
30
        add(i,a[i]);
31
        add(i+1,-a[i]);
32
    }
33
    for(int i=1;i<=m;i++){
34
        cin>>cmd;
35
        if(cmd==1){
36
            cin>>x>>y>>k;
37
            add(x,k);
38
            add(y+1,-k);
39
        }else{
40
            cin>>x;
41
            cout<<query(x)<<endl;
42
        }
43
    }
44
    return 0;
45
}

6. 【模板】线段树 1#

题目描述#

如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 $k$ 。
求出某区间每一个数的和。

输入格式#

第一行包含两个整数 $n, m$ ，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1 x y k：将区间 $[x, y]$ 内每个数加上 $k$ 。
2 x y：输出区间 $[x, y]$ 内每个数的和。

输出格式#

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

对于 $30\%$ 的数据： $n \le 8$ ， $m \le 10$ 。
对于 $70\%$ 的数据： $n \le {10}^3$ ， $m \le {10}^4$ 。
对于 $100\%$ 的数据： $1 \le n, m \le {10}^5$ 。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$ 。

【样例解释】

代码#

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4
const int maxn=8e5+10;
5
int tree[maxn];
6
int lazy[maxn];
7
int n,m;
8
void push_up(int p){
9
    tree[p]=tree[p*2]+tree[p*2+1];
10
}
11
void push_down(int p,int l,int r){
12
    lazy[p*2]+=lazy[p];
13
    lazy[p*2+1]+=lazy[p];
14
    int mid=(r+l)/2;
15
    tree[p*2]+=lazy[p]*(mid-l+1);
16
    tree[p*2+1]+=lazy[p]*(r-mid);
17
    lazy[p]=0;
18
}
19
void build(int s,int t,int p){
20
    if(s==t){
21
        cin>>tree[p];
22
        return;
23
    }
24
    int mid=(s+t)/2;
25
    build(s,mid,p*2);
26
    build(mid+1,t,p*2+1);
27
    push_up(p);
28
}
29
void update(int l,int r,int s,int t,int p,int v){
30
    if(l<=s&&t<=r){
31
        lazy[p]+=v;
32
        tree[p]+=v*(t-s+1);
33
        return;
34
    }
35
    push_down(p,s,t);
36
    int mid=(s+t)/2;
37
    if(mid>=l)
38
        update(l,r,s,mid,p*2,v);
39
    if(mid<r)
40
        update(l,r,mid+1,t,p*2+1,v);
41
    push_up(p);
42
}
43
int query(int l,int r,int s,int t,int p){
44
    if(l<=s&&t<=r){
45
        return tree[p];
46
    }
47
    int mid=(s+t)/2;
48
    int ans=0;
49
    push_down(p,s,t);
50
    if(mid>=l){
51
        ans+=query(l,r,s,mid,p*2);
52
    }
53
    if(mid<r){
54
        ans+=query(l,r,mid+1,t,p*2+1);
55
    }
56
    return ans;
57
}
58
signed main(){
59
    cin>>n>>m;
60
    build(1,n,1);
61
    while(m--){
62
        int op,x,y,z;
63
        cin>>op;
64
        if(op==1){
65
            cin>>x>>y>>z;
66
            update(x,y,1,n,1,z);
67
        }else{
68
            cin>>x>>y;
69
            cout<<query(x,y,1,n,1)<<endl;
70
        }
71
    }
72
    return 0;
73
}

0. 重要提示#

0.1 重定向输入输出#

0.2 文件目录#

0.3 试题#

1. P3865 ST 表#

题目描述#

输入格式#

输出格式#

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

代码#

2. P4779 【模板】单源最短路径（标准版）#

题目背景#

题目描述#

输入格式#

输出格式#

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

代码#

3. P3366【模板】最小生成树#

题目描述#

输入格式#

输出格式#

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

代码#

4. 【模板】树状数组 1#

题目描述#

输入格式#

输出格式#

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

代码#

5. 【模板】树状数组 2#

题目描述#

输入格式#

输出格式#

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

样例 1 解释：#

数据规模与约定#

代码#

6. 【模板】线段树 1#

题目描述#

输入格式#

输出格式#

样例 #1#

样例输入 #1#

样例输出 #1#

提示#

代码#

支持与分享

评论区

目录

1. P3865 ST 表 #

3. P3366【模板】最小生成树 #