01Tire树

利用Tire树将一个数的二进制表示存储进Tire树中，边存储边求最大异或值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 2e5 + 10, MOD = 1e9 + 7, T = 20;

int n;

int a[N], idx;

struct Node{
    int val;
    int son[2];
}t[N * 32]; //最多有32位 

void insert(int x)
{
    int o = 0;
    for(int i = 30; i >= 0; -- i)
    {
        //取出x的第i位 
        int y = x >> i & 1;

        int &u = t[o].son[y]; 
        //如果u点（对应边的儿子）不存在，就新开一个点 
        if(!u) u = ++ idx;

        o = u;
    }
} 

int getMax(int x)
{
    int o = 0, res = 0;

    for(int i = 30; i >= 0; -- i)
    {
        //去除x的第i位
        int y = x >> i & 1;

        int u = t[o].son[y], v = t[o].son[!y];
        // 尽量往当前位的反方向走才能保证异或值最大

        if(v) 
        {
            o = v;
            res |= (1 << i);
        }
        else o = u; 
    }

    return res;
}
void solve()
{
   cin >> n;


   for(int i = 2; i <= n; i ++)
   {
       cin >> a[i]; 
   }    

    int ans = a[1] ^ a[2];

    //一边插入一边求最大异或值 
    for(int i = 2; i <= n; i ++)
    {
        ans = max(ans, getMax(a[i]));
        insert(a[i]);
    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
     int T = 1;
     //cin >> T;
     while(T --)
     {
        solve();    
     }   
    return 0; 
} 

ACwing模板

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 31 * N;

int a[N];
int s[M][2];

int n, idx;

void insert(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if(!s[p][u]) s[p][u] = ++ idx;

        p = s[p][u];
    }
}

int getans(int x)
{
    int res = 0, p = 0;

    for(int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if(s[p][!u]) 
        {
            p = s[p][!u];
            res = res * 2 + !u;
        }
        else
        {
            p = s[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}
int main()
{
   ios::sync_with_stdio(false);

   cin >> n;

   for(int i = 1; i <= n; i ++) cin >> a[i];
   int ans = 0;
   for(int i = 1; i <= n; i ++)
   {
      insert(a[i]);

      ans = max(ans, a[i] ^ getans(a[i]));  
   }   

   cout << ans;
   return 0;    
} 

KMP字符串匹配

题目链接

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e6 + 10, inf = 2e18;

char s[N], t[N];

int nex[N];


void solve()
{
   cin >> s + 1 >> t + 1;

   int n = strlen(s + 1), m = strlen(t + 1);

   s[n + 1] = '#', t[m + 1] = '$';

   nex[1] = 0;

   for(int i = 2, j = 0; i <= m; i ++)
   {
      while(j && t[i] != t[j + 1]) j = nex[j];

      if(t[i] == t[j + 1]) j ++;

      nex[i] = j;
   }


   for(int i = 1, j = 0; i <= n; i ++)
   {
      while(j && s[i] != t[j + 1]) j = nex[j];

      if(s[i] == t[j + 1]) j ++;

      if(j == m)
      {
         cout << i - j + 1 << " ";  
      }

   }

   cout << endl;

   for(int i = 1; i <= m; i ++) cout << nex[i] << " ";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
     int T = 1;
    // cin >> T;
     while(T --)
     {
        solve();    
     }   
    return 0; 
} 

ACwing模板

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;

char p[N], s[N];

int ne[N];

int n, m;
int main()
{
   ios::sync_with_stdio(false);

   cin >> n >> p + 1 >> m >> s + 1;

   for(int i = 2, j = 0; i <= n; i ++)
   {
       while(j && p[i] != p[j + 1]) j = ne[j];

       if(p[i] == p[j + 1]) j ++;

       ne[i] = j;
   }

   for(int i = 1, j = 0; i <= m; i ++)
   {
       while(j && s[i] != p[j + 1]) j = ne[j];

       if(s[i] == p[j + 1]) j ++;

       if(j == n) 
       {
        cout << i - n << " "; 
       }
   }

   return 0;    
} 

带权并查集

题目
find函数的解释

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], d[N]; //p[]寻找祖宗节点，d[]求到祖宗节点的距离

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]); // u暂时存一下p[x]根节点，辅助变量
        d[x] += d[p[x]];    // 更新距离
        p[x] = t;
    }
    return p[x];
}



int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int res = 0;//记录错误数
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (x > n || y > n) res ++ ; // 当前的话中X或Y比N大，是假话
        else
        {
            int px = find(x), py = find(y); // 查找根节点
            if (t == 1) // 判断是否同类
            {
                if (px == py) {  // 若 x 与 y 在同一个集合中
                    if ((d[x] - d[y]) % 3) res ++ ; // 两数到根节点距离之差的模不为 0，说明不是同一类，是假话
                    // 其中 (d[x] - d[y]) % 3 不可写为 d[x] % 3 != d[y] % 3
                    // 因为 d[x], d[y] 可能为负数（一正一负），可改做 (d[x] % 3 + 3) % 3 != (d[y] % 3 + 3) % 3
                    // 负数 mod 正数为负数
                } else {    // 则 x 与 y 不在同一个集合中
                    p[px] = py;     // x 所在集合 合并到 y 所在集合
                    d[px] = d[y] - d[x];
                    // d[x] 的距离为什么不更新？
                    // 只是暂时不更新，在调用 find 时再更新
                }
            }
            else // X 是否吃 Y
            {
                if (px == py) {     // 若 x 与 y 在同一个集合中
                    // 若 X 吃 Y，则 d[x] 比 d[y] 大 1
                    if ((d[x] - d[y] - 1) % 3) res ++ ;  // 若距离之差 - 1 的模不为 0，说明吃不掉，是假话
                } else {    // 则 x 与 y 不在同一个集合中
                    p[px] = py;
                    // (d[x] - d[y] - 1) % 3 == 0
                    // d[x] + d[px] - 1 = d[y]  则：
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}

模拟堆

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 3 * N;

int n, m;

int h[N], sz;


void down(int u)
{
    int t = u;

    if(u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;

    if(u != t)
    {
        swap(h[u], h[t]);
        down(t);
    } 
}

void up(int u)
{
    while(u / 2 && h[u / 2] > h[u])
    {
        swap(h[u / 2], h[u]);
        u /= 2;
     } 
}
int main()
{
   ios::sync_with_stdio(false);
   cin >> n >> m;
   sz = n;
   for(int i = 1; i <= n; i ++) cin >> h[i];

   for(int i = n / 2; i >= 1; i --)
   {
       down(i);
   }

   while(m --)
   {
      cout << h[1] << " ";

      h[1] = h[sz];
      sz --;
      down(1);
   }
   return 0;    
}