devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

模板综合2_所有普及提高模板

作者：你好赵伟 | 2024-08-17 17:51:50

赞

踩

所有普及提高模板

部分算法模板（普及/提高-）

9.单调队列/滑动窗口 || 难度：普及/提高-

有一个长为 n n n 的序列 a a a，以及一个大小为 k k k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。


很不错的题解

#include<iostream>
#include<deque>
using namespace std;
long long n,k,a[1000005];
long long zhizhen;
deque<int> de;
template <typename T> void read(T &x){
	x = 0;
	bool f = 0;
	char c = getchar();
	while (c < '0' || c > '9') f |= c == '-', c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	if (f) x = -x;
}
template <typename T> void write(T x){
	if (x < 0) putchar('-'), x = -x;
	if (x < 10) putchar(x + '0');
	else write(x / 10), putchar(x % 10 + '0');
}
int main(){
	zhizhen=0;
	read(n),read(k);
	for(int i=0;i<n;i++){
		read(a[i]);
	}
	for (int i=0;i<n;i++){
		while(!de.empty()&&de.back()>=a[i]){
			de.pop_back();
		}
		de.push_back(a[i]);
		if(i-zhizhen>=k&&a[zhizhen]==de.front()){
			zhizhen++;
			de.pop_front();
		}
		if(i-zhizhen>=k&&a[zhizhen]!=de.front()){
			zhizhen++;
		}
		if(i>=k-1){
			write(de.front());
			cout<<" ";
		}
	}
	cout<<"\n";
	de.clear();
	zhizhen=0;
	for (int i=0;i<n;i++){
		while(!de.empty()&&de.back()<=a[i]){
			de.pop_back();
		}
		de.push_back(a[i]);
		if(i-zhizhen>=k&&a[zhizhen]==de.front()){
			zhizhen++;
			de.pop_front();
		}
		if(i-zhizhen>=k&&a[zhizhen]!=de.front()){
			zhizhen++;
		}
		if(i>=k-1){
			write(de.front());
			cout<<" ";
		}
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

10.ST表 || 难度：普及/提高-

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



以上内容选自这篇极不错的题解。

#include<cstdio>
#include<algorithm>
#define max(x,y) (x>y)?x:y
using namespace std;
int a[100005];
int b[100005]={-1};
int maxx[100005][50];
int n,m,l,r;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=b[i/2]+1;
        maxx[i][0]=a[i];
    }
    for(int i=1;i<=b[n];i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            maxx[j][i]=max(maxx[j][i-1],maxx[j+(1<<(i-1))][i-1]);
        }
    }
    while(m--){
        scanf("%d%d",&l,&r);
        int len=b[r-l+1];
        printf("%d\n",max(maxx[l][len],maxx[r-(1<<(len))+1][len]));
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
'
运行

11. 链式前向星 || 难度：未知

#include<iostream>
using namespace std;
int n,m,u,v,tot,head[1001];
bool vis[1001];
struct edge{
    int u,v,next;
}g[1001];
void addedge(int u,int v){
    g[++tot].u=u;
    g[tot].v=v;
    g[tot].next=head[u];
    head[u]=tot;
}
void dfs(int u){
    cout<<u<<" ";
    vis[u]=true;
    for(int i=head[u];i!=-1;i=g[i].next){
        int v=g[i].v;
        if(!vis[v]) dfs(v);
    }
}
int main(){
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;++i){
        cin>>u>>v;
        addedge(u,v);
 //     addedge(v,u);
    }
    for(int i=1;i<=n;++i){
        if(!vis[i]) dfs(i);
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

12.拓扑排序 || 难度：未知

#include<iostream>//拓扑排序 
#include<vector>
#include<queue>
using namespace std;
int n,m,in[1001];
//in[i]:点i的入度 
vector<int> g[1001];
void tpsort(){//拓扑排序函数 
    queue<int> q;
    for(int i=1;i<=n;++i) 
        if(!in[i]) q.push(i);//将入度为0的点加入queue 
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<g[u].size();++i){//删边 
            int v=g[u][i];
            --in[v];
            if(!in[v]) q.push(v);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        ++in[v];
        g[u].push_back(v);
    }
    tpsort();
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

13.三分法 || 难度：普及/提高-

题意：
给出一个 N N N 次函数，保证在范围 [ l , r ] [l, r] [l,r] 内存在一点 x x x，使得 [ l , x ] [l, x] [l,x] 上单调增， [ x , r ] [x, r] [x,r] 上单调减。试求出 x x x 的值

  • 第一行一次包含一个正整数 N N N 和两个实数 l , r l, r l,r,含义如题目描述所示。
  • 第二行包含 N + 1 N + 1 N+1 个实数，从高到低依次表示该 N N N 次函数各项的系数
原理：

三分其实是每次取 L , R L,R L,R 的终点 m i d mid mid，把 m i d mid mid 左边一点点的函数值和右边一点点的函数值比较，舍弃一边的区间，这样不断缩小区间直到满足精度要求(一般 e p s eps eps 取 0.1 0.1 0.1 精度)，但我们都喜欢取三等分点，其实只要是左边一点点和右边一点点就行了。

多项式求值还有个秦九韶算法，可以把 2 n + 1 2n+1 2n+1 次乘法 n n n 次加法简化为 n n n 次乘法和 n n n 次加法。

三分

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7;//其实一般精度*0.1=1e-6就可以了
int n;
double L,R;
double a[15];
//普通的求多项式
//秦九韶算法从里到外逐层计算一次多项式的值
double F(double x){
    double sum=0;
    for(int i=n;i>=0;i--) sum=sum*x+a[i];
    return sum; 
}
int main(){
    cin>>n>>L>>R;
    for(int i=n;i>=0;i--) cin>>a[i];
    while(fabs(L-R)>=eps){
        double mid=(L+R)/2;
        if(F(mid+eps)>F(mid-eps)) L=mid;//舍弃左区间
        else R=mid;//舍弃右区间
    }
    printf("%.5lf",R);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

14.树状数组 || 难度：普及/提高-

(1)数状数组1

题意：
第一行包含两个正整数 n , m n,m n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n n n 个用空格分隔的整数，其中第 i i i 个数字表示数列第 i i i 项的初始值。
接下来 m m m 行每行包含 3 3 3 个整数，表示一个操作，具体如下：

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

其中 l o w b i t lowbit lowbit 指：

一个数的二进制表示中最右边 11 11 11 所对应的值
或者说：
l o w b i t = 2 k lowbit=2^k lowbit=2k
, k k k 为一个数的二进制表示中末尾 0 0 0 的个数。

树状数组就是由 l o w b i t lowbit lowbit 分段的一种数据结构，它的每一个节点管一个区间，存的是这个节点管的区间的最大值。

修改：

模板：

#include<bits/stdc++.h>
using namespace std;
const int Maxn=500005;
int n,s[Maxn],m;
int lowbit(int x){
    return x&(-x);
}
struct node{
    int c[Maxn];
    void add(int x,int d){//修改
        s[x]+=d;
        for(int i=x;i<=n;i+=lowbit(i)) c[i]+=d;
    }
    int sum(int x){//查询
        int ans=0;
        for(int i=x;i>0;i-=lowbit(i)) ans+=c[i];
        return ans;
    }
    void init(){
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            for(int j=i-lowbit(i)+1;j<=i;j++){
                c[i]=c[i]+s[j];
            }
        }
    }
}a;
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++)//输入
        scanf("%d",&s[i]);
    a.init();//初始化
    for(int i=1;i<=m;i++){
        int b,x,y;
        scanf("%d%d%d",&b,&x,&y);
        if(b==1) a.add(x,y);//把x为加上y
        else printf("%d\n",a.sum(y)-a.sum(x-1));
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

(2)树状数组2

题意：
第一行包含两个整数 N N N、 M M M，分别表示该数列数字的个数和操作的总个数。
第二行包含 N N N 个用空格分隔的整数，其中第 i i i 个数字表示数列第 i i i 项的初始值。
接下来 M M M 行每行包含 2 2 2 或 4 4 4 个整数，表示一个操作，具体如下：

  • 操作 1 1 1： 格式：1 x y k含义：将区间 [ x , y ] [x,y] [x,y] 内每个数加上 k k k；
  • 操作 2 2 2： 格式：2 x含义：输出第 x x x 个数的值。

一篇不错的题解：here

对于修改我们可以用树状数组维护差分数组
但是用树状数组我们仅维护修改的值（也就是改变的值）
最后查询的时候加上初始值就好了

#include<iostream>
#include<cstdio>
#define maxn 500100
using namespace std;
int n,m;
int c[maxn];
int a[maxn];
int add(int x,int k){
    for(int i=x;i<=n;i+=i&(-i)) c[i]+=k;
}
int query(int x){
    int sum=0;
    for(int i=x;i>0;i-=i&(-i)) sum+=c[i];
    return sum;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    while(m--){
        int k;
        scanf("%d",&k);
        if(k==1){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,z);           //维护查分数组
            add(y+1,-z);
        }
        else{
            int x;
            scanf("%d",&x);
            printf("%d\n",a[x]+query(x));   //query()求的是改变的值，再加上原来的值就可以了
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

15.乘法逆元 || 难度：普及/提高- ~ 普及+/提高

乘法逆元1

给定 n , p n,p n,p 求 1 ∼ n 1\sim n 1∼n 中所有整数在模 p p p 意义下的乘法逆元。
这里 a a a 模 p p p 的乘法逆元定义为 a x ≡ 1 ( m o d p ) ax\equiv1\pmod p ax≡1(modp) 的解。

又有一篇写的不错的题解：here,那就不多赘述了。

（1）递推
#include<cstdio>
using namespace std;
long long n,p;
long long ans[5000010]={0,1};
int main(){
   scanf("%lld%lld",&n,&p);
   printf("1\n");
   for(long long i=2;i<=n;i++){//线性递推
     	ans[i]=(long long)(p-p/i)*ans[p%i]%p;
       printf("%lld\n",ans[i]); 
   }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
(2)阶乘逆元
#include<cstdio>
#define ll long long
using namespace std;
ll ksm(ll a,ll b,ll mod){ //快速幂模板
    ll ans=1;
    while(b){
    	if(b&1) ans=ans*a%mod;
    	a=(a*a)%mod;
    	b>>=1;
    }
    return ans%mod;
}
ll n,p;
ll c[5000010]={1};
ll f[5000010];
int main(){
    scanf("%lld%lld",&n,&p);
    for(int i=1;i<=n;i++)
        c[i]=(c[i-1]*i)%p;
    f[n]=ksm(c[n],p-2,p); //获得inv(n!)
    for(int i=n-1;i>=1;i--) //递推阶乘的逆元
        f[i]=(f[i+1]*(i+1))%p;
    for(int j=1;j<=n;j++) //转化并输出
        printf("%lld\n",(f[j]*c[j-1])%p);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
(3)欧拉定理（不保证其正确性）
#include <iostream>
typedef long long int ll;
ll X,p;
ll mpow(ll x, ll y) {
    ll _ret = 1;
    while (y) {
        if (y & 1) (_ret *= x) %= p;
        y >>= 1;
        (x *= x) %= p;
    }
    return _ret;
}
int main() {
    std::cin >> X >> p;
    std::cout << mpow(X, p - 2) << std::endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

乘法逆元2

题意：
给定 n n n 个正整数 a i a_i ai​，求它们在模 p p p 意义下的乘法逆元。
由于输出太多不好，所以将会给定常数 k k k，你要输出的答案为：
∑ i = 1 n k i a i \sum\limits_{i=1}^n\frac{k^i}{a_i} i=1∑n​ai​ki​
答案对 p p p 取模。

分析：
来篇题解尝尝鲜？

#include <cstdio>
#define N 5000010
#define re register
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
typedef long long ll;
static char buf[100000],*pa(buf),*pb(buf);
inline int read() {
    re int x(0);re char c(gc);
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9')
        x=x*10+c-48,c=gc;
    return x;
}
inline int pow(int a,int b,int p) {
    int ans(1);
    while(b)
        ans=b&1?(ll)ans*a%p:ans,a=(ll)a*a%p,b>>=1;
    return ans;
}
int n,p,k,a[N],s[N]={1},inv_s[N],ans;
int main() {
    n=read(),p=read(),k=read();
    for(int i=1;i<=n;++i)
        a[i]=read(),s[i]=(ll)s[i-1]*a[i]%p;
    inv_s[n]=pow(s[n],p-2,p);
    for(int i=n-1;i;--i)
        inv_s[i]=(ll)inv_s[i+1]*a[i+1]%p;
    for(int i=n;i;--i)
        ans=((ll)inv_s[i]*s[i-1]%p+ans)*k%p;
    printf("%d",ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

16.最近公共祖先(LCA)

题意：
一行包含三个正整数 N , M , S N,M,S N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N − 1 N-1 N−1 行每行包含两个正整数 x , y x, y x,y，表示 x x x 结点和 y y y 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 M M M 行每行包含两个正整数 a , b a, b a,b，表示询问 a a a 结点和 b b b 结点的最近公共祖先。

一篇很棒的题解：here。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=5e5+1;
int n,m,rt,f[maxn][24],dep[maxn];
vector<int> g[maxn];
inline void dfs(int u){
    for(int i=1;i<=20;++i) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if(v==f[u][0]) continue;
        f[v][0]=u;
        dep[v]=dep[u]+1;
        dfs(v);
	}
}
int up(int v,int d){
    for(int i=0;d;++i){
        if(d&1) v=f[v][i];
        d>>=1;
    }
    return v;
}
int LCA(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    v=up(v,dep[v]-dep[u]);
    if(u==v) return u;
    for(int i=20;i>=0;--i){
        if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    }
    return f[u][0];
}
int main(){
   scanf("%d%d%d",&n,&m,&rt);
   for(int i=1,u,v;i<n;++i){
       scanf("%d%d",&u,&v);
       g[u].push_back(v);
       g[v].push_back(u);
   }
   dfs(rt);
   for(int i=1,x,y;i<=m;++i){
       scanf("%d%d",&x,&y);
       printf("%d\n",LCA(x,y));
   }
   return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

17.KMP字符串匹配 || 难度：普及/提高-

题意：
给出两个字符串 s 1 s_1 s1​和 s 2 s_2 s2​，若 s 1 s_1 s1​ 的区间 [ l , r ] [l, r] [l,r] 子串与 s 2 s_2 s2​ 完全相同，则称 s 2 s_2 s2​ 在 s 1 s_1 s1​ 中出现了，其出现位置为 l l l。现在请你求出 s 2 s_2 s2​ 在 s 1 s_1 s1​ 中所有出现的位置。
定义一个字符串 s s s 的 b o r d e r border border 为 s s s 的一个非 s s s 本身的子串 t t t，满足 t t t 既是 s s s 的前缀，又是 s s s 的后缀。对于 s 2 s_2 s2​，你还需要求出对于其每个前缀 s ′ s' s′ 的最长 b o r d e r t ′ border t' bordert′ 的长度。

比较复杂，详情参见这篇题解！

#include <cstdio>
#include <cstring>
char p[1000005], t[1000005];
int len1, len2;
int next[1000005], next2[1000005];
void do_next(){
    next[0] = 0;
    int i = 1;
    int len = 0;
    while (i < len2){
        if (t[i] == t[len]) next[i++] = ++len;
        else{
            if (len > 0) len = next[len - 1];
            else next[i++] = len;
        }
    }
}
void kmp(){
    int i = 0, j = 0;
    next2[0] = -1;
    for (int i = 1; i < len2; i++)
        next2[i] = next[i - 1];
    while (i < len1){
        if (j == len2 - 1 && p[i] == t[j]){
            printf("%d\n", i - j + 1);
            j = next2[j];
            if (j == -1)
                j++;
        }
        if (p[i] == t[j]){
            j++;
            i++;
        }
        else{
            j = next2[j];
            if (j == -1){
                i++;
                j++;
            }
        }
    }
}
int main(){
    scanf("%s%s", p, t);
    len1 = strlen(p);
    len2 = strlen(t);
    do_next();
    kmp();
    for (int i = 0; i < len2; i++)
        printf("%d ", next[i]);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

18.线段树 || 难度：普及/提高- ~ 普及+/提高

线段树1

题意：
第一行包含两个整数 n , m n, m n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n n n 个用空格分隔的整数，其中第 i i i 个数字表示数列第 i i i 项的初始值。
接下来 m m m 行每行包含 3 3 3 或 4 4 4 个整数，表示一个操作，具体如下：

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

区间加减，区间查询

详情见这个题解：here 或者 这个。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init long long
using namespace std;
init n,m;
struct node{
    init l,r,data;
    init lt;    
}tree[1000010];
init arr[1000010];
void build(init l,init r,init index,init arr[]){
    tree[index].lt=0;
    tree[index].l=l;
    tree[index].r=r;
    if(l==r){
        tree[index].data=arr[l];
        return ;
    }
    init mid=(l+r)/2;
    build(l,mid,index*2,arr);
    build(mid+1,r,index*2+1,arr);
    tree[index].data=tree[index*2].data+tree[index*2+1].data;
    return ;
}
void push_down(init index){
    if(tree[index].lt!=0){
        tree[index*2].lt+=tree[index].lt;
        tree[index*2+1].lt+=tree[index].lt;
        init mid=(tree[index].l+tree[index].r)/2;
        tree[index*2].data+=tree[index].lt*(mid-tree[index*2].l+1);
        tree[index*2+1].data+=tree[index].lt*(tree[index*2+1].r-mid);
        tree[index].lt=0;
    }
    return ;
}
void up_data(init index,init l,init r,init k){
    if(tree[index].r<=r && tree[index].l>=l){
        tree[index].data+=k*(tree[index].r-tree[index].l+1);
        tree[index].lt+=k;
        return ;
    }
    push_down(index);
    if(tree[index*2].r>=l)
        up_data(index*2,l,r,k);
    if(tree[index*2+1].l<=r)
        up_data(index*2+1,l,r,k);
    tree[index].data=tree[index*2].data+tree[index*2+1].data;
    return ;
}
init search(init index,init l,init r){
    if(tree[index].l>=l && tree[index].r<=r)
        return tree[index].data;
    push_down(index);
    init num=0;
    if(tree[index*2].r>=l)
        num+=search(index*2,l,r);
    if(tree[index*2+1].l<=r)
        num+=search(index*2+1,l,r);
    return num;
}
int main(){
    cin>>n>>m;
    for(init i=1;i<=n;i++)
        cin>>arr[i];
    build(1,n,1,arr);
    for(init i=1;i<=m;i++){
        init f;
        cin>>f;
        if(f==1){
            init a,b,c;
            cin>>a>>b>>c;
            up_data(1,a,b,c);
        }
        if(f==2){
            init a,b;
            cin>>a>>b;
            printf("%lld\n",search(1,a,b));
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83

线段树2

题意：
第一行包含三个整数 n , m , p n,m,p n,m,p，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 n n n 个用空格分隔的整数，其中第 i i i 个数字表示数列第 i i i 项的初始值。
接下来 m m m 行每行包含若干个整数，表示一个操作，具体如下：

  • 操作 1 1 1： 格式：1 x y k含义：将区间 [ x , y ] [x,y] [x,y] 内每个数乘上 k k k.
  • 操作 2 2 2： 格式：2 x y k含义：将区间 [ x , y ] [x,y] [x,y] 内每个数加上 k k k
  • 操作 3 3 3： 格式：3 x y含义：输出区间 [ x , y ] [x,y] [x,y] 内每个数的和对 p p p 取模所得的结果

区间乘法

这是一篇较为能理解的题解：传送门！

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define INF 10000009
#define MOD 10000007
#define LL long long
#define in(a) a=read()
#define REP(i,k,n) for(long long i=k;i<=n;i++)
#define DREP(i,k,n) for(long long i=k;i>=n;i--)
#define cl(a) memset(a,0,sizeof(a))
inline long long read(){
    long long x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
inline void out(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
long long n,m,p;
long long input[MAXN];
struct node{
    long long l,r;
    long long sum,mlz,plz;
}tree[4*MAXN];
inline void build(long long i,long long l,long long r){
    tree[i].l=l;
    tree[i].r=r;
    tree[i].mlz=1;
    if(l==r){
        tree[i].sum=input[l]%p;
        return ;
    }
    long long mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline void pushdown(long long i){
    long long k1=tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;
    tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
    tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
    tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
    tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
    tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
    tree[i].plz=0;
    tree[i].mlz=1;
    return ;
}
inline void mul(long long i,long long l,long long r,long long k){
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum=(tree[i].sum*k)%p;
        tree[i].mlz=(tree[i].mlz*k)%p;
        tree[i].plz=(tree[i].plz*k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  mul(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)  mul(i<<1|1,l,r,k);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline void add(long long i,long long l,long long r,long long k){
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum+=((tree[i].r-tree[i].l+1)*k)%p;
        tree[i].plz=(tree[i].plz+k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  add(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)  add(i<<1|1,l,r,k);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline long long search(long long i,long long l,long long r){
    if(tree[i].r<l || tree[i].l>r)  return 0;
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    pushdown(i);
    long long sum=0;
    if(tree[i<<1].r>=l)  sum+=search(i<<1,l,r)%p;
    if(tree[i<<1|1].l<=r)  sum+=search(i<<1|1,l,r)%p;
    return sum%p;
}
int main(){
    in(n);    in(m);in(p);
    REP(i,1,n)  in(input[i]);
    build(1,1,n); 

    REP(i,1,m){
        long long fl,a,b,c;
        in(fl);
        if(fl==1){
            in(a);in(b);in(c);
            c%=p;
            mul(1,a,b,c);
        }
        if(fl==2){
            in(a);in(b);in(c);
            c%=p;
            add(1,a,b,c);
        }
        if(fl==3){
            in(a);in(b);
            printf("%lld\n",search(1,a,b));
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123

19.负环

题意
输入的第一行是一个整数 T T T，表示测试数据的组数。对于每组数据的格式如下：
第一行有两个整数，分别表示图的点数 n n n 和接下来给出边信息的条数 m m m。
接下来 m m m 行，每行三个整数 u , v , w u, v, w u,v,w。
若 w ≥ 0 w \geq 0 w≥0，则表示存在一条从 u u u 至 v v v 边权为 w w w 的边，还存在一条从 v v v 至 u u u 边权为 w w w 的边。
若 w < 0 w < 0 w<0，则只表示存在一条从 u u u 至 v v v 边权为 w w w 的边。
给定一个 n n n 个点的有向图，请求出图中是否存在从顶点 1 1 1 出发能到达的负环。
负环的定义是：一条边权之和为负数的回路。

见解释，自认为写的还行。

各种做法请移步至上边的题解。

#include <bits/stdc++.h>
using namespace std;
inline int gin(){//快读
    char c=getchar();
    int s=0,f=1;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}
const int N=5e3+5;//本题数据范围不大，习惯开大一点。
int n,m,cnt[N],d[N],tot=0,head[N];
//cnt记录已经入队的次数。
bool h[N],t;
//小写字母t用来存是否存在负环，存在则为1，否则为0。
queue<int> q;
struct edge{//用结构体存链接表
    int dis,ne,to;
}e[N<<1];
inline void add(int u,int v,int w){//连边
	e[++tot].dis=w;
	e[tot].to=v;
	e[tot].ne=head[u];
	head[u]=tot;
}
void spfa(){//最短路模板
    memset(h,0,sizeof h);
    memset(cnt,0,sizeof cnt);
    memset(d,63,sizeof d);//记得每次初始化
    h[1]=1,t=0,d[1]=0;
    q.push(1);
    while(q.size()){
        int u=q.front();
        q.pop();
        h[u]=0;
        if(cnt[u]==n-1){t=1;return;}//如果在此之前已经有n-1次入队了则有负环。
        cnt[u]++;
        for(int i=head[u];i;i=e[i].ne){
            int v=e[i].to,w=e[i].dis;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(!h[v])h[v]=1,q.push(v);
            }
        }
    } 
}
int main(){
    int T=gin();
    while(T--){
        n=gin(),m=gin();
        tot=0;//在tot变为0的情况下，结构体e每次存的时候都会覆盖老的答案，所以不再需要初始化e了。
        memset(head,-1,sizeof head);//初始化head数组
        for(int i=1;i<=m;i++){
            int u=gin(),v=gin(),w=gin();
            add(u,v,w);
            if(w>=0)add(v,u,w);
        }
        spfa();
        if(t)printf("YES\n");
        else printf("NO\n");
     }
     return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

20.单调栈 || 难度：普及/提高-

题意：
给出项数为 n n n 的整数数列 a 1 … n a_{1 \dots n} a1…n​。
定义函数 f ( i ) f(i) f(i) 代表数列中第 i i i 个元素之后第一个大于 a i a_i ai​ 的元素的下标，即 f ( i ) = min ⁡ i < j ≤ n , a j > a i { j } f(i)=\min_{i<j\leq n, a_j > a_i} \{j\} f(i)=mini<j≤n,aj​>ai​​{j}。
若不存在，则 f ( i ) = 0 f(i)=0 f(i)=0。
试求出 f ( 1 … n ) f(1\dots n) f(1…n)。

归纳一下:

  • 从后往前扫

  • 对于每个点：

    • 弹出栈顶比她小的元素
    • 此时栈顶就是答案
    • 加入这个元素
      好了。

（1）STL版

#include<cstdio>
#include<stack>
using namespace std;
int n,a[3000005],f[3000005];//a是需要判断的数组（即输入的数组），f是存储答案的数组
stack<int>s;//模拟用的栈
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=n;i>=1;i--){
        while(!s.empty()&&a[s.top()]<=a[i]) s.pop();//弹出栈顶比当前数小的
        f[i]=s.empty()?0:s.top();//存储答案，由于没有比她大的要输出0，所以加了个三目运算
        s.push(i);//压入当前元素
    }
    for(int i=1;i<=n;i++) printf("%d ",f[i]);//输出
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

（2）手写板

#include<iostream>
#include<cstdio>
#define INF 3000005
//头文件+预处理名。
using namespace std;
int n,a[Inf],q[INF],r,f[INF];
//定义变量，其中a数组表示输入的数，q数组表示存下标的单调栈，f数组是存结果。
int main(){
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d",&a[i]);
   //上面是读入。
    for (int i=n; i>=1; i--) {
    //从最后开始枚举。
        while (a[i]>=a[q[r]] && r>0) r--;
    //如果说它找到了比矮高的人并且不是最后，那么将那个矮的人弹掉，毕竟后面也不会有人看到它了，因为如果看到它的话那么必定可以看到比它前面的还比它高的。
        f[i]=q[r];
      //存结果，因为要正向输出。
        q[++r]=i;
     //将它入栈。
     }
     for (int i=1; i<=n; i++) printf("%d ",f[i]);
   //最后正着输出。
     return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

21.矩阵加速（数列）|| 难度：普及/提高-

题意：
已知一个数列 a a a，它满足：

a x = { 1 x ∈ { 1 , 2 , 3 } a x − 1 + a x − 3 x ≥ 4 a_x=

{1x∈{1,2,3}ax−1+ax−3x≥4
ax​={1ax−1​+ax−3​​x∈{1,2,3}x≥4​

求 a a a 数列的第 n n n 项对 1 0 9 + 7 10^9+7 109+7 取余的值。

好题解*4

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;
const int Mod = 1e9+7;
int T, n;
struct mat{
    LL m[5][5];
}Ans, base;
void init() {
    memset(Ans.m, 0, sizeof(Ans.m));
    for(int i=1; i<=3; i++) Ans.m[i][i] = 1;
    memset(base.m, 0, sizeof(base.m));
    base.m[1][1] = base.m[1][3] = base.m[2][1] = base.m[3][2] = 1;
}
mat mul(mat a, mat b) {
    mat res;
    memset(res.m, 0, sizeof(res.m));
    for(int i=1; i<=3; i++) {
        for(int j=1; j<=3; j++) {
            for(int k=1; k<=3; k++) {
                res.m[i][j] += (a.m[i][k] % Mod) * (b.m[k][j] % Mod);
                res.m[i][j] %= Mod;
            }
        }
    }
    return res;
}
void Qmat_pow(int p) {
    while (p) {
        if(p & 1) Ans = mul(Ans, base);
        base = mul(base, base);
        p >>= 1;
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if(n <= 3) {
            printf("1\n");
            continue;
        }
        init();
        Qmat_pow(n);
        printf("%lld\n", Ans.m[2][1]);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

22.单源最短路径（标准版）|| 难度：普及/提高-

题意：
给定一个 n n n 个点， m m m 条有向边的带非负权图，请你计算从 s s s 出发，到每个点的距离。
第一行为三个正整数 n , m , s n, m, s n,m,s。 第二行起 m m m 行，每行三个非负整数 u i , v i , w i u_i, v_i, w_i ui​,vi​,wi​，表示从 u i u_i ui​ 有一条权值为 w i w_i wi​ 的有向边。

关于算法的题解

(1) d i j k s t r a dijkstra dijkstra 堆优化版本，复杂度 O ( ( n + m ) l o g 2   n ) O((n+m)log_2\ n) O((n+m)log2​ n)

复杂版（？）
#include<bits/stdc++.h>
const int MaxN = 100010, MaxM = 500010;
struct edge{
    int to, dis, next;
};
edge e[MaxM];
int head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
int n, m, s;
inline void add_edge( int u, int v, int d ){
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
struct node{
    int dis;
    int pos;
    bool operator <( const node &x )const{
        return x.dis < dis;
    }
};
std::priority_queue<node> q;

inline void dijkstra(){
    dis[s] = 0;
    q.push( ( node ){0, s} );
    while( !q.empty() ){
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if( vis[x] )
            continue;
        vis[x] = 1;
        for( int i = head[x]; i; i = e[i].next ){
            int y = e[i].to;
            if( dis[y] > dis[x] + e[i].dis ){
                dis[y] = dis[x] + e[i].dis;
                if( !vis[y] ){
                    q.push( ( node ){dis[y], y} );
                }
            }
        }
    }
}
int main(){
    scanf( "%d%d%d", &n, &m, &s );
    for(int i = 1; i <= n; ++i)dis[i] = 0x7fffffff;
    for( register int i = 0; i < m; ++i ){
        register int u, v, d;
        scanf( "%d%d%d", &u, &v, &d );
        add_edge( u, v, d );
    }
    dijkstra();
    for( int i = 1; i <= n; i++ )
        printf( "%d ", dis[i] );
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
简单版（？）
#include<bits/stdc++.h>
#define M(x,y) make_pair(x,y)
using namespace std;
int fr[100010],to[200010],nex[200010],v[200010],tl,d[100010];
bool b[100010];
void add(int x,int y,int w){
    to[++tl]=y;
    v[tl]=w;
    nex[tl]=fr[x];
    fr[x]=tl;
}
priority_queue< pair<int,int> > q;
int main(){
    int n,m,x,y,z,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1;i<=n;i++) d[i]=1e10;
    d[s]=0;
    q.push(M(0,s));
    while(!q.empty()){
        int x=q.top().second;
        q.pop(); 
        if(b[x]) continue;
        b[x]=1;
        for(int i=fr[x];i;i=nex[i]){
            int y=to[i],l=v[i];
            if(d[y]>d[x]+l){
                d[y]=d[x]+l;
                q.push(M(-d[y],y));//懒得重载运算符
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",d[i]);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

（2） d i j k s t r a dijkstra dijkstra 的 p a i r pair pair 优化版本

#include<bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}
const int N=100000+10,M=200000+10;
int n,m,s,t;
struct edge { int v,w,nxt; } e[M];
int head[N];
void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}
// 这是一个以 dis 为第一关键字的小根堆
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> Q; 
int dis[N];
void dijkstra(int s) {
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,Q.push(make_pair(0,s));
    while (!Q.empty()) {
        int u=Q.top().second,d=Q.top().first; Q.pop();
        if (d!=dis[u]) continue;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) dis[v]=dis[u]+w,Q.push(make_pair(dis[v],v));
        }
    }
}
int main(){
    n=read(),m=read(),s=read();
    for (int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w);
    }
    dijkstra(s);
    for (int i=1;i<=n;++i) printf("%d%c",dis[i]," \n"[i==n]);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

（3） d i j k s t r a dijkstra dijkstra 的线段树优化版本（恶臭）

#include<bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}
const int N=100000+10,M=200000+10;
const int inf=0x3f3f3f3f;
int n,m,s;
struct edge { int v,w,nxt; } e[M];
int head[N];
void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}
#define ls (o<<1)
#define rs (o<<1|1)
int minv[N<<2],minp[N<<2];
void pushup(int o) {
    if (minv[ls]<=minv[rs]) minv[o]=minv[ls],minp[o]=minp[ls];
    else minv[o]=minv[rs],minp[o]=minp[rs];
}
void build(int o,int l,int r) {
    if (l==r) { minv[o]=inf,minp[o]=l; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int p,int w) {
    if (l==r) { minv[o]=w; return; }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    pushup(o);
}
#undef ls
#undef rs
int dis[N];
void dijkstra(int s) {
    build(1,1,n); modify(1,1,n,s,0);
    memset(dis,0x3f,sizeof(dis)),dis[s]=0;
    while (minv[1]!=inf) {
        int u=minp[1]; modify(1,1,n,u,inf);
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) 
                dis[v]=dis[u]+w,modify(1,1,n,v,dis[v]);
        }
    }
}
int main() {
    n=read(),m=read(),s=read();
    for (int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w);
    }
    dijkstra(s);
    for (int i=1;i<=n;++i) printf("%d%c",dis[i]," \n"[i==n]);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65

关于 S P F A SPFA SPFA,它死了

啊不不不，反转了。
它可以过弱化版
用的是STL队列，首先用数组dis记录起点到每个结点的最短路径，用邻接表来存储图，用vis数组记录当前节点是否在队列中

具体操作为：用队列来保存待优化的结点（类似于BFS），优化时每次取出队首结点，并且用队手节点来对最短路径进行更新并进行松弛操作

如果要对所连点的最短路径需要更新，且改点不在当前的队列中，就将改点加入队列

然后不断进行松弛操作，直至队列空为止。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
#define maxn 10005
#define maxm 500005
#define inf 1234567890
int n,m,s,tot,dis[maxn],head[maxn];
bool vis[maxn];
struct Edge{
      int next,to,w;
}h[maxm];
void add(int u,int v,int w){
    h[++tot].next=head[u];
    h[tot].to=v;
    h[tot].w=w;
    head[u]=tot;
}
//上面和dijkstra算法基本上一样
queue<int> q;
//队列优化
inline void spfa(){
    for(int i=1; i<=n; i++){
        dis[i]=inf;
        //赋初值
    }
    int u,v;
    q.push(s);
    dis[s]=0;
    //将起点的值负为0
    vis[s]=1;//这句话可加可不加，因为循环的时候vis[s]又会被赋为0
    while(!q.empty()){
    //当队列里没有元素的时候，那就已经更新了所有的单源最短路径
        u=q.front();
        //将队手节点记录并弹出队首节点
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=h[i].next){
        //寻找与u相连的边
            v=h[i].to;
            if(dis[v]>dis[u]+h[i].w){
                dis[v]=dis[u]+h[i].w;
                //松弛操作，和floyd比较相似
                if(!vis[v]){
                //已经在队列里的点就不用再进入了
                      vis[v]=1;
                      q.push(v);
                }
            }
        }
    }
}
int main(){
    n=read(),m=read(),s=read();
    for(int i=1,u,v,w;i<=m;i++){
        u=read(),v=read(),w=read();
        add(u,v,w);
    }
    spfa();
    for(int i=1; i<=n; i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

S P F A SPFA SPFA内容选自这个博文

23.矩阵快速幂 || 难度：普及/提高-

题意：
给定 n × n n\times n n×n 的矩阵 A A A，求 A k A^k Ak。
第一行两个整数 n , k n,k n,k 接下来 n n n 行，每行 n n n 个整数，第 i i i 行的第 j j j 的数表示 A i , j A_{i,j} Ai,j​.
共 n n n 行，每行 n n n 个数，第 i i i 行第 j j j 个数表示 ( A k ) i , j (A^k)_{i,j} (Ak)i,j​,每个元素对 $10^9+7$10 取模。

先了解了解吧

#include<cstdio>
#define ll long long
using namespace std;
const ll Mod=1000000007;
ll n,k;  
struct matrix{  
    ll m[105][105];  
}a;
matrix x(matrix a,matrix b){ //矩阵乘法的模板    
    matrix t;  
    for(int i=0;i<n;i++)  
     for(int j=0;j<n;j++){  
        t.m[i][j]=0; 
        for(int k=0;k<n;k++)  
         t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%Mod; 
     }  
    return t;  
}  
matrix fast_m(matrix a,ll k){
    matrix ret=a,b=a;k--;
    //这里记得减一因为之前已经乘过一次了 
    while(k>0){
        if(k%2==1) ret=x(b,ret);
        b=x(b,b);
        k/=2;
    }
    return ret;
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      scanf("%lld",&a.m[i][j]);
    a=fast_m(a,k);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
        printf("%lld ",a.m[i][j]);
        printf("\n");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

24.裴蜀定理 || 难度：普及/提高-

较简单的板子，在看完那么多繁琐复杂的板子后放松一下吧！

题意：
给定一个包含 n n n 个元素的整数序列 A A A，记作 A 1 , A 2 , A 3 , . . . , A n A_1,A_2,A_3,...,A_n A1​,A2​,A3​,...,An​。
求另一个包含 n n n 个元素的待定整数序列 X X X，记 S = ∑ i = 1 n A i × X i S=\sum\limits_{i=1}^nA_i\times X_i S=i=1∑n​Ai​×Xi​，使得 S > 0 S>0 S>0 且 S S S 尽可能的小。

先了解亿下。

#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a,int b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int main(){
    int n,ans=0;
    cin>>n;
    while (n--){
        int c;
        cin>>c;
        ans=gcd(ans,abs(c));
    }
    cout<<ans<<endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

25.字典树 || 难度：普及/提高-

题意：
给定 n n n 个模式串 s 1 , s 2 , … , s n s_1, s_2, \dots, s_n s1​,s2​,…,sn​ 和 q q q 次询问，每次询问给定一个文本串 t i t_i ti​，请回答 s 1 ∼ s n s_1 \sim s_n s1​∼sn​ 中有多少个字符串 s j s_j sj​ ,满足 t i t_i ti​ 是 s j s_j sj​ 的前缀。
一个字符串 t t t 是 s s s 的前缀当且仅当从 s s s 的末尾删去若干个（可以为 0 0 0 个）连续的字符后与 t t t 相同。
输入的字符串大小敏感。

先看看它here？

#include<bits/stdc++.h>
using namespace std;
int T,q,n,t[3000005][65],cnt[3000005],idx;
char s[3000005];
int getnum(char x){
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
} 
void insert(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            t[p][c]=++idx;
        p=t[p][c];
        cnt[p]++;
    }
}
int find(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            return 0;
        p=t[p][c];
    }
    return cnt[p];
}
int main(){
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<=idx;i++)
            for(int j=0;j<=122;j++)
                t[i][j]=0;
        for(int i=0;i<=idx;i++)
            cnt[i]=0;
        idx=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            insert(s);
        }
        for(int i=1;i<=q;i++){
            scanf("%s",s);
            printf("%d\n",find(s));
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/993840
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号