博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
Noip蒟蒻专用模板
阅读量：5024 次
发布时间：2019-06-12

本文共 13717 字，大约阅读时间需要 45 分钟。

目录

模板

数论

线性筛素数

#include 
    
     using namespace std;int n,notp[20000000],pri[2000000],tot;void get(){    notp[1]=1;    for(int i=2;i<=n;i++){        if(!notp[i]) pri[++tot]=i;        for(int j=1;j<=tot&&i*pri[j]<=n;j++){            notp[i*pri[j]]=1;            if(i%pri[j]==0) break;        }    }}int k;int main(){    scanf("%d%d",&n,&k);    get();    for(int i=1;i<=k;i++){        int a;        scanf("%d",&a);        if(!notp[a])puts("Yes");        else puts("No");    }}

线性筛欧拉

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;int notp[500000],pri[500000],cnt,phi[500000],n;void get(){ notp[1]=1; for(int i=2;i<=n;i++){ if(!notp[i]) pri[++cnt]=i,phi[i]=i-1; for(int j=1;j<=cnt && i*pri[j]<=n;j++){ notp[i*pri[j]]=1; if(i%pri[j]!=0)phi[i*pri[j]]=phi[i]*(pri[j]-1); if(i%pri[j]==0){ phi[i*pri[j]]=phi[i]*pri[j]; break; } } }}int main(){ scanf("%d",&n); get(); for(int i=1;i<=n;i++)printf("%d ",phi[i]);}

裴蜀定理

#include
    
     using namespace std;int n;int gcd(int x,int y){    return !y ? x : gcd(y,x%y);}int a , ans;int main(){    cin >> n;    cin >> ans;    if(ans <0 )ans = -ans;    for(int i = 2;i <= n;i ++)    {        cin >> a;        if(a <0 )            a = -a;        ans = gcd(ans , a);    }    cout << ans;}

卢卡斯定理

#include 
    
     using namespace std;typedef long long LL;int n,m,p;LL inv[200011],fac[200101];void get() {    inv[1]=1;    fac[0]=1;    inv[0]=1;    for(int i=1; i<=m+n; i++)fac[i]=fac[i-1]*i%p;    for(int i=2; i<=m+n; i++)inv[i]=(p-p/i)%p*inv[p%i]%p;    for(int i=2; i<=m+n; i++)inv[i]=inv[i-1]*inv[i]%p;}LL lucas(int x,int y) {    if(x

矩阵快速幂

#include
    
     #include
     
      #define LL long longusing namespace std;const int  mod = 1000000007;LL n,k;struct edge{    LL a[101][101];};edge A,B;edge multi(edge x,edge y){    edge C;    memset(C.a,0,sizeof(C.a));    for(int i = 1; i <= n; i ++)        for(int j = 1; j <= n; j++)            for(int k = 1; k <= n; k ++)                C.a[i][j]+=(x.a[i][k]*y.a[k][j])%mod,C.a[i][j]%=mod;    return C;}int main(){    cin >> n >> k;    for(int i = 1; i <= n; i ++)        for(int j = 1; j <= n; j ++)            cin >> A.a[i][j];    for(int i = 1; i <= n; i ++)        B.a[i][i]=1;    while(k)    {        if(k&1)B=multi(B,A);        A=multi(A,A);        k>>=1;    }    for(int i = 1; i <= n; i ++)    {        for(int j = 1; j <= n; j ++)            cout << B.a[i][j] << ' ';        cout << endl;    }}

逆元

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;long long A[5000000];int n,p;int main() {    A[1]=1;    cin >> n >> p;    for(int i=2; i<=n; i++) {        A[i]=((p-p/i)*A[p%i]%p+p)%p;    }    for(int i=1; i<=n; i++)printf("%d\n",A[i]);}

高斯消元

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define eps 1e-10using namespace std;double a[200][200];int n;void guass() { for(int i=1; i<=n; i++) { int wz=0; for(int j=i; j<=n; j++) if(fabs(a[j][i])>eps) { wz=j; break; } if(wz==0) { puts("No Solution"); exit(0); } if(wz!=i)swap(a[i],a[wz]); double tmp=a[i][i]; for(int j=1; j<=n+1; j++)a[i][j]/=tmp; for(int j=i+1; j<=n; j++) { double tmp=a[j][i]; for(int k=1; k<=n+1; k++)a[j][k]-=a[i][k]*tmp; } } for(int i=n; i>=1; i--) for(int j=i+1; j<=n; j++) if(fabs(a[i][j])>eps) a[i][n+1]-=a[j][n+1]*a[i][j],a[i][j]=0;}int main() {// freopen("a.in","r",stdin); cin >> n; for(int i=1; i<=n; i++) for(int j=1; j<=n+1; j++) cin >> a[i][j]; guass(); for(int i=1; i<=n; i++)printf("%.2lf\n",a[i][n+1]);}

图论

割点

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int N = 20010,M = 200010;struct edge { int next,to;} e[M];int head[N],tot;void add(int x,int y) { e[++tot].next = head[x]; head[x] = tot; e[tot].to = y;}int n,m,low[N],dfn[N],cnt,vis[N];void tarjan(int x,int f) { int num=0; dfn[x]=++cnt; low[x]=cnt; for(int i=head[x]; i; i=e[i].next) { int v=e[i].to; if(v == f)continue; if(!dfn[v]) { num++; tarjan(v,x); low[x]=min(low[x],low[v]); if(f!=0 && low[x]>=dfn[x]) vis[x]=1; } else low[x]=min(low[x],dfn[v]); } if(f==0 && num>=2) vis[x]=1;}int main() { scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int a,b; scanf("%d%d",&a,&b); add(a,b),add(b,a); } int ans=0; for(int i=1; i<=n; i++) if(!dfn[i])tarjan(i,0); for(int i=1;i<=n;i++) if(vis[i]) ans++; printf("%d\n",ans); for(int i=1; i<=n; i++) if(vis[i]) printf("%d\n",i);}

最小生成树

#include
    
     #include
     
      #include
      
       #define N 5001using namespace std;int n,m;int a,b,c,ans;int flag[N],map[N][N],dis[N];int main(){    memset(map,0x3f,sizeof(map));    memset(dis,0x3f,sizeof(dis));    cin>>n>>m;    for(int i=1;i<=m;i++)    {        cin>>a>>b>>c;        map[a][b]=min(map[a][b],c);        map[b][a]=map[a][b];    }    dis[1]=0;    int k;    for(int i=1;i<=n;i++)    {        k=0;        for(int j=1;j<=n;j++)            if(!flag[j]&&dis[j]

倍增

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 500100;struct edge {    int next,to;} e[N<<1];int head[N],tot;void add(int x,int y) {    e[++tot].next=head[x];    head[x]=tot;    e[tot].to=y;}int n,m,rt;int f[N][32],deep[N];void dfs(int x,int fa) {    f[x][0]=fa;    deep[x]=deep[fa]+1;    for(int i=1; i<=21; i++)f[x][i]=f[f[x][i-1]][i-1];    for(int i=head[x]; i; i=e[i].next) {        int v=e[i].to;        if(v == fa) continue;        dfs(v,x);    }}int LCA(int x,int y) {    if(deep[x]
         
          =0; i--) if(delta >= (1<
          
           =0;i--){ if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i]; } } if(x!=y) x=f[x][0]; return x;}int main() { scanf("%d%d%d",&n,&m,&rt); for(int i=1; i<=n-1; i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } deep[rt]=1; dfs(rt,0); while(m--){ int a,b; scanf("%d%d",&a,&b); printf("%d\n",LCA(a,b)); }}

SPFA

#include
    
     using namespace std;queue
     
      q;struct edge{    int next,to,dist;} e[500007];int head[500007],tot;inline void add(int x,int y,int z){    e[++tot].next=head[x];    e[tot].to=y;    e[tot].dist=z;    head[x]=tot;}int n,m,s;int f,g,w;long  vis[500007],dis[500010];void spfa(){    while(!q.empty())q.pop();    for(int i=1; i<=n; i++)dis[i]=2147483647;    dis[s]=0;    q.push(s);    vis[s]=1;    while(!q.empty())    {        int u=q.front();        q.pop();        vis[u]=0;        for(int i=head[u],v; v=e[i].to,i; i=e[i].next)            if(e[i].dist+dis[u]
      
       >n>>m>>s;    for(int i=1; i<=m; i++)cin>>f>>g>>w,add(f,g,w);    spfa();    for(int i=1;i<=n;i++)cout<
       
        <<' ';    return 0;}

负环

#include
    
     #include
     
      #include
      
       #include
       
        #define N 20000using namespace std;struct edge {    int next , to , dist;} e[N];int head[N] , tot , vis[N] , dis[N] , T , n , m , num[N];inline void add(int x,int y,int z) {    e[++tot].next = head[x];    e[tot].to = y;    e[tot].dist = z;    head[x] = tot;}bool spfa(int s) {    memset(dis,0x3f3f,sizeof(dis));    queue
        
         q;    vis[s] = 1;    q.push(s);    num[s]++;    dis[s]=0;    while(!q.empty()) {        int u = q.front();        q.pop();        vis[u] = 0;        for(int i = head[u],v; i,v=e[i].to; i=e[i].next)            if(dis[v]>dis[u]+e[i].dist) {                num[v]++;                if(num[v]>=n)return true;                dis[v] = dis[u]+e[i].dist;                if(!vis[v])                    vis[v] = 1,q.push(v);            }    }    return false;}int main() {    cin >> T;    while(T--) {        scanf("%d%d",&n,&m);        memset(vis,0,sizeof(vis));        memset(num,0,sizeof(num));        memset(head,0,sizeof(head));        tot = 0;        for(int i = 1; i <= m; i ++) {            int a , b , w;            scanf("%d%d%d",&a,&b,&w);            if(w>=0) {                e[++tot].next = head[a];                e[tot].to = b;                e[tot].dist = w;                head[a] = tot;                e[++tot].next = head[b];                e[tot].to = a;                e[tot].dist = w;                head[b] = tot;            } else {                e[++tot].next = head[a]                                ;                e[tot].to = b;                e[tot].dist = w;                head[a] = tot;            }        }        if(spfa(1))            printf("YE5\n");        else printf("N0\n");    }}

堆优化迪杰斯特拉

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long LL;const int N = 100010,M = 200020;struct edge {    int next,to,dis;} e[M];struct node {    int id,dis;    node() {}    node(int a,int b) {        id=a,dis=b;    }};priority_queue
         
          q;bool operator <(const node &a,const node &b) { return a.dis>b.dis;}int n,m,st,dis[N],head[N],tot;void add(int x,int y,int z) { e[++tot].next = head[x]; head[x] = tot; e[tot].to = y; e[tot].dis = z;}void dijkstra(int s) { memset(dis,0x3f,sizeof(dis)); dis[s]=0; q.push(node(s,0)); while(!q.empty()) { node x=q.top(); q.pop(); int u=x.id,d=x.dis; if(dis[u]!=d) continue; for(int i=head[u]; i; i=e[i].next) { int v=e[i].to; if(dis[v]>dis[u]+e[i].dis) { dis[v]=dis[u]+e[i].dis; q.push(node(v,dis[v])); } } }}int main() { scanf("%d%d%d",&n,&m,&st); for(int i=1; i<=m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } dijkstra(st); for(int i=1; i<=n; i++)printf("%d ",dis[i]);}

匈牙利

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int N = 2000;int n,m,M;int _map[N][N],result[N],vis[N];bool dfs(int u) { for(int v=1; v<=m; v++) if(!vis[v]&&_map[u][v]) { vis[v]=1; if(!result[v]||dfs(result[v])) { result[v]=u; return true; } } return false;}int solve() { int ans=0; for(int u=1; u<=n; u++) { memset(vis,0,sizeof(vis)); if(dfs(u))ans++; } return ans;}int main() { scanf("%d%d%d",&n,&m,&M); for(int i=1; i<=M; i++) { int a,b; scanf("%d%d",&a,&b); _map[a][b]=1; } printf("%d\n",solve());}

数据结构

树状数组

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 500001;int tree[N],n,m;int lowbit(int x){    return x&(-x);}void add(int x,int y){    while(x<=n)    {        tree[x]+=y;        x+=lowbit(x);    }}int sum(int x){    int ans=0;    while(x!=0)    {        ans+=tree[x];        x-=lowbit(x);    }    return ans;}int main(){    scanf("%d%d",&n,&m);    for(int i=1; i<=n; i++)    {        int a;        scanf("%d",&a);        add(i,a);    }    for(int i=1; i<=m; i++)    {        int opt,x,y;        scanf("%d%d%d",&opt,&x,&y);        if(opt==1)add(x,y);        else if(opt==2)printf("%d\n",sum(y)-sum(x-1));    }}

ST表

#include 
    
     using namespace std;int n,m,ST[100010][30];void work(){    for(int j=1;j<=21;j++){        for(int i=1;i+(1<
     
      <=n;i++)            ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);    }}int find(int l,int r){    int k=log2(r-l+1);    return max(ST[l][k],ST[r-(1<

线段树

#include
    
     using namespace std;long long n,p,a,b,m,x,y,ans;struct node {    long long l,r,w,f;} tree[500000];inline void build(int k,int ll,int rr) {    tree[k].l=ll,tree[k].r=rr;    if(tree[k].l==tree[k].r) {        cin>>tree[k].w;        return;    }    int m=(ll+rr)/2;    build(k<<1,ll,m);    build(k<<1|1,m+1,rr);    tree[k].w=tree[k<<1].w+tree[k<<1|1].w;}inline void down(int k) {    tree[k<<1].f+=tree[k].f;    tree[k<<1|1].f+=tree[k].f;    tree[k<<1].w+=tree[k].f*(tree[k<<1].r-tree[k<<1].l+1);    tree[k<<1|1].w+=tree[k].f*(tree[k<<1|1].r-tree[k<<1|1].l+1);    tree[k].f=0;}inline void ask_interval(int k) {    if(tree[k].l>=a&&tree[k].r<=b) {        ans+=tree[k].w;        return;    }    if(tree[k].f) down(k);    int m=(tree[k].l+tree[k].r)/2;    if(a<=m) ask_interval(k<<1);    if(b>m) ask_interval(k<<1|1);}inline void change_interval(int k) {    if(tree[k].l>=a&&tree[k].r<=b) {        tree[k].w+=(tree[k].r-tree[k].l+1)*y;        tree[k].f+=y;        return;    }    if(tree[k].f) down(k);    int m=(tree[k].l+tree[k].r)/2;    if(a<=m) change_interval(k<<1);    if(b>m) change_interval(k<<1|1);    tree[k].w=tree[k<<1].w+tree[k<<1|1].w;}int main() {    cin>>n>>m;    build(1,1,n);    for(int i=1; i<=m; i++) {        cin>>p;        ans=0;        if(p==1) {            cin>>a>>b>>y;            change_interval(1);        }        if(p==2) {            cin>>a>>b;            ask_interval(1);            cout<
     
      <

字符串

kmp

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char s1[2000000],s2[2000000];int kmp[2000000];int main() { cin >> s1 >> s2; int len1=strlen(s1); int len2=strlen(s2); int k=0; for(int i=1; i

DP

最长公共子序列

// luogu-judger-enable-o2#include
    
     using namespace std;int n,a[200000],b[200000];int dp[2000][2000];int main(){    cin>>n;    for(int i=1; i<=n; i++)        cin>>a[i];    for(int i=1; i<=n; i++)        cin>>b[i];    for(int i=1; i<=n; i++)        for(int j=1; j<=n; j++)        {            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);            if(a[i]==b[j])                dp[i][j]=max(dp[i][j],dp[i-1][j-1])+1;        }    cout<

转载于:https://www.cnblogs.com/ifmyt/p/9909218.html

你可能感兴趣的文章
NO.44 文字超出显示省略号后面小图标紧跟文字后面
查看>>
注册dll
查看>>
5.27 考试 + 总结
查看>>
Magento 2.2.5和2.2.6的bug 产品设置special price又删除后价格排序有误
查看>>
P2015 二叉苹果树
查看>>
ASP.NET MVC一次删除多笔记录
查看>>
使用HashSet<>去除重复元素的集合
查看>>
JSON 小记
查看>>
《Linux命令行与shell脚本编程大全 第3版》高级Shell脚本编程---06
查看>>
[1-4] 把时间当做朋友（李笑来）Chapter 4 【开拓我们的心智】 摘录
查看>>
redis数据过期策略【转】
查看>>
ASP.net MVC4 View设置Html代码显示为文本字符问题
查看>>
go语言之进阶篇关闭channel
查看>>
《那些年啊，那些事——一个程序员的奋斗史》——65
查看>>
opencv 内存溢出问题
查看>>
简单的静态网页（宠物网）
查看>>
HDU 5410(2015多校10)-CRB and His Birthday(全然背包)
查看>>
hdu 2874 Connections between cities（st&rmq LCA）
查看>>
【Linux基础学习之五】Linux管理命令的基础学习（df、du、free、kill、tar等）
查看>>
20171115
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-14 12:25:48   当前IP: 3.144.42.2   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我