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

const int N = 1010;
int n,m;
int v[N],w[N],s[N];
int f[N][N];

int main()
{   
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    //从前i个物品中选择总体积不超过j，并且选择的物品数不超过s[i]的，所有选法的价值的最大值
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k*v[i]<=j&&k<=s[i];k++) 
                f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    cout<<f[n][m];
    return 0;
}

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

const int N =1001;
int n,m;
int v[N],w[N];//体积 重量 f[i][j]是选法
int f[N][N];

int main()
{
    cin>> n >> m;
    for (int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for (int i=1;i<=n;i++)
    //所有「只考虑前 i 个物品」，「并且总体积不超过 j」 的“选法”的集合
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,d[360][5] ,bz[4][8][11],man[4]={0,3,7,10};
    //d代表节点，bz标注状态数组 man 杯子满水的情况
    scanf("%d",&t);//第三个杯子 目标水量
    memset(d,0,sizeof(d));
    memset(bz,0,sizeof(bz));
    //状态初始化 
    d[1][1] = 0;
    d[1][2] = 0;
    d[1][3] = 10;
    d[1][4] = 0;
    //标注第一种状态
    bz[0][0][10] =1;
    int i=0,j=1;
    while(i<j)
    {
        i++;
        for(int p=1;p<=3;p++)//倒出水的杯子
            for(int q=1;q<=3;q++)//倒入水的杯子
                if(p!=q && d[i][p]>=0 && d[i][q]<=man[q])
                {
                    j++;
                    for(int k=1;k<=4;k++) d[j][k] = d[i][k];

                    if(d[j][p]+d[j][q]<=man[q]) //倒出杯的水加上倒入杯的水小于满杯
                    {//把自己倒空
                        d[j][q] = d[j][q]+d[j][p];
                        d[j][p] = 0;
                    }
                    else
                    {//把对方倒满
                        d[j][p] = d[j][p] - (man[q] - d[j][q]);
                        d[j][q] = man[q];
                    }
                    if(bz[d[j][1]][d[j][2]][d[j][3]] == 0)
                    {
                       bz[d[j][1]][d[j][2]][d[j][3]] = 1;
                       d[j][4]++;
                       if(d[j][3] == t)
                       {
                           printf("%d",d[j][4]);
                           return 0;
                       }

                    }
                    else j--;
                }
    }
    printf("%d",-1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{   
    //bfs
    int n,st,en,a[205],d[205][3],bz[205],c[2]={-1,1};
    scanf("%d%d%d",&n,&st,&en);
    if(st == en)
    {
        printf("%d",0);
        return 0;
    }

    memset(d,0,sizeof(d));
    memset(bz,0,sizeof(bz));

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    d[1][1] = st; //楼层
    d[1][2] = 0; //到达这一层要的步数
    bz[st] = 1;

    int i=0,j=1;
    while(i<j)
    {
        i++;
        for(int t = 0;t<=1;t++)
        {
            int k = d[i][1]+a[d[i][1]]*c[t];
            if(k>=1 && k<=n)
            {
                j++;
                d[j][1] = k;
                d[j][2] = d[i][2]+1;
                if(bz[k] == 0)
                {
                    bz[k] =1;
                    if(k == en)
                    {
                        printf("%d",d[j][2]);
                        return 0;
                    }
                }
                else j--; 
            }
        }
    }
    printf("%d",-1);
    return 0;
}

还没有吃透

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

const int N = 100100;

int hp[N],h[N],ph[N],sizes;

void heap_swap(int a,int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}

void down(int u)
{
    int t = u;
    if(u*2 <= sizes&& h[u*2]<h[t]) t = u * 2; //如果左儿子存在并且比父节点小则交换下标
    if(u*2+1<= sizes&& h[u*2+1]<h[t]) t = 2 * u + 1; //同上 右儿子
    if(u != t)
    {
        heap_swap(u ,t);
        down(t);
    }
}

void up(int u)
{
    while(u / 2 && h[u/2]>h[u]) //父节点存在，并且父节点的值大于u
    {
        heap_swap(u/2 , u);
        u/=2;
    }
}


int main()
{
    int n,m=0;;
    scanf("%d",&n);
    while(n--)
    {
        char op[10];
        int k,x;
        scanf("%s",op);
        if(!strcmp(op,"I"))
        {
            scanf("%d",&x);
            sizes++;
            m++;
            ph[m] = sizes,hp[sizes] = m;
            h[sizes] = x;
            up(sizes);
        }
        else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
        else if(!strcmp(op,"DM")) 
        {
            heap_swap(1,sizes);
            sizes--;
            down(1);
        }
        else if(!strcmp(op,"D"))
        {
            scanf("%d",&k);
            k = ph[k];
            heap_swap(k,sizes);
            sizes--;
            down(k),up(k);
        }
        else{
            scanf("%d%d",&k,&x);
             k = ph[k];
             h[k] = x;
             down(k),up(k);
        }
    }
}

用树来维护多个集合中元素的个数，用并查集来进行操作 把集合元素存到一个数组中 其余操作和 模板一样

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

const int N = 100010;

int p[N],k[N]; //集合编号,集合中数的个数
int n,m,a,b; 

int find(int x)
{
    if(p[x]!=x) p[x] = find(p[x]); //递归查找父节点（集合编号）
    return p[x];
}


int main()
{
    scanf("%d%d",&n,&m);
    //因为一开始每个元素的都在一个集合中所以根节点 就是元素本身
    for(int i=1;i<=n;i++) 
    {
        p[i] = i;  //父节点
        k[i] = 1;//一开始每一个集合都有一个元素
    }
    char op[2];
    while(m--)
    {
        scanf("%s",op);
        // 合并 把a的父节点设置为b的父节点
        if(op[0]=='C') 
        {   
            scanf("%d%d",&a,&b);
            if(find(a)==find(b)) continue; //如果两个元素本来就在一个集合中 那么不需要合并
            k[find(b)] += k[find(a)]; //b合并掉a后 连通块的个数要加上a
            p[find(a)] = find(b); //a的父节点更新为b的根节点
        }
        else if(op[1]=='1'){
            scanf("%d%d",&a,&b);
            //查找 如果两个元素的父节点都相同 那么这两个元素一定在一个集合中
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }else if(op[1]=='2')
        {   
            scanf("%d",&a);
            printf("%d\n",k[find(a)]);
        }
    }
    return 0;
}

并查集作用：

1.将两个集合合并（把任意一个树的父节点指向另一个树的父节点，使前者成为后者的一个子节点）
2.询问两个元素是否在一个集合当中（查找两个元素的父节点，如果两个父节点（编号）相同则说明在一个集合中）

原理：

每个集合用一棵树表示，树根就是这个集合的编号，每个节点存的是它的父节点，p[x] 表示的是x的父节点

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

const int N = 100010;

int p[N]; //集合编号 父节点
int n,m,a,b; 

int find(int x)
{
    if(p[x]!=x) p[x] = find(p[x]); //递归查找根节点（集合编号）
    return p[x];
}


int main()
{
    scanf("%d%d",&n,&m);
    //因为一开始每个元素的都在一个集合中所以根节点 就是元素本身
    for(int i=1;i<=n;i++) p[i] = i;

    char op[2];
    while(m--)
    {
        scanf("%s%d%d",op,&a,&b);
        // 合并 把a的父节点设置为b的父节点
        if(op[0]=='M') p[find(a)] = find(b);
        else{
            //查找 如果两个元素的父节点都相同 那么这两个元素一定在一个集合中
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

trie树主要用于单词的插入和查找 以树的形式存

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

const int N =10010;
int son[N][26],cnt[N],idx; //存单词的,存单词出现次数的,下标 树的层
char str[N];

void insert(char str[])
{
    int p=0;//从根节点出发
    for(int i=0;str[i];i++)
    {
        int u = str[i]-'a'; //字母转数字
        //如果当前不存在该字母则插入
        if(!son[p][u]) son[p][u]=++idx; 
        p = son[p][u];//子节点下移
    }
    cnt[p]++;//插入完成把该单词所对应的下标计数
}

int query(char str[])
{
    int p =0; //同上
    for(int i=0;str[i];i++)
    {
        int u = str[i]-'a'; //同上
        if(!son[p][u]) return 0; //如果当前字母不存在则结束
        p = son[p][u]; //子节点下移
    }
    return cnt[p]; //返回该单词对应下标的计数器 
}


int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        char op[2];
        scanf("%s%s",op,str);
        if(op[0]=='I') insert(str);
        else printf("%d\n",query(str));
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

// 看入队元素 是否比队中的元素小 若比队中的元素小 则队要清空 
// 看入队元素 是否比队中的元素大 若比队中的元素大 则队要清空

int main()
{
    int n, k;
    cin >> n >> k; //n个数 k代表窗口的长度
    for (int i = 0; i < n; ++ i) //输出最小值的情况
    {
        scanf("%d", &a[i]); //读入数据
        if (i -  q[hh] + 1 >k) ++ hh;                  // 队满 队头出（窗口的末尾到头的长度没有超过限制）
        while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若入队的元素比队中的所有元素都要小 那么从队尾
        q[++ tt] = i;                                  // 下标加到队尾
        if (i + 1 >= k) printf("%d ", a[q[hh]]);       // 输出结果
    }
    cout << endl;
    hh = 0; tt = -1;                                   // 重置！
    for (int i = 0; i < n; ++ i) //输出最大值的情况
    {
        if (i -  q[hh] + 1 >k) ++ hh;
        while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
        q[++ tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    return 0;
}

#include<bits/stdc++.h> 
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=10;i++)
    {
        printf("%d x %d = %d\n",i,n,i*n);
    }
}