trie树

#include<iostream>
#include<algorithm>

using namespace std;

const int N=3000010;

int son[N][2],idx;
int a[N];
int n;

void insert(int x)//建立trie树
{
  int p=0;
  for(int i=30;~i;i--) //~i  ==  i>=0
  {
    int &s=son[p][x>>i & 1]; //引用s ，取数x的第i位建立trie树
    if(!s) s=++idx ; //当前i位没有遍历过，则给当前位置赋值
    p=s;//走到下一位
  }
}

int query(int x)
{
  int p=0,res=0;
  for(int i =30;~i;i--)
  {
    int s=x>>i  & 1;
    if(son[p][!s]) //与当前i位 可以异或 且答案位1 的存在
    {
      res+=1 << i;
      p=son[p][!s];
    }
    else p=son[p][s];
  }
  return res;
}
int main(){
  cin>>n;
  for(int i =0;i<n;i++) 
  {
    cin>>a[i];
    insert(a[i]);
  }

  int res=0;
  for(int i=0;i<n;i++)  res=max(res,query(a[i]) );

  cout<<res<<endl;
  return 0;
}

莫比乌斯函数（容次原理的 系数）

int primes[N], cnt;
bool st[N];
int mobius[N], sum[N];

// 线性筛法，求莫比乌斯函数
void init(int n)
{
    mobius[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            mobius[i] = -1;
        }
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                mobius[t] = 0;
                break;
            }
            mobius[t] = mobius[i] * -1;
        }
    }

    for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + mobius[i];
}

快速幂中的矩阵乘法

 while (k)
    {
        if (k & 1) mul(f1, f1, a);  // f1 = f1 * a
        mul(a, a, a);  // a = a * a
        k >>= 1;
    }

void mul(int c[][N], int a[][N], int b[][N])  // c = a * b
{
     int t[N][N];
    memset(t, 0, sizeof t); //sizeof c  是返回指针的长度

    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                t[i][j] = (t[i][j] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, t, sizeof t);
}

快速幂

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

并查集

int p[N];//存当前节点的祖宗节点
int find(int x){//路径压缩+返回祖宗节点
    if(p[x]!= x) p[x]=find(p[x]);
    return p[x];
}

int find(int x){//路径压缩+返回祖宗节点
    if (p[x] == x || p[p[x]] == p[x]) return p[x];
    int r = find(p[x]);
// d[x] += d[p[x]];若并查集中需要加值 在当前数下+上路径上 值
    p[x] = r;
    return r;
}

int find(int x){//路径压缩+返回祖宗节点
    if(p[x]!= x && p[x]!=p[p[x]]) p[x]=find(p[x]);
    return p[x];
}

p[find(a)]=find(b);

扩展欧几里得

int gcd(int a,int b,int &x,int &y){
  if(!b){
    x=1,y=0;
    return a;
  }
  int d=gcd(b,a%b,y,x);
  y-=a/b*x;   //等价x=y′,y=x′−⌊a/b⌋∗y′
  return d;
}

//若以求出来任意一组解 x0,y0;
x=x0+k(b/d)
y=y0-k(a/d)
//k属于正整数

求x的最小正整数解= x0 %(b/d)

bfs可以找到最短的步数
dfs 不可以

i<< j+1 //位运算的优先级 小于 + -

闰年

  year % 4 == 0 && year % 100 || year % 400 == 0

//取别名，用到的a就是f[a][b];
int &a = f[a][b];

//下标 从0开始  第n个数开始 行，列(n/w,n%w)  从1开始则不行

//二维数组 下标
// 一个n*m的二维数组a中，第i个数的下标（第一个数是从第0行0列开始）== a[i/m][i%m];
// （0,0) 开头 下标(i/m,i%m)  (1,1) 开头下标 (i/m+1,i%m+1);


//裴蜀定理   输入的 a,b 必须互质， 这样我们才可以找到 一个最大的不可以被凑出来的数(例题1205)
//公式  
ans = (a-1)*(b-1)-1 == a*b-a-b;

上取整

(a+b-1)/b

#include<iomanip>       //求精度
cout<<fixed << setprecision(6)<<x<<endl;

//memset 和memcpy 头文件在cstring中
memset(a,0x3f3,sizeof a);

哈希表unordered_map，unordered_map是C++中的哈希表，可以在任意类型与类型之间做映射。

unordered_map<char,int> pr{{'*',2},{'/',2},{'+',1},{'-',1}};  定义

unordered_map<int,int> pr

pr[x]=i //x是键值，i对应哈希值
pr.count(t)  //返回的是被查找元素的个数。如果有，返回1；否则，返回0


unordered_set::insert
unordered_set::find
unordered_set::erase

unordered_set(无序集合) 拥有快速查找和删除

//判断是否为空
c1.empty();

//获取元素个数 size()
c1.size();

//获取最大存储量 max_size()
c1.max_size();

//value出现的次数 count() 返回匹配给定主键的元素的个数
    c1.count(1);
    //插入函数 insert()
    c1.insert(1);
  //删除 erase()
    c1.erase(1);//1.迭代器 value 区域

    //清空 clear()
    c1.clear();

//字符操作
#include<cstring>
char a[N];
 n =strlen(a);

//pair类型的vector，排序;

        vector<vector<int>> f(n + 1, vector<int>(m + 1)); //初始化为n+1行和m+1列都为0

typedef  pair<int,int> PII
vector<PII> a;
sort(a.begin(),a.end);

vector<int> aa;                           stack<int> a;
aa ={a,b,c};                                  
aa.push_back(a);                          a.push(x);
aa.size()

//队列
#include<queue>
queue<int> q;
q.front() //取队头
q.pop() //弹出队头
q.push()  //入队
string a 的+-只能拼接
char  a 的+-只能asscill码++--

//前缀和 
s[i][j] =s[i-1][j]+s[i][j-1]+w[i][j]-s[i-1][j-1]

//最大公约数写法  
return b? gcd(b,a%b): a;

//线性筛

int primes[N], cnt;
int minp[N];//存当前数  的最小的一个质因子
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            minp[i] = i;
            primes[cnt ++ ] = i;
        }
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            minp[t] = primes[j];
            if (i % primes[j] == 0) break;
        }
    }
}


#include<queue>

priority_queue<int,vector<int>,greater<int> >heap //小跟堆
heap.size()
heap.top()
heap.push()
heap.pop()

//a到b的个数
//a-b+1;
for(int i=0;i<a-b+1;i++)   ||  for(int i =1;i<=a-b+1;i++)

//a到b的边数  (a-b n个点)一共n-1条边  
//a-b
for(int i =0;i<a-b;i++)   ||  for(int i =1;i<=a-b;i++)

string 操作注意

//string操作
#include<string>
string a;//初始化为空串
cout<<stoi(a)<<endl;  //表示将字符串a换成整数输出
reverse(s.begin(),s.end());//string翻转(字符串的操作)

//若是翻转 数组
#include<algorithm>
int a[10];
reverse(a,a+10);

//二进制
lowbit(x)  返回x的二进制的最后的一位1
{
    return x&-x;  //-x在c++里面是用补码存储的
}

//设定最小数    并且 0x3f3f3f3f是最大的 可以相加 的int整数 
#include<limits.h>
int maxa = INT_MAX //最小整数     int mina = INT_MIN  //最小整数（32位的）

a=(a>b? a:b);//三目运算符

//重载
struct Sum
{
    int s, c, d;

    bool operator< (const Sum &t)const
    {
      if( s!=t.s) return s<t.s;
      if(c!= t.c) return c<t.c;
      return d<t.d;
    }
}sum[N];
 sort(sum, sum + m);


//邻接表存储 树或者图

const int N=1e5+10;//无向图 需要存两倍的边
int h[N],e[N*2],ne[2*N];
int w[N*2];
memset(h,-1,sizeof h);//头节点初始化为-1
void add(int a,int b,int c){  //c是代表的值（eg：距离）
    w[idx] =c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}