模板集合

佚名 6年前 (2019-04-10) 随笔 1001人围观抢沙发百度已收录

并查集

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,z,x,y,f[10000+5];
 4 
 5 int find(int x)
 6 {
 7     return x==f[x]?x:f[x]=find(f[x]);
 8 }
 9 
10 void merge(int x,int y)
11 {
12     f[find(x)]=find(y);
13 }
14 
15 int main()
16 {
17     scanf("%d%d",&n,&m);
18     for(int i=1;i<=n;i++) f[i]=i;
19     for(int i=1;i<=m;i++) 
20     {
21         scanf("%d%d%d",&z,&x,&y);
22         if(z==1) merge(x,y);
23         if(z==2)
24         {
25             if(find(x)==find(y)) printf("Y\n");
26             else printf("N\n");
27         }
28     }
29     return 0;
30 }

快速幂||取余运算

输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long a,b,c;
 4 
 5 int main()
 6 {
 7     scanf("%lld%lld%lld",&a,&b,&c);
 8     if(a==1&&b==0&&c==1)
 9     {
10         printf("1^0 mod 1=0");
11         return 0;
12     }
13     
14     long long ans=1,base=a,b2=b;
15     while(b!=0)
16     {
17         if((b & 1)!=0)
18         ans=ans*base%c;
19         base=base*base%c;
20         b>>=1; 
21     }
22     printf("%lld^%lld mod %lld=%lld",a,b2,c,ans);
23     return 0;
24 }

最小/大生成树：kruscal+重建树

 1 struct kedge{
 2     int u,v,limit;
 3     bool operator < (const kedge &x) const{
 4         return limit < x.limit;// > 即最大生成树 
 5     }
 6 }ke[M<<1];
 7 
 8 struct edge{
 9     int v,limit,nxt;
10 }e[M<<1];int tot,head[N];
11 
12 void build_tree(int u,int v,int w) {e[++tot] = (edge){v,w,head[u]}; head[u] = tot;}
13 
14 //-----------------------------------------------------------------
15 int find(int i) {if(f[i] == i) return i;f[i] = find(f[i]);return f[i]; }
16 void kruscal(){
17     sort(ke+1,ke+m+1);
18     up(i,1,n) f[i] = i;
19     int cnt = 0;
20     up(i,1,m)
21     {
22         if(cnt == n-1) break;
23         if(find(ke[i].u) != find(ke[i].v))
24         {
25             f[f[ke[i].u]] = f[ke[i].v];
26             cnt++;
27             build_tree(ke[i].u,ke[i].v,ke[i].limit);
28             build_tree(ke[i].v,ke[i].u,ke[i].limit);//debug ke[i].u -> ke[i].v;
29         }
30         else continue;
31     }
32 }

矩阵快速幂

给定n*n的矩阵A，求A^k

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 const int mod  = 1e9 + 7;
 2 long long n,k;
 3 
 4 struct matrix
 5 {
 6     long long g[101][101]; 
 7 }a,res;
 8 
 9 inline matrix Multiple(matrix x,matrix y)
10 {
11     matrix z;
12     for (int i = 1;i <= n;i++)
13         for (int j = 1;j <= n;j++)    
14             z.g[i][j] = 0;
15     for(int i = 1;i <= n; i++)
16         for(int j = 1;j <= n; j++)
17             for(int k = 1;k <= n; k++)
18                 z.g[i][j] = z.g[i][j]%mod + x.g[i][k] * y.g[k][j]%mod;
19     return z;
20 }
21 
22 void quickpow(long long k)
23 {
24     for(int i = 1;i <= n;i++) res.g[i][i] = 1;
25     matrix temp = a;
26     while(k)
27     {
28         if(k & 1)
29         {
30             res = Multiple(res,temp);
31         }
32         temp = Multiple(temp,temp);
33         k >>= 1;
34     }
35 }
36 
37 int main()
38 {
39     n = read; k = read;
40     for(int i = 1;i <= n; i++)
41     {
42         for(int j = 1;j <= n; j++)
43         a.g[i][j] = read;
44     }
45     quickpow(k);
46     for(int i = 1;i <= n; i++)
47     {
48         for(int j = 1;j <= n; j++)
49         printf("%lld ",res.g[i][j]%mod);
50         printf("\n");
51     }
52 }