模版

2023-12-22 00:00:00 未分类

dijkstra 
#include<cstdio>
#include<queue>
#include<string.h>
#include <limits.h>
using namespace std;

int read() {
    int x=1,ans=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') x*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {ans=ans*10+ch-'0';ch=getchar();}
    return x*ans;
}

const int N=100005,M=500005;

struct EDGE {
    int to,val,next;
}edge[M];

int top=0,head[N],dis[N],n,m,s;
bool vis[N];

void add_edge(int u,int v,int val) {
    edge[++top].to=v;
    edge[top].val=val;
    edge[top].next=head[u];
    head[u]=top;
}

void dijk() {
    memset(dis,0x7f,sizeof(dis));
    // for(register int i=0;i<=n;++i) dis[i]=INT_MAX;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> w; 
    dis[s]=0;
    w.push(make_pair(dis[s],s));
    while(w.size()) {
        int u=w.top().second; w.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(register int i=head[u];i;i=edge[i].next) {
            int v=edge[i].to;
            int ans=dis[u]+edge[i].val;
            if(ans<dis[v]) {
                dis[v]=ans;
                if(!vis[v])
                    w.push(make_pair(dis[v],v));
            }
        }
    }
}

int main() {
    n=read(),m=read();s=read();
    for(register int i=1;i<=m;++i) {
        int u=read(),v=read(),val=read();
        add_edge(u,v,val);
    }
    dijk();
    for(register int i=1;i<=n;++i) {
        printf("%d ",dis[i]);
    }
    return 0;
}
乘法逆元 
#include<bits/stdc++.h>
using namespace std;

int read() {
    register int x=1,ans=0;register char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') x*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=(ans<<3)+(ans<<1)+ch-48;ch=getchar();}
    return x*ans;
}

int n,p;

void exgcd(int a,int b,int &x,int &y) {
    if(b==0) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}

int inv(int a) {
    int x,y; exgcd(a,p,x,y); return (x%p+p)%p;
}

/*
a*x=1 mod y

x*a+y*b=gcd(a,b)

gcd(b,a%b)=x*b+y*(a-a/b*b)
=x*b+y*a-y*a/b*b
x*a+y*b=y*a+(x-y*a/b)*b
x=y;
y=x-y*a/b

*/

int in[3000005];

int main() {
    n=read(); p=read();
    in[1]=1;puts("1");
    for(register int i=2;i<=n;++i) {
        in[i]=(long long)(p-p/i)*in[p%i]%p;
        printf("%dn",in[i]);
    }
    return 0;
}
线性基 
#include<bits/stdc++.h>
using namespace std;

long long read() {
    register long long x=1,ans=0;register char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') x*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=(ans<<3)+(ans<<1)+ch-48;ch=getchar();}
    return x*ans;
}

const int N=65;
long long b[N],n;

int main() {
    n=read();
    for(long long i=1;i<=n;++i) {
        long long x=read();
        for(long long j=62;j>=0;--j) {
            if((x>>j)&1) {
                if(b[j]) x^=b[j];
                else {
                    b[j]=x; break;
                }
            }
//          if(!(x>>j)) continue;
//          if(!b[j]) {
//              b[j]=x; break;
//          }
//          x^=b[j];
        }
    }
    long long ans=0;
    for(long long i=62;i>=0;--i)
        if((ans^b[i])>ans) ans^=b[i];
    printf("%lldn",ans);
    return 0;
}
线段树 
#include<bits/stdc++.h>
using namespace std;

int read() {
    int tmp;
    scanf("%d",&tmp);
    return tmp;
}

const int MAXN=100005;

struct tree{
    int l,r,tag;
    long long dat;
}t[MAXN*3];//warning !

int a[MAXN],n,m;

void build(int p,int l,int r) {
    //cout<<p<<' '<<l<<' '<<r<<endl;
    t[p].l=l; t[p].r=r;
    if(l==r) {
        t[p].dat=a[l];
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=t[p*2].dat+t[p*2+1].dat; 
}

void pushdown(int p) {
    t[p*2].tag+=t[p].tag;
    t[p*2+1].tag+=t[p].tag;
    t[p*2].dat+=(t[p*2].r-t[p*2].l+1)*t[p].tag;
    t[p*2+1].dat+=(t[p*2+1].r-t[p*2+1].l+1)*t[p].tag;
    t[p].tag=0;
}

void add(int p,int l,int r,int k) {
    if(t[p].l>r||t[p].r<l) return ;
    if(t[p].l>=l&&t[p].r<=r) {
        t[p].dat+=(t[p].r-t[p].l+1)*k;
        t[p].tag+=k;
        return ;
    }
    pushdown(p);
    add(p*2,l,r,k); add(p*2+1,l,r,k);
    t[p].dat=t[p*2].dat+t[p*2+1].dat;
}

long long ask(int p,int l,int r) {
    if(t[p].l>r||t[p].r<l) return 0;
    if(t[p].l>=l&&t[p].r<=r) return t[p].dat;
    pushdown(p);
    long long ans=ask(p*2,l,r)+ask(p*2+1,l,r);
    return ans;
}

int main() {
    n=read(); m=read();
    for(register int i=1;i<=n;++i) {
        a[i]=read();
    }
    //cout<<"ok"<<endl;
    build(1,1,n);
    while(m--) {
        int l,r,k;
        if(read()==1) {
            l=read();r=read();k=read();
            add(1,l,r,k);
        }
        else {
            l=read();r=read();
            printf("%lldn",ask(1,l,r));
        }
    }
    return 0;
}
割点 
#include<bits/stdc++.h>
using namespace std;

int read() {
    int x=1,ans=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            x*=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        ans=ans*10+ch-48;
        ch=getchar();
    }
    return x*ans;
}

const int N=20005,M=100005;

struct EDGE {

    struct Edge {
        int to,next;
    }edge[M*2];

    int head[N],top,dfn[N],low[N],n,m,root;
    bitset<N> c;

    void add(int u,int v) {
        edge[++top].to=v;
        edge[top].next=head[u];
        head[u]=top;
    }

    void tarjan(int u) {
        dfn[u]=low[u]=++top;
        int ch=0;
        for(int i=head[u];i;i=edge[i].next) {
            int v=edge[i].to;
            if(!dfn[v]) {
                ch++;
                tarjan(v);
                low[u]=min(low[u],low[v]);
                if((u==root&&ch>1)||(u!=root&&low[v]>=dfn[u]))
                    c[u]=true;
            }
            else low[u]=min(low[u],dfn[v]);
        }
    }

    void tarjan() {
        top=0;
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(root=i);
    }

}a;

int main() {
    a.n=read();a.m=read();
    for(int i=1;i<=a.m;i++) {
        int u=read(),v=read();
        a.add(u,v);a.add(v,u);
    }
    a.tarjan();
    queue<int> ans;
    for(int i=1;i<=a.n;i++)
        if(a.c[i]) ans.push(i);
    printf("%lun",ans.size());
    while(ans.size()) printf("%d ",ans.front()),ans.pop();
    return 0;
}
lct 
#include<bits/stdc++.h>
using namespace std;
#define chk(x) (ch[fa[x]][1]==x)
#define update(x) (s[x]=s[ch[x][0]]^val[x]^s[ch[x][1]])

int read() {
    register int x=1,ans=0;register char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') x*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=(ans<<1)+(ans<<3)+ch-48;ch=getchar();}
    return x*ans;
}

const int N=300005;
int ch[N][2],val[N],s[N],fa[N],rt,fg[N];

inline bool nrt(int x) {
    return ch[fa[x]][1]==x||ch[fa[x]][0]==x;
}

void rev(int x) {
    fg[x]^=1; swap(ch[x][1],ch[x][0]);
}

void rotate(int x) {
    int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
    ch[y][k]=w;     fa[w]=y;
    if(nrt(y)) ch[z][chk(y)]=x; fa[x]=z;
    ch[x][k^1]=y;   fa[y]=x;
    update(y);      update(x);
}

void pushdown(int x) {
    if(fg[x]) {
        fg[x]=0;
        rev(ch[x][1]); rev(ch[x][0]);
    }
}

void pushall(int x) {
    if(nrt(x)) pushall(fa[x]);
    pushdown(x);
}

void splay(int x) {
    pushall(x);
    while(nrt(x)) {
        int y=fa[x],z=fa[y];
        if(nrt(y)) {
            if(chk(x)==chk(y)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}

void access(int x) {
    for(int y=0;x;x=fa[y=x]) {
        splay(x); ch[x][1]=y; update(x);
    }
}

void makeroot(int x) {
    access(x); splay(x); rev(x);
}

int findroot(int x) {
    access(x); splay(x);
    while(ch[x][0]) pushdown(x),x=ch[x][0];
    splay(x);
    return x;
}

void split(int x,int y) { 
    makeroot(x); access(y); splay(y);
}

void link(int x,int y) {
    makeroot(x);
    if(findroot(y)!=x) fa[x]=y;
}

void cut(int x,int y) {
    makeroot(x);
    if(findroot(y)==x&&fa[y]==x) {
        fa[y]=ch[x][1]=0;
        update(x);
    }
}

int main() {
    int n=read(),m=read();
    for(register int i=1;i<=n;++i) {
        val[i]=read();
    } 
    while(m--) {
        int t=read(),x=read(),y=read();
        if(t==0) split(x,y),printf("%dn",s[y]);
        else if(t==1) link(x,y);
        else if(t==2) cut(x,y);
        else splay(x),val[x]=y,update(x);
    }
    return 0;
}
树状数组 
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
const int MAXN=500005;
int c[MAXN],a[MAXN];
int n,m;
void add(int x,int k) {
    for(;x<=n;x+=lowbit(x))
        c[x]+=k; 
} 
int sum(int x) {
    int ans=0;
    for(;x>=1;x-=lowbit(x))
        ans+=c[x];
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),a[i]+=a[i-1];
    for(int i=1;i<=n;i++)
        c[i]=a[i]-a[i-lowbit(i)];
    while(m--) {
        int c,l,r;
        scanf("%d%d%d",&c,&l,&r);
        if(c==1) add(l,r);
        else printf("%dn",sum(r)-sum(l-1));
    }
    return 0;
}
上一篇：使用natfrp映射ssh服务 and 使用shell脚本实现：开机自启、掉线重连功能
下一篇：Linux在睡眠(or休眠)唤醒之后触摸板失灵的解决方法

搜索

归档

标签

最新文章

© 2024 Cznorth's Blog powered by Flask & Buefy

赣公网安备36110002000135 赣ICP备2024022131号-2