#include<queue>
#include<iostream>
using namespace std;
typedef pair<int, int> PII;
const int N=110;
int n, m, g[N][N], d[N][N];//g地图 d表示该点到(0, 0)的距离，d[i][j]== -1 表示该点是第一次走
queue<PII> q;

int bfs(){
    d[0][0]=0;//进来先走了(0,0)点
    q.push({0, 0});
    int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
    while(!q.empty()){//只要队列中还有待处理的点
        PII t = q.front();
        q.pop();
        for(int i=0; i<4; i++){ //上下左右四个方向循环检测，满足条件的点加入队列
            int x=t.first + dx[i], y=t.second + dy[i];//临时xy存储该方向上下一个点的坐标
            if(x>=0 && x<n && y>=0 && y<m && g[x][y] ==0 && d[x][y]==-1){//该点可以到达并且是第一次到达
                d[x][y]=d[t.first][t.second]+1;//最重要的一步，更新每个点到原点的距离
                q.push({x, y});//将这个点加入队列 稍后处理
            }
        }
    }
    return d[n-1][m-1]; //返回迷宫出口距离远点的距离
}

int main(){
    cin >>n >>m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >>g[i][j];
            d[i][j]=-1;//将每个点到远点的距离初始化为-1，表示尚未走过
        }
    }

    cout <<bfs();
    return 0;
}

#include<iostream>
using namespace std;
const int N=20;//y由于对角线问题，开二倍空间
char res[N][N];

//以二维数组坐上为远点，y轴向右，x轴向下，主对角线为y=x+b，令b为每次插入的行坐标，则用b=y-x表示，
//由于y-x取值范围为-n~n， 将其加上n避免取负值，b=y-x+n，即将x行y列放入皇后时，将dg[y-x+n]置为true;
//同理，副对角线对应将udg[x+y]置为true;
bool col[N], dg[N], udg[N];//列状态(判断当前列是否已经存在皇后)，对角线状态，副对角线状态
int n;
void dfs(int u){//此处u表示二维数组中遍历到的行数
    if(n==u){
        for(int i=0; i<n; i++) puts(res[i]); //char[][]的每一行作为字符串输出
        puts("");
        return;
    }
    for(int i=0; i<n; i++){//当前行的每一列 此处i表示列数，u表示行数
        if(!col[i] && !dg[i-u+n] && !udg[i+u]){//如果当前位置同对角线、同副对角线、同列上都没有放皇后
            res[u][i] = 'Q';
            col[i] = dg[i-u+n] = udg[i+u] = true;
            dfs(u+1); //安排下一行
            //恢复现场
            res[u][i] = '.'; 
            col[i] = dg[i-u+n] = udg[i+u] = false;
        }
    }
}
int main(){
    cin >>n;
    for(int i=0 ;i<n; i++){
        for(int j=0; j<n; j++){
            res[i][j]='.';
        }
    }
    dfs(0);
    return 0;
}

#include<iostream>
using namespace std;
const int N=10;
int n, path[N]; //path用来存当前走过的路径，即要输出的排列
bool st[N]; //存每个数是否可用 s[i]==false表示尚未被使用
void dfs(int u){
    if(n==u){ //数组下标从0开始，当最后一个节点(n-1的节点)再向下搜索时，n==u，返回
        for(int i=0; i<n; i++) printf("%d ", path[i]);  //此处的i表示path[]的下标，从path[0]开始输出
        printf("\n");
        return;
    }
    for(int i=1; i<=n; i++){ //此处循环条件表示需要填充的数字从1开始到n
        if(st[i]==false){
            path[u]=i; //i表示当前要向path里存储的数字，u表示当前path中要存数字的位置
            st[i]=true;//数字i已经被使用
            dfs(u+1);//填充下一位置
            st[i]=false;//递归返回后，需要释放当前层占用的数字，即恢复st[i]
        }
    }
}
int main(){
    cin >>n;
    dfs(0); //此处传入0，表示从path[0]开始填充数字
    return 0;
}

/*
利用并查集的查询过程递归维护每个节点到根节点的距离d[]，由于题中有三种动物互相捕食，所以节点距离逢3循环，
如果(d[x]-d[y])%3==0，表示x y为同类，(d[x]-d[y]-1)%3==0，表示x吃y
*/

#include<iostream>
using namespace std;
const int N=50010;
int d[N], p[N];//d[x]表示x到其父节点的距离，p[x]表示x的父节点 题目中的元素为1~N的整数，每个整数就是一个节点 用p[x]==x表示该节点是根节点

int find(int x){ //寻找x的根节点，过程中路径压缩并维护该节点到根节点的距离d[x]
    if(p[x]!=x){ //如果x不是根节点
        int t=find(p[x]);//将父节点的父节点保存下来，稍后更新成x的父节点，递归进行，即路径压缩
        //x的父节点路径压缩后变为根节点，为了维护x到新的父节点(即根节点)的距离，
        //将x到父节点(路径压缩后为根节点)的距离更新加上x父节点到其父节点的距离，
        //在已经返回的下一层递归过程中，x父节点的父节点已经被更新为根节点，所以x父节点到其父节点的距离已经被更新为到根节点的距离
        d[x] += d[p[x]];
        p[x]=t;//将x的父节点更新为x父节点的父节点，由于路径压缩，此时的t即为根节点
        //
    }
    return p[x];
}

int main(){
    int n, k, res=0;
    scanf("%d%d", &n, &k);
    //将每个节点的父节点初始化为自己 未加入并查集的元素独立成为一个集合 根节点是自己
    for(int i=1; i<=n; i++) p[i]=i; 
    while(k--){
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if(x>n||y>n){
            res++;
        }else{
            int px=find(x), py=find(y);//寻找x,y的根节点，并维护d[x],d[y]
            if(t==1){ //称xy同类
                if(px==py && (d[x]-d[y])%3!=0) res++; //如果在同一集合，但是不是同类
                else if(px!=py){//如果不在同集合，此时为真话，需要记录关系
                    p[px]=py;
                    d[px] = d[y]-d[x];
                }
            }else{//称x吃y
                //判断d[x],d[y] 余三后做差是否为1， 不能用(d[x]-d[y])%3!=1表示，因为在c++中 余三后结果可能为-2
                if(px==py && (d[x]-d[y]-1)%3!=0) res++; 
                else if(px!=py){ //如果不在集合，此时为真话
                    p[px]=py;
                    d[px] = d[y]-d[x] + 1;
                }
            }
        }
    }
    cout <<res;
    return 0;
}

#include<iostream>
using namespace std;
typedef unsigned long long ULL;
//P进制，模Q，经验值P=131或13331，Q=2^64   
//操作中，用unsigned long long 存储每个字串的哈希值，ULL为64位，超出会溢出，模拟模2^64
const int N=100010, P=131;
ULL h[N]; //h[]存从头开始的每个字串对应的哈希值
ULL p[N];  //p[i]存储p的i次方的值 加快运算速度
char str[N];//存字符串

ULL get_hash(int l, int r){
    ULL res = h[r] - h[l-1] * p[r-l+1]; //p^(R-L+1)
    return res;
}

int main(){
    int n, m;
    scanf("%d%d%s", &n, &m, str+1);//下标从1开始避免冲突
    p[0]=1;
    for(int i=1; i<=n; i++){
        p[i]=p[i-1] * P; //初始化p[]  *后面的是大写P，进制
        h[i]=h[i-1] * P + str[i]; //初始化h[]，由于从左向右存，每i位的值等于i-1位乘以进制后加上str[i]对应字符的ASCII值
    }
    while(m--){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get_hash(l1, r1)==get_hash(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

开放寻址法

#include<cstring>
#include<iostream>
using namespace std;
const int N=200003, null=0x3f3f3f3f; //用null表示这个位置没有存数据，0x3f3f3f3f > 10e9，题目给的数据范围取不到这个数，可以作为标志
int h[N];

//find(x); 返回x在哈希表中的位置，如果x不在哈希表中，返回x应该存储的位置，即取模位置及其后的第一个可用空位置
int find(int x){
    int k = ((x%N)+N)%N; //哈希函数 (x&N)先将数据范围缩小到-N~N，在+N使其一定为整数，再%N使其成为小于N的正数
    //如果哈希出的结果对应位置 即不为空，又不是x，说明此位置被其他数据占用，向后寻找空位置或x所在位置
    while(h[k]!=null && h[k]!=x){ 
        k++;
        if(k==N) k=0; //如果遍历到了数组末尾，从头开始继续
    }
    return k;
}
int main(){
    memset(h, 0x3f, sizeof(h)); //将h[]每一个位置都初始化为null
    int n;
    cin >>n;
    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op=='I') h[find(x)]=x;
        else{
            if(h[find(x)]==null) puts("No"); //如果返回的位置的数为null，即没有存数，输出No
            else puts("Yes"); //如果这一位上有数，则为要找的数
        }
    }
}

拉链法

#include<cstring>
#include<iostream>
using namespace std;
const int N=200003; 
//在拉链法中，h[]的每个位置存储一个链表，即每个位置都是一个头节点，用-1表示此节点是尾节点
//e[x]表示链表中节点x的值，ne[x]表示链表中x节点的下一个节点的位置 idx分配器 同模拟链表
int h[N], e[N], ne[N], idx; 

void insert(int x){ 
    int k=((x%N)+N)%N; //哈希得到x应该连接到的链表的头节点位置
    e[idx]=x; //插入该链表 头插  同模拟链表
    ne[idx]=h[k];
    h[k]=idx++;
}
bool find(int x){
    int k=((x%N)+N)%N;
    for(int i=h[k]; i!=-1; i=ne[i]){ //h[k]为头节点，h[k]存储该链表下一个节点的位置
        if (e[i]==x) return true;
    }
    return false;
}
int main(){
    memset(h, -1, sizeof(h)); //拉链法中将h[]每一个位置都初始化为-1，即初始状态下哈希表中每个位置的链表都为空
    int n;
    cin >>n;
    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op=='I') insert(x);//插入x
        else{
            if(find(x)) puts("Yes"); //如果找到
            else puts("No");  //否则
        }
    }
}

#include<iostream>
using namespace std;
const int N=100010, M=31*N;
int trie[M][2], idx;

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

int query(int x){
    int p=0, res=0;
    for(int i=30; i>=0; i--){
        int u = x >> i & 1;
        if(trie[p][!u]){
            p=trie[p][!u];
            res = res * 2 + !u;
        }else{
            p=trie[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}

int main(){
    int n, res=0;
    cin >>n;
    for(int i=0; i<n; i++){
        int x;
        scanf("%d", &x);
        insert(x);
        res = max(res, query(x) ^ x);
    }
    printf("%d", res);
}

纯数组模拟

看算法基础课习题课时没有看到这道题，自己做了一下，由于对树和stl容器之类不太熟悉，用了数组模拟，期间遇到问题时翻看题解也没有看到数组模拟的方法，于是写一个题解，分享一下菜鸟的思路

#include<iostream>
using namespace std;
const int N=100010;
char cal[N];
int num[N], num_top=-1, op[N], op_top=-1, cate[N];
//num存储数字，op存储第一次遍历到的操作符
//cate表示种类，1表示这一位存的是操作符的ascii码，0表示这一位是数字

int is_Prior(int a, int b){//a优先于b返回1，否则返回0
    if(a=='*'||a=='/'){
        if(b=='+'||b=='-'||b=='(') return 1;
        else return 0;
    }else if(a!='('&& b=='(') return 1;
    else return 0;
}

int calcu(int a, int b, int op){
    if(op=='*') return a*b;
    if(op=='/') return a/b;
    if(op=='+') return a+b;
    if(op=='-') return a-b;
}

int main(){
    scanf("%s", cal);
    for(int i=0; cal[i]!=0; i++){
        int number=0;
        if(cal[i]>='0'&&cal[i]<='9'){
            while(cal[i]>='0'&&cal[i]<='9') {
                number=number*10 +(cal[i]-'0');
                i++;
            }
            i--;
            num[++num_top]=number; //数字直接放进数字栈
            cate[num_top]=0;
        }else if(cal[i]==')'){ //如果当前为右括号')'
            while(op[op_top]!='(') {
                num[++num_top]=op[op_top--]; //遇到右括号就将符号栈中左括号之前的操作符依次压入数字栈
                cate[num_top]=1;
            }
            op_top--;//舍弃左括号
        }
        else{//如果为除右括号以外的其他符号
            char c=cal[i];
            if(op_top<0 || c=='(') op[++op_top] = c; //符号栈为空或者当前为左括号 直接进栈
            else if( is_Prior(c, op[op_top]) ){//如果栈顶符号优先级低
                op[++op_top] = c;//此符号进栈
            }else{ //如果栈顶优先级不低
                while(op_top>=0 && !is_Prior(c, op[op_top])) {
                    num[++num_top]=op[op_top--];
                    cate[num_top]=1;
                }
                op[++op_top] = c;
            }
        }
    }
    while(op_top>=0) {
        num[++num_top]=op[op_top--];
        cate[num_top]=1;
    }
    //此时op栈为空，数字和操作符以后缀表达式的顺序存储在num[]数组中

    //******************上面求后缀表达式，下面根据后缀表达式计算***********************

    //回收利用op数组，将他作为临时数组存储数字
    for(int i=0; i<=num_top; i++){ //遍历后缀表达式(num[]数组)，数字为压入临时栈(op[])中
        if(cate[i]==0) { //数字位
            op[++op_top]=num[i];
        }
        else{ //遇到操作符弹出两个数字计算结果并再次压入临时数组中
            int b=op[op_top--], a=op[op_top--];
            op[++op_top]=calcu(a, b, num[i]);
        }
    }
    //此时op[]中只有一个数，num栈为空
    printf("%d\n", op[op_top]); //输出最终结果

    return 0;
}

纯数组模拟，先转成后缀表达式再计算

#include<iostream>
using namespace std;
const int N=100010;
char cal[N];
int num[N], num_top=-1, op[N], op_top=-1, cate[N];
//num存储数字，op存储第一次遍历到的操作符
//cate表示种类，1表示这一位存的是操作符的ascii码，0表示这一位是数字

int is_Prior(int a, int b){//a优先于b返回1，否则返回0
    if(a=='*'||a=='/'){
        if(b=='+'||b=='-'||b=='(') return 1;
        else return 0;
    }else if(a!='('&& b=='(') return 1;
    else return 0;
}

int calcu(int a, int b, int op){
    if(op=='*') return a*b;
    if(op=='/') return a/b;
    if(op=='+') return a+b;
    if(op=='-') return a-b;
}

int main(){
    scanf("%s", cal);
    for(int i=0; cal[i]!=0; i++){
        int number=0;
        if(cal[i]>='0'&&cal[i]<='9'){
            while(cal[i]>='0'&&cal[i]<='9') {
                number=number*10 +(cal[i]-'0');
                i++;
            }
            i--;
            num[++num_top]=number; //数字直接放进数字栈
            cate[num_top]=0;
        }else if(cal[i]==')'){ //如果当前为右括号')'
            while(op[op_top]!='(') {
                num[++num_top]=op[op_top--]; //遇到右括号就将符号栈中左括号之前的操作符依次压入数字栈
                cate[num_top]=1;
            }
            op_top--;//舍弃左括号
        }
        else{//如果为除右括号以外的其他符号
            char c=cal[i];
            if(op_top<0 || c=='(') op[++op_top] = c; //符号栈为空或者当前为左括号 直接进栈
            else if( is_Prior(c, op[op_top]) ){//如果栈顶符号优先级低
                op[++op_top] = c;//此符号进栈
            }else{ //如果栈顶优先级不低
                while(op_top>=0 && !is_Prior(c, op[op_top])) {
                    num[++num_top]=op[op_top--];
                    cate[num_top]=1;
                }
                op[++op_top] = c;
            }
        }
    }
    while(op_top>=0) {
        num[++num_top]=op[op_top--];
        cate[num_top]=1;
    }
    //此时op栈为空，数字和操作符以后缀表达式的顺序存储在num[]数组中

    //******************上面求后缀表达式，下面根据后缀表达式计算***********************

    //回收利用op数组，将他作为临时数组存储数字
    for(int i=0; i<=num_top; i++){ //遍历后缀表达式(num[]数组)，数字为压入临时栈(op[])中
        if(cate[i]==0) { //数字位
            op[++op_top]=num[i];
        }
        else{ //遇到操作符弹出两个数字计算结果并再次压入临时数组中
            int b=op[op_top--], a=op[op_top--];
            op[++op_top]=calcu(a, b, num[i]);
        }
    }
    //此时op[]中只有一个数，num栈为空
    printf("%d\n", op[op_top]); //输出最终结果

    return 0;
}

#include<iostream>
using namespace std;
const int N=100010;
int h[N], hp[N], ph[N] ,cnt; //hp[]表示堆中(h[])每个位置的元素是第几个插入的，ph[]表示第几个插入的元素在h[]中的位置, cnt表示当前堆元素个数

void heap_swap(int a, int b){
    swap(h[a], h[b]);
    swap(ph[hp[a]], ph[hp[b]]); //先根据堆中位置找到插入次序，先交换ph 再交换hp，否则交换Hp后无法找到正确的Ph
    swap(hp[a], hp[b]);
}

void down(int x){
    int t=x;
    if(x*2<=cnt && h[x*2]<h[t]) t=2*x; //注意t和x的位置不能随意调换
    if(x*2+1<=cnt && h[x*2+1]<h[t]) t=x*2+1;
    if(t!=x) {
        heap_swap(x, t);
        down(t);
    }
}

void up(int x){
    int t=x;
    if(x/2>0 && h[x/2]>h[x]) t=x/2;
    if(t!=x){
        heap_swap(x, t);
        up(t);
    }
}

int main(){
    int n, m=0; //m表示当前插入次数
    cin >>n;
    while(n--){
        char op[5];
        scanf("%s", op);
        if(op[0]=='I'){
            int x;
            scanf("%d", &x);
            cnt++, m++;
            h[cnt]=x;
            ph[m]=cnt; //第m个插入的数在堆中的下标为cnt
            hp[cnt]=m; //堆中下标为cnt的数是第m个插入的
            up(cnt);
        }else if(op[0]=='P'){ 
            printf("%d\n", h[1]);//打印堆顶
        }else if(op[0]=='C'){ 
            int k, x; //将第k个插入的数变成x
            scanf("%d%d", &k, &x);
            k = ph[k]; //将k从次序映射为在堆中的下标
            h[k]=x;
            down(k), up(k);
        }else{ //"D"
            if(op[1]=='M'){ //"DM" 删除最小值
                heap_swap(1, cnt);
                cnt--;
                down(1);
            }else{ //"D" 删除第k个插入的数
                int k;
                scanf("%d", &k);
                k=ph[k];//映射为下标
                heap_swap(k, cnt);
                cnt--;
                down(k), up(k);
            }
        }
    }
    return 0;
}