考察DFS和二叉树的基本知识

非常老实的写法：

#include <iostream>
#include <string>
using namespace std;

typedef struct Node{
    char c;
    struct Node*l;
    struct Node*r;
}Node;
// 建树
void getTree(Node* &T){
    char x;
    scanf("%c",&x);
    if(x=='#'){
        T=NULL;
        return;
    }else{
        T=new Node();
        T->c=x;
        getTree(T->l);
        getTree(T->r);
    }
}
// 深度优先遍历
void DFS(Node* &T){
    if(T==NULL)return ;
    DFS(T->l);
    cout<<T->c<<' ';
    DFS(T->r);
}

int main(){
    Node*T;
    getTree(T);
    DFS(T);
    return 0;
}

边建树边遍历：

两点优化：

1. 因为我们在后续不会使用到这棵树，所以其实没必要用结构体指针把整棵树存下来
2. 鉴于先序建树的顺序是“根左右”，所以在建立完左子树的时候，根节点已有，此时在建立右子树之前可以直接输出根节点，这样其实相当于“左根右”的中序遍历

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int k;
string str;

void dfs()
{
    if (str[k] == '#')
    {
        k ++ ;
        return;
    }
    //用r来记录当前正在建立结点的值，省去结构体指针存储
    char r = str[k ++ ];  // 根节点
    dfs();  // 左子树
    //建立右子树之前先行输出根节点，达到中序遍历的效果
    cout << r << ' ';
    dfs();  // 右子树
}

int main()
{
    cin >> str;
    dfs();
    return 0;
}

#include <iostream>
#include <string.h>
using namespace std;
const int N=1e3+10;
char a[N][15];
int getDistance(char a[],char b[]){
    int la=strlen(a+1),lb=strlen(b+1);
    int f[15][15];
    for(int i=0;i<=la;i++)f[i][0]=i;
    for(int i=0;i<=lb;i++)f[0][i]=i;
    for(int i=1;i<=la;i++){
        for(int j=1;j<=lb;j++){
            if(a[i]==b[j])f[i][j]=f[i-1][j-1];
            else{
                f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
                f[i][j]=min(f[i][j],f[i-1][j-1]+1);
            }
        }
    }
    return f[la][lb];
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)scanf("%s",a[i]+1);
    while(m--){
        char b[15];
        int k,res=0;
        scanf("%s %d",b+1,&k);
        for(int i=0;i<n;i++){
            int len=getDistance(a[i],b);
            if(len<=k)res++;
        }
        cout<<res<<endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+10;
int f[N][N];
int main(){
    int n,m;
    cin>>n;
    char a[n+10];
    scanf("%s",a+1);
    cin>>m;
    char b[m+10];
    scanf("%s",b+1);
    for(int i=0;i<=n;i++)f[i][0]=i;
    for(int i=0;i<=m;i++)f[0][i]=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            //如果结尾字符相等则直接转移为f[i-1][j-1]
            if(a[i]==b[j])f[i][j]=f[i-1][j-1];
            else{
                //否则进行三种修改
                f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
                f[i][j]=min(f[i][j],f[i-1][j-1]+1);
            }
        }
    cout<<f[n][m]<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int main(){
    int n;
    cin>>n;
    int q[N];
    int len=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        int l=0,r=len;
        while(l<r){
            int mid=l+r+1>>1;
            if(q[mid]<x)l=mid;
            else r=mid-1;
        }
        len=max(len,r+1);
        q[r+1]=x;
    }
    cout<<len;
    return 0;
}

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N=110;
int f[N];
int sg(int x){
    if(f[x]!=-1)return f[x];
    unordered_set<int> s;
    for(int i=0;i<x;i++)
        for(int j=0;j<=i;j++){
            //注意这里传入的是i和j不是x-i和x-j
            s.insert(sg(i)^sg(j));
        }
    int i=0;
    while(true){
        if(!s.count(i))return f[x]=i;
        i++;
    }
}


int main(){
    int n;
    cin>>n;
    memset(f,-1,sizeof f);
    int res=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        res^=sg(x);
    }
    if(res)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

#include <iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int res=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(i%2)res^=x;
    }
    if(res)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

//求exgcd传入的是a2，则最后更新a1是不用abs因为d是正的
#include <iostream>
typedef long long LL;
using namespace std;
const int N=30;
int a[N];
int m[N];

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        y=0,x=1;
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>m[i];
    }
    LL m1,a1;
    a1=a[0],m1=m[0];
    bool flag=true;
    for(int i=1;i<n;i++){
        LL a2,m2;
        a2=a[i],m2=m[i];
        //用exgcd求出一组合法解
        LL k1,k2;
        LL d=exgcd(a1,a2,k1,k2);
        if((m2-m1)%d){
            flag=false;
            break;
        }
        k1*=(m2-m1)/d;
        //把这个合法解变最小
        LL t=a2/d;
        k1=(k1%t+t)%t;
        //求出当前两式的通解
        m1=k1*a1+m1;
        a1=a1/d*a2;
    }
    if(!flag)cout<<-1;
    else{
        LL res=(m1%a1+a1)%a1;
        cout<<res;
    }
    return 0;
}

//求exgcd的时候传入的是-a2，则最后更新a1的时候需要abs，因为d是负的，而我们要求a1必须是正数（不然最后求x的时候会出现负数）
#include <iostream>
typedef long long LL;
using namespace std;
const int N=30;
int a[N];
int m[N];

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        y=0,x=1;
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>m[i];
    }
    LL m1,a1;
    a1=a[0],m1=m[0];
    bool flag=true;
    for(int i=1;i<n;i++){
        LL a2,m2;
        a2=a[i],m2=m[i];
        //用exgcd求出一组合法解
        LL k1,k2;
        LL d=exgcd(a1,-a2,k1,k2);
        if((m2-m1)%d){
            flag=false;
            break;
        }
        k1*=(m2-m1)/d;
        //把这个合法解变最小
        LL t=a2/d;
        k1=(k1%t+t)%t;
        //求出当前两式的通解
        m1=k1*a1+m1;
        a1=abs(a1/d*a2);
    }
    if(!flag)cout<<-1;
    else{
        LL res=(m1%a1+a1)%a1;
        cout<<res;
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N=110;
int a[N][N];
int n;
int gaussplus(){
    int c,r;
    for(c=0,r=0;c<n;c++){
        int t=-1;
        for(int i=r;i<n;i++){
            if(a[i][c]==1){
                t=i;
                break;
            }
        }
        if(t==-1)continue;
        for(int i=c;i<n+1;i++)swap(a[r][i],a[t][i]);
        for(int i=r+1;i<n;i++){
            if(a[i][c]==1){
                for(int j=c;j<n+1;j++)a[i][j]^=a[r][j];
            }
        }
        r++;
    }
    if(r<n){
        for(int i=r;i<n;i++){
            if(a[i][n]==1)return 1;
        }
        return 2;
    }
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<n;j++){
            a[i][n]^=a[i][j]*a[j][n];
        }
    }
    return 3;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n+1;j++)
            cin>>a[i][j];
    int res=gaussplus();
    //1是无解，2是有多组解，3是有唯一解
    if(res==1)cout<<"No solution";
    if(res==2)cout<<"Multiple sets of solutions";
    if(res==3){
        for(int i=0;i<n;i++)cout<<a[i][n]<<endl;
    }
    return 0;
}