跳转至

2、NOIP必会模板

一、 最小生成树

1. Prim

C++
 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
void prim() 
{
      //邻接矩阵 a[i][j] 表示 i,j 之间边权 
      //先选取一个点(now)作起始点，然后选择它邻近的权值最小的点 
      int now=1,minn=inf,node;
      for(int i=1;i<=n;i++)
         low[i]=a[1][i];       //low[i]的值为i点到标记点的最小距离
      v[1]=1;
      for(int Cs=1;Cs<n;Cs++) //找n-1条边 
      {
          minn=inf; 
          for(int i=1;i<=n;i++) 
          if(!v[i]) {
              if(low[i]<minn) {
                  minn=low[i];
                  node=i;   
               }
          }
          v[node]=1;
          ans += minn;
          for(int i=1;i<=n;i++)
             if(!v[i]) low[i]=min(low[i],a[node][i]);
          //更新low值  
      }
}

2.Kruscal

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void Kruscal(){
for(int i=1;i<=n;i++) f[i]=i;
sort(a+1,a+m+1,comp);    // 边 按照从小到大排序 
for(int i=1;i<=m;i++) {
   int x=find(a[i].x),y=find(a[i].y);    //find 函数 找父亲 
   if(x!=y) {
     ans+=a[i].v;
     f[x]=y;
   }
 }
}

3.堆优化的Prim 思路与MST1完全一样，用堆维护最小值

C++
 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
Struct Eage {     // 小根堆          
      int to,dis;
      Eage(int to,int dis):to(to),dis(dis){}
      friend bool operator < (Eage a,Eage b){
           return a.dis>b.dis;
      }
};
vector<Eage>g[100005];
priority_queue<Eage>q;
void zprim() {
      for(int i=1;i<=m;i++) {
        cin>>a>>b>>c;      //a,b 双向之间 边权为 c 
        g[a].push_back(Eage(b,c));
        g[b].push_back(Eage(a,c));
      }
      v[1]=1;
      for(int i=0;i<g[1].size();i++)
        q.push(g[1][i]);
      int num=n-1;
      while(num&&q.size()) {
        Eage tmp=q.top();
        q.pop();
        if(v[tmp.to]) continue;
        v[tmp.to]=1;
        num--;
        ans+=tmp.dis;
        int t=tmp.to;
        for(int i=0;i<g[t].size();i++)
        if(!v[g[t][i].to])
             q.push(g[t][i]);
      }
}

二、数论

1.exgcd

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int exgcd(int a,int b,int &x,int &y)
{
   if(b==0){
     x=1;y=0;
     return a;
   }
   int d=exgcd(b,a%b,x,y);
   int tmp=x;
   x=y;
   y=tmp-a/b*y;
   return d;
}

2.fastpower 快速幂

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int fastpower(int a,int b)
{
   int r=1,c=a;
   while(b>0){
     if(b%2==1) r*=c;
     c*=c;
     b/=2;
   }
   return r;
}

3.求矩阵乘法 A(nm) * 矩阵 B (mp) = 矩阵 C

C++
1
2
3
4
5
6
void mul(){
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        for(int k=1;k<=p;k++)
            c[i][j]+=a[i][j]*b[j][k];
}

4. 乘法逆元 扩展欧几里得求逆元

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int extgcd(int a, int b, int& x, int& y) {
  int d=a;
  if(b!=0){
     d=extgcd(b,a%b,y,x); //d为最大公约数 
     y-=(a/b)*x;
  }
  else{x=1;y=0;}   
  return d;
}
int mod_inverse(int a, int m)  //在模m下a的逆元 
{
  int x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}

5.矩阵快速幂

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void mul1() {  //求 矩阵 A 的 b 次方 
      memset(b,0,sizeof(b));
      for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                b[i][j]+=a[i][j]*c[j][k];
      memcpy(a,b,sizeof(a)); 
}
void mul2(){ //自乘矩阵 n 行 n 列 
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                b[i][j]+=c[i][k]*c[k][j];
    memcpy(c,b,sizeof(c)); 
}
void power(){
    while(b){
        if(b&1)  mul1();
        mul2();
        b>>=1;
    }
}

6.素数筛

C++
1
2
3
4
5
6
7
8
9
tot=0;
for(i=2;i<=n;i++){
     if(!v[i]) prime[++tot]=i;
     for(j=1;j<=tot;j++){
         if(i*prime[j]>n) break;
         v[i*prime[j]]=true;
         if(i%prime[j]==0) break;
      }
}

三、背包

1. 背包

C++
1
2
3
for(int i=1;i<=n;i++)
   for(int j=m;j>=v[i];j--)
      f[j]=max(f[j],f[j-v[i]]+c[i]);

2.完全背包

C++
1
2
3
for(int i=1;i<=n;i++)
   for(int j=v[i];j<=m;j++)
      f[j]=max(f[j],f[j-v[i]]+c[i]);

3.多重背包 二进制优化

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
for(int i=1;i<=n;i++){
   t=1;
   cin>>x>>y>>s;
   while(s>=t){
       n1++;
       v[n1]=x*t;
       c[n1]=y*t;
       s-=t;
       t*=2;
    }
    n1++;
    v[n1]=x*s;
    c[n1]=y*s;
}

for(int i=1;i<=n1;i++){
   for(int j=m;j>=v[i];j--)
   f[j]=max(f[j],f[j-v[i]]+c[i]);
}

4. 多重背包

C++
1
2
3
4
5
6
7
for(int k=1;k<=n;k++)
   for(int j=m;j>=0;j--)
       for(int i=1;i<=a[k][0];i++)
           if(j>=v[a[k][i]]){     
             int tt=a[k][i];
             f[j]=max(f[j],f[j-v[tt]]+c[tt]);
           }

5. 多重背包 单调队列优化

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
for(int i=1;i<=n;i++){
   ni=num[i];vi=v[i];ci=c[i];
   for(int b=0;b<vi;b++){
      head1=head2=0;
      tail1=tail2=0;
      k=0;
      for(int j=b;j<=m;j+=vi){
         if(tail1-head1==ni+1)
           if(q2[head2+1]==q1[head1+1])  head2++;
         head1++;
         int t=f[j]-k*ci;
         tail1++;
         q1[tail1]=t;
         while(head2!=tail2&&q2[tail2]<t) tail2--;
         tail2++;
         q2[tail2]=t;
         f[j]=q2[head2+1]+k*ci;
         k++;
      }
   }
}

6.二维费用背包

C++
1
2
3
4
      for(int i=1;i<=n;i++)
           for(int j1=m1;j1>=v1[i];j1--)
               for(int j2=m2;j2>=v2[i];j2--)
                   f[j1][j2]=max(f[j1][j2],f[j1-v1[i]][j2-v2[i]]+c[i]);

四、线段树

C++
  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
int mountain(int o) {
      mx[o]=max(mx[lch],mx[rch]);
      mn[o]=min(mn[lch],mn[rch]);
      sum[o]=sum[lch]+sum[rch];
}

void build(int l,int r,int o) { //建树 
      if(l==r) {
           mx[o]=mn[o]=sum[o]=a[l];
           return ;       }
      build(l,mid,lch);
      build(mid+1,r,rch);
      mountain(o);
      return ;
}

void push_down(int l,int r,int o) {//下放 
      if(add[o]) {
           if(flag[o]) {
               set[o]+=add[o];add[o]=0;
           } else {
               mn[lch]+=add[o];  mn[rch]+=add[o];
               mx[lch]+=add[o];  mx[rch]+=add[o];
               add[lch]+=add[o]; add[rch]+=add[o];
               sum[lch]+=((LL)(mid-l+1))*add[o];
               sum[rch]+=((LL)(r-mid))*add[o];
               add[o]=0;
           }
      }

      if(flag[o]) {
         mn[lch]=mn[rch]=mx[lch]=mx[rch]=set[o];
         set[lch]=set[rch]=set[o];
         sum[lch]=(mid-l+1)*set[o];
         sum[rch]=(r-mid)*set[o];
         add[lch]=add[rch]=0;
         flag[lch]=flag[rch]=1;
         flag[o]=set[o]=0;
      }
}

//区间加  [x,y] 每个数 + z
void add_work(int l,int r,int o) {
      if(x<=l&&r<=y) {
           add[o]+=z; mx[o]+=z; mn[o]+=z;
           sum[o]+=((LL)(r-l+1))*z;
           return ;
      }
      push_down(l,r,o);
      if(mid>=x) add_work(l,mid,lch);
      if(mid<y) add_work(mid+1,r,rch);
      mountain(o);
}

//区间  [x,y] 每个数 变为 z
void set_work(int l,int r,int o) {
      if(x<=l&&r<=y) {
           add[o]=0;     //把之前区间加覆盖
           lag[o]=1;//表示此区间有修改
           mx[o]=mn[o]=set[o]=z;
           sum[o]=((LL)(r-l+1))*z;
           return ;
      }

      push_down(l,r,o);//标记下放 
      if(mid>=x) set_work(l,mid,lch);
      if(mid<y) set_work(mid+1,r,rch);
      mountain(o);
}

//区间求和 查询 sum [x,y]     
long long query_sum(int l,int r,int o) {
      if(x<=l&&r<=y) return sum[o];
      push_down(l,r,o);
      LL s=0;
      if(mid>=x) s=query_sum(l,mid,lch);
      if(mid<y) s+=query_sum(mid+1,r,rch);
      mountain(o);
      return s;
}

// 查询 max [x,y] 
long long query_max(int l,int r,int o) {
      if(x<=l&&r<=y) return mx[o];
      push_down(l,r,o);
      LL s=-INF;
      if(mid>=x) s=query_max(l,mid,lch);
      if(mid<y) s=max(s,query_max(mid+1,r,rch));
      mountain(o);
      return s;
}

// 查询 min [x,y] 
long long query_min(int l,int r,int o) {
      if(x<=l&&r<=y) return mn[o];
      push_down(l,r,o);
      LL s=INF;
      if(mid>=x) s=query_min(l,mid,lch);
      if(mid<y) s=min(s,query_min(mid+1,r,rch));
      mountain(o);
      return s;
}

五、树状数组

C++
 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
#define lowbit(x) (x&(-x))
// 区间和 + 单点修改 
void Add(int k,const int &delta){ // k位置 delta数值 
  while(k<=n){ 
     tr[k]+=delta;   // 每个位置 加delta 
     k+=lowbit(k);    // 往树上走 
  }
}

void BuildTree() {
      for(int i = 1;i <= n;i++) Add(i,a[i]);
}

int GetSum(int k) { //前缀和 
      int ans = 0;
      while(k) {
        ans += tr[k];
        k -= lowbit(k);// 获取每个树上值
      }  
   return ans;
}

// 区间加 + 单点查询 
void LinePlus(const int &l,const int &r,const int &delta) {
      Add(l,delta); 
      Add(r+1,-delta);
}

**ST**
void ST()
{//f[i][j]表示i位置向右延伸2^j范围内的最值
  for(int j = 1; j <= n; j++) f[j][0] = a[j];//初始化
  int m = log(n)/log(2);//换底公式
  for(int i = 1; i <= m; i++) {//递推(DP)
     for(int j = n; j > 0; j--) {//复杂度nlogn 
       f[j][i] = f[j][i-1];//第一个2^(i-1)
       if(j+(1<<(i-1)) <= n)
 f[j][i] = max(f[j][i], f[j + (1<<(i-1))][i-1]);//第二个 
      //两个2^(i-1)取最值得到当前位置的2^i最值
     }
  }
}

int RMQ(int l,int r) {//如果求最小值把所有max换成min
      int m = log(r-l+1)/log(2);    //取m为恰不超过区间范围的2^m
      return max(f[l][m], f[r-(1<<m)+1][m]);   //在完全覆盖的情况下取最值
}

六、高精

1、进位

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void jinwei(){
    for(int i=1;i<=len;i++)
      if(c[i]>=10)    
      {
           c[i+1]+=c[i]/10;
           c[i]%=10;
           if(i==len) len ++;
      }         
      while(c[len]==0) len--;        
}

2、高精加

C++
1
2
3
      for(int i=1;i<=len;i++)
          c[i]=a[i]+b[i];
      jinwei();

3、高精减 a 被减数 b 减数

C++
1
2
3
4
5
6
7
8
9
      for(int i=0,j=0;i<lena||j<lenb;i++,j++){
           if(a[i]<b[j]){
               a[i]+=10;
               a[i+1]--;
           }         
           ans[i]=a[i]-b[j];
      }
      int t=0; 
      while(c[lena]==0) lena--;

4、高精乘 a * b = c

C++
1
2
3
4
5
6
7
8
      for(int i=0;i<lena;i++)
       for(int j=0;j<lenb;j++)
       {
           c[i+j]+=a[i]*b[j];
       }
      int lenc=lena+lenb-1;
      jinwei();
}

5、高精除低精 a / x

C++
1
2
3
4
5
  for(int i=len;i>0;i--)
      {
           a[i-1]+=(a[i]%x)*10;
           a[i]=a[i]/x;
      }

6、高精%低精 a % x

C++
1
2
3
4
5
for(int i=len;i>0;i--)
  { 
     b=b*10+a[i]; 
     b=b%x;
  }

七、归并排序

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
      void mergesort(int l,int r){
           if(l==r)return ;
           int m=(l+r)/2;
           mergesort(l,m);
           mergesort(m+1,r);
           int i=l, j=m+1,k=l;
           while(i<=m&&j<=r){
               if(a[i]<=a[j]){
                   r[k]=a[i];
                   i++;k++;
               }
               else { 
                   r[k]=a[j];
                   j++;k++;
               }
           }
           while(i<=m){ r[k]=a[i]; i++;k++;}
           while(j<=r){ r[k]=a[j]; j++;k++;}
           for(int i=l;i<=r;i++)  a[i]=r[i];
      }

八、二分图

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
for(int i=1;i<=n;i++)
{
      memset(bo,0,sizeof(bo));
      if(dfs(i)) ans++;
}
bool dfs(int x) {
      for(int i=1;i<=a[x][0];i++) {// a 邻接表 
           if(!bo[a[x][i]]) {
               if(find(link[a[x][i]])||link[a[x][i]]==0) 
               { //判断没有连过边或可以换 
                    link[a[x][i]]=x; 
                    // 与右侧a[x][i]相连的为x 
                    return 1;
               }
           }}
      return 0;
}

九、并查集

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void ff() {
    for(int i=1;i<=n;i++) 
           fa[i]=i,r[i]=0;//r[i]表示以i为根的树的高度 
} 

void un(int x,int y) {//find(x) 找 x 父亲
      int f1=find(x),f2=find(y);
      if(f1==f2) return;
      if(r[f1]==r[f2]) r[f2]++,fa[f1]=f2;
      else if(r[f1]>r[f2]) fa[f2]=f1;
      else fa[f1]=f2;
}

十、SPFA

C++
 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
vector<int>v[MN],w[MN];
deque<int>q; 
void spfa()
{
      for(int i=1;i<=n;i++) dis[i]=INF;
      dis[s]=0;
      q.push_back(s);
      while(!q.empty()){
           int x=q.front();q.pop_front();
           v[x]=0;
           for(int i=0;i<v[x].size();i++){
               int xx=v[x][i];
               if(dis[xx]>dis[x]+w[x][i]){
                    dis[xx]=dis[x]+w[x][i];
                    if(!v[xx])
                    {
                     v[xx]=1;
                     if(!q.empty()&&dis[xx]<dis[q.front])
                        q.push_front(xx);
                     else q.push_back(xx);
                    }
                 }
           }
       }
}

十一、dijkstra

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
      typedef pair<long long,int> pii;
      priority_queue<pii,vector<pii>,greater<pii> > ty;   //重载小根堆
      for(int i=1;i<=n;++i) dis[i]=INF;
      dis[1]=0;
      ty.push(make_pair(0,1));
      while(1){
           if(ty.empty()){
               printf("-1\n");
               return 0;}
           int x=ty.top().second;ty.pop();
           if(e[x]==1) continue;
           e[x]=1;
           if(x==n) break;
           for(int i=0;i<u[x].size();i++){
               int v=u[x][i];
               if(e[v]==0&&dis[v]>dis[x]+w[x][i]){
                    dis[v]=dis[x]+w[x][i];
                    ty.push(make_pair(dis[v],v));
               }
           }
      }

十二、KMP

C++
 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
/*kmp求模式串在文本串出现次数，结果可能重叠*/
int kmp() {
      int i,j,ans=0;
      for(i=0,j=0;i<ssl;i++) {
           while(j!=-1&&s[j]!=ss[i]) j=next[j];
           j++;
           if(j==sl) {
               j=next[j];
               ans++;
           }
      }
      return ans;

}

/*kmp求next未优化*/
void gets_next() {     //s[i]表示前缀，s[j]表示后缀 
      int i=0,j=-1;
      next[0]=-1;      //开头赋-1
      while(i<n) {
           if(s[i]==s[j]||j==-1) { //已知0...i求i+1，相等则next[i+1]=i+1
               i++,j++;
               next[i]=j;
           }
           else j=next[j];  //否则递归求next
      }
      return ;
}

/*kmp优化next*/
void gets_next() {    
      int i=0,j=-1;
      next[0]=-1;
      while(i<n) {
       if(s[i]==s[j]||j==-1) { //s[i]表示前缀，s[j]表示后缀  
           i++,j++;  
      //较之前next数组求法，改动在下面4行
               if(s[i]!=s[j]) next[i]=j; //原先只有这一句   
               else next[i]=next[j];    
           }
       else {//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续
             // 递归，j = next[j] = next[next[j]] 
               j=next[j];
}
      }
      return ;
}

/* kmp匹配过程 */
int KmpSearch(char* s, char* p) { //s文本串，p模式串
  int i = 0,j = 0; 
  int sLen = strlen(s),pLen = strlen(p); 
  while (i < sLen && j < pLen)  { 
     //如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++   
     if (j == -1 || s[i] == p[j]) 
       i++,j++; 
     else {
       //如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]       
       //next[j]即为j所对应的next值    
       j = next[j];
     }
  }

  if (j == pLen) return i - j;
  else return -1;
}

十三、字符串hash

C++
 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
#define base 31 // 31 131 1313 13131 131313 etc..
struct String_hash {
   char s[MAXX];int len,st;
   ulg Hash[MAXX],h[MAXX]; 
   inline ulg gethash(int l,int r) { //取出l到r的hash （BDKR） 
   return Hash[r]-Hash[l-1]*b[r-l+1];
   }

  void BKDRHash() {//最常用的hash函数 
     for (int i = 1; i <= len; i++)
     Hash[i] = Hash[i-1] * base + s[i-1]; 
  }

  ulg JSHash() { //另外一种hash函数
   register ulg _hash = 1315423911; 
   for (int i = 1; i <= len; i++)
     _hash ^= ((_hash << 5) + s[i-1] + (_hash >> 2));
   return _hash;    
  }

  void make(register int x) { //算出长为x的所有子串hash 并sort 方便查找 
        for(int i = 1;i <= len-x+1; i++) 
         h[i] = gethash(i,i+x-1);
        sort(h+1,h+len-x+2);st = 1;
      }
};

inline void init() {//b [i] 为base的i次方 
      b[0] = 1;
      for (int i = 1; i < MAXX; i++)
       b[i] = b[i-1]*base;
}

//   hash_table
#define mod 1000007
struct hash_table {
      int val;
      hash_table():val(0){}
      hash_table(int val):val(val){}
};

vector<hash_table> tab[mod];
unsigned int f(int x) {
      return ((unsigned int)(7*(x-5)+x*31))%mod;// 求hash值,注意负数 
}

void insert_h(register int v) {//插入v 
      tab[f(v)].push_back(v);
}

bool query_h(register int x) {//询问x是否出现过 
      register unsigned int tmp = f(x);
      for (int i = 0; i < tab[tmp].size(); i++)
         if(tab[tmp][i].val == x)  return true;    
      return false;
}

十四、读入优化

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
inline int read(){
      register char ch; register int t = 0; 
      register bool flag = 0;
      while (!((((ch = getchar()) >= '0') && (ch <= '9')) || (ch == '-')));
      ch == '-' ? flag = 1 : t = ch - '0';
      while (((ch = getchar()) >= '0') && (ch <= '9')) t = t * 10 + ch - '0';
      return flag ? -t : t;
}

inline void write(int t)
{
      if (t < 0) {putchar('-'); t = -t;}
      if (t >= 10) write(t / 10);
      putchar(t % 10 + '0');
}

十五、Trie树

C++
 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
void init()//加入字典树
{
      int now=0;
      char *p=s;//s 为 加入字典中的串 
      while(*p) {
           int idx=(int)(*p-'a');
           if(!f[now].next[idx]) {
               tot++;
               f[now].next[idx]=tot;//新结点 
           }
           now=f[now].next[idx];
           f[now].cnt++;//以now为前缀单词数 
           p++;
      }
}

void search()//询问 前缀
{
      int now=0;
      char *p=s;// 询问 以 s 为前缀的单词数  即cnt 
      while(*p) {
           int idx=(int)(*p-'a');
           if(!f[now].next[idx]){//不存在 输出 0 
               printf("0\n");  return ;
           }
           now=f[now].next[idx];
           p++;
      }
      printf("%d\n",f[now].cnt);
      return;
}

void _delete()//删除某个单词
{
      int now=0,mm=0;
      char *p=s;
      while(*p) {
           int idx=(int)(*p-'a');
           mm=now;
           now=f[now].next[idx];
           f[mm].cnt--;//前缀 依次减减 
           p++;
      }

      if(!f[mm].cnt)f[mm].next[idx]=0;//如果此单词为叶节点 将最后一个字符删除 
}

十六、LCA

1.离线 tarjan+并查集

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void tarjan(int u){
   int j,v;
   visit[u]=1;
   father[u]=u;
   for(j=head1[u];j!=-1;j=edge1[j].next){
      v=edge1[j].to;
      if(visit[v]) 
            LCA[edge1[j].num]=find(v);
   }

   for(j=head[u];j!=-1;j=edge[j].next){
      v=edge[j].to;
      if(!visit[v]) {
        dis[v]=dis[u]+edge[j].val;
        tarjan(v);
        father[v]=u;
      }
   }
}

2.倍增

C++
 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
int f[12000][32];//i节点的第2的j次方个祖先 
int dep[12000];//深度 
vector<int> c[12000];
int dfs()//遍历深度，记下父子关系 
int adjust(int &x,int high){//对深度的调整 
      for(int i=31;i>=0;--i) {//2的j次方 
           if(dep[f[x][i]]>=high) {
               x=f[x][i];
           }
      }
}

int equal(int x,int y)//相等时调整，先跳到儿子节点 
      for(int i=31;i>=0;--i) {
           if(f[x][i]!=f[y][i]) {
               x=f[x][i];y=f[y][i];
           }
      }
      return f[x][0];//现在在儿子节点 
}

int LCA(int x,int y){
      if(dep[x]>dep[y]) adjust(x,dep[y]);
      if(dep[x]<dep[y]) adjust(y,dep[x]);
 }//调深度 

      if(x==y) {return x;}//特判    
          return equal(x,y);
}


Int main()
{
      for(int i=1;i<=n-1;++i) {
           scanf("%d%d",&x,&y);
           c[x].push_back(y);
           f[y][0]=x;
      }

      int k=0;
      for(int i=1;i<=n;++i) {
           if(f[i][0]==0) {//找根 
               k=i;
               break;
             }
      }

      dep[k]=1;
      dfs(k);
      for(int j=1;(1<<(j))<=n;++j) {//倍增方式处理f数组 
           for(int i=1;i<=n;++i) 
               f[i][j]=f[f[i][j-1]][j-1];
      scanf("%d%d",&x1,&y1);
      printf("%d\n",LCA(x1,y1));
      for(int i=1;i<=n;++i) c[i].clear();
      return 0;
}

3.欧拉序列+ST 倍增

C++
 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
int dfs(int x)//在dfs中求解欧拉序列 
{
      ver[++tot]=x; //欧拉序列 
      r[tot]=dep[x]; //欧拉序列中的深度 
      first[x]=tot; //第一次在欧拉序列中出现的位置 
      vis[x]=1;
      for(int i=0;i<c[x].size();++i) {
           int vv=c[x][i];
           if(!vis[vv]) {
               dep[vv]=dep[x]+1;
               dfs(vv);
               ver[++tot]=x;
               r[tot]=dep[x];
           }
      }
}

for(int i=1;i<=tot;++i) f[i][0]=i;//ST初始化 
for(int j=1;(1<<j)<=tot;++j) {   //求解ST表，其中深度最小的
     for(int i=1;i+(1<<j)-1<=tot;++i) {
       int tmp1=f[i][j-1]; 
       int tmp2=f[i+(1<<(j-1))][j-1];
       if(r[tmp1]>r[tmp2]) f[i][j]=tmp2;//记标号比较深度 
       else f[i][j]=tmp1;
     }
}

十七、tarjan

C++
 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
/*有向图的tarjan算法*/
void tarjan(int x) {
      dfn[x]=low[x]=++ti;
      stack[++top]=x;     
      bo[x]=1;         
      int y;
      for(int i=1;i<=n;i++)
           if(map[x][i]) {
               if(!dfn[i]) {  
                    tarjan(i);
                    low[x]=min(low[x],low[i]);
               }
               else if(bo[i])  //在栈中 
               low[x]=min(low[x],dfn[i]);       
           }

      if(low[x]==dfn[x]) {   
           ++num;
           do {
               y=stack[top--];
               bo[y]=0; 
               bel[y]=num;   
           } while(x!=y);
      }

}

/*tarjan求桥与割点*/

struct node{
    int sum;         //相连边的条数
    int a[1001],num[1001];  //边的终点，边的编号
} no[1001]; 

void Tarjan(int i,int Father) { 
  father[i]=Father;   //记录每一个点的父亲 
  dfn[i]=low[i]=tim++; 
  for(int j=0;j<no[i].sum;++j) { 
     int k=no[i].a[j]; 
     if(dfn[k]==-1){
       line[k]=no[i].num[j];  //记录每一个点所连的树边，避免重边
       Tarjan(k,i); 
       low[i]=min(low[i],low[k]);
     }
     else if(line[i]!=no[i].num[j]) //一条边只走一次
       low[i]=min(low[i],low[k]);
  } 
} 

/*桥和割点计数*/
void count() { 
  int rootson=0; 
  Tarjan(1,0); 
  for(int i=2;i<=n;++i) 
  { 
     int v=father[i];
     if(v==1) rootson++;//统计根节点子树的个数，根节点的子树个数>=2,就是割点
     else{
       if(low[i]>=dfn[v])/*割点的条件*/
          is_cut[v]=true;
     }
  }
  if(rootson>1)  is_cut[1]=true;
  for(int i=1;i<=n;++i)
  if(is_cut[i])  printf("%d\n",i);
  for(int i=1;i<=n;++i) {
     int v=father[i];
     if(v>0&&low[i]>dfn[v])/*桥的条件*/ 
     printf("%d,%d\n",v,i); 
  }
}

十八、树的遍历

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void front(int x){  //先序 x为根
      printf("%d ",x);
      if(lch[x])front(lch[x]);
      if(rch[x])front(rch[x]);    
}

void middle(int x){  //中序  x为根
      if(lch[x])middle(lch[x]);
      printf("%d ",x);
      if(rch[x])middle(rch[x]);
}

void queen(int x){  //后序  x为根
      if(lch[x])queen(lch[x]);
      if(rch[x])queen(rch[x]);
      printf("%d ",x);
}

1.先序+中序 -> 后序

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int find(const string &s,char c){  //查找根在中序遍历中第一次出现的位置 
      for(int i=0;i<s.size();i++) {
           if(s[i]==c) return i;
      }
      return -1;
}

void premid(const string &pre,const string &mid){ //pre,mid string类已知先中求后 
   if(pre.size()==0) return ;//没有节点了，返回 
   if(pre.size()==1) {    //无子树，输出根，返回 
       printf("%c",pre[0]);
       return;
   }
   int k=find(mid,pre[0]);  //在中序遍历中找到根第一次出现的位置，即分左右子树 
   string midtmp=mid.substr(0,k);//左子树的先序遍历 
   string pretmp=pre.substr(1,k); //左子树的中序遍历
   premid(pretmp,midtmp);  //递归左子树
   pretmp=pre.substr(k+1,pre.size()-k-1);//右子树的先序遍历
   midtmp=mid.substr(k+1,mid.size()-k-1);//右子树的中序遍历
   premid(pretmp,midtmp);  //递归右子树    
   printf("%c",pre[0]);   //输出根
}

2.后序+中序 -> 先序

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
bool BackMid(const string &back, const string &mid) //注释及find函数详见 上
{ 
  if (back.size() == 0) 
     return false; 
  if (back.size() == 1) 
  { 
     cout<<back; 
     return true; 
  } 

  //根节点是最后一个元素 
  int k = find(mid, back[back.size() - 1]);  //变成前序遍历要先输出节点的值 
  cout << back[back.size() - 1]; 
  string backTmp = back.substr(0, k); 
  string midTmp = mid.substr(0, k); 
  BackMid(backTmp, midTmp); 
  backTmp = back.substr(k, back.size() - k - 1); 
  midTmp = mid.substr(k + 1, mid.size() - k - 1); 
  BackMid(backTmp, midTmp); 
}
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用