拉链法

//拉链法--数据结构和建树和图一样的呀
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100003;
int h[N],e[N],ne[N],idx;

void insert(int x)
{
    //哈希函数--把-10^9--10^9映射成10^5
    int k = (x%N+N)%N;
    //当前这个点存地值是x！！！
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx;
    idx++;
}

bool find(int x)
{
    //哈希函数--把-10^9--10^9映射成10^5
    int k = (x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i])
    {
        //在每一个槽中实际查询的仍然是x，不是k！！
        if(e[i]==x)return true;
    }
    return false;
}

int main()
{
    int n;
    cin>>n;

    memset(h, -1, sizeof h);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0]=='I')insert(x);
        else
        {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

开放寻址法

//开放寻址法，好像并查集的另类应用
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
//默认将数组开到2-3倍的一个质数
const int N = 200003,null = 0x3f3f3f3f;
int h[N];

//如果x在哈希表中，k就是他的下标
//如果x不在哈希表中，k就是他应该存储的地方
int find(int x)
{
   int k = (x%N+N)%N; 
   //当前h[k]位置被别人占领了
   while(h[k]!=null && h[k]!=x)
   {
       k++;
       //到头了，再从新开始啊
       if(k==N) k=0;
   }
   //返回x真正存放的位置
   return k;
}

int main()
{
    int n;
    cin>>n;

    memset(h,0x3f,sizeof h);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);

        int k=find(x);
        if(op[0]=='I') h[k]=x;
        else
        {
            if(h[k]!=null) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

并查集写法

能互相走动的点都放到一个集合中
最后看看从0-h能不能两端都有点，串联起来

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

using namespace std;
typedef long long LL;

const int N = 1010;
LL n,h,r;
LL x[N],y[N],z[N];
int p[N];
//返回ij这两个点之间的距离
long long dist(int i,int j)
{
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
}

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>h>>r;

        for(int i=1;i<=n;i++) p[i]=i;
        for(int i=1;i<=n;i++)
        {
            x[i]=y[i]=z[i]=0;
            cin>>x[i]>>y[i]>>z[i];
        }
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                if(dist(i,j)<=4*r*r) p[find(i)]=find(j);

        //搜搜看哪个家族有靠近地面和天花板的，
        //找到满足条件的,把0，n+1 加入
        p[n+1]=n+1;
        p[0]=0;
        //这里到底是怎么保证的呀
        for(int i=1;i<=n;i++)
        {
            if(z[i]<=r) p[find(0)]=find(i);
            if(z[i]>=h-r) p[find(n+1)]=find(i);
        }
        if(find(0)==find(n+1)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

BFS大法，大爱BFS

//BFS写法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long LL;

const int N = 1010;
LL n,h,r;
LL x[N],y[N],z[N];
int p[N];
bool f[N];
//返回ij这两个点之间的距离
long long dist(int i,int j)
{
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
}

void bfs()
{
    queue<int> q;
   // bool flag = false;
    //从地板开始搜索
    for(int i=1;i<=n;i++)
        if(z[i]<=r) q.push(i),f[i]=true;
    while(q.size())
    {
        int p = q.front();
        q.pop();

        //满足条件的，从这里直接就出去了
        if(z[p]+r>=h)
        {
         //   flag = true;
            puts("Yes");
            return;
        }
        //搜索一遍所有的节点，找到相邻的，可以连起来的
        for(int i=1;i<=n;i++)
        {
            //如果这个节点已经被搜索过了，不再搜索
            if(f[i]==true) continue;
            //满足相邻的条件，加入队列
            if(dist(p,i)<=4*r*r)
            {
                q.push(i);
                f[i]=true;
            }
        }

    }

    //if(flag ==false) 
    puts("No");

    return;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>h>>r;
        //一定记得多组输入输出时，要初始化各种状态数组啊！！！
        memset(f,0,sizeof f);

        for(int i=1;i<=n;i++)
        {
            x[i]=y[i]=z[i]=0;
            cin>>x[i]>>y[i]>>z[i];
        }
      bfs();
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20010;
int p[N];

int  find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;

    while (m -- ){
        int a,b;
        scanf("%d%d",&a,&b);
        //合并
        p[find(b)]=find(a);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(find(a)==find(b)) puts("Yes");
        else puts("No");
    }
    return 0;
}

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

using namespace std;

const int N = 200010,M=2*N;
int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int d1[N],d2[N],p[N],up[N];
int maxd;//最长直径
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

//标准的求树的直径的代码
//求解每一个结点u作为最高点的时候的最大直径
void dfs_d(int u,int father)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            dfs_d(j,u);
            //逻辑：搜索完j节点后，j的最大值和次大值就都知道了
            //判断一下u结点的值是否发生改变
            int distance = d1[j]+1;
            if(distance > d1[u] )
            {
                d2[u]=d1[u];
                d1[u]=distance;
                p[u]=j; //u的子树中最大的是j节点
            }
            else if(distance>d2[u])d2[u]=distance;
        }
    }
    maxd = max(maxd,d1[u]+d2[u]);
}

//找j节点往上走的最大长度 j的父亲是u
//u可以往上走，往最大边走，往次大边走（如果u的最大边节点是j p[u]=j）
void dfs_u(int u,int father)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            up[j]=up[u]+1;  //选择u往上走的路
            if(p[u]!=j) up[j]=max(up[j],d1[u]+1); //选择最大子路
            else up[j]=max(up[j],d2[u]+1); //选择次大子路
            //自上而下，先更新完上面的值，再向下搜索！！
            dfs_u(j,u);
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    //找一下每个结点的最大值和次大值
    dfs_d(0,-1);
    dfs_u(0,-1);
    for(int i=0;i<=n-1;i++)
    {
      int d[3]={d1[i],d2[i],up[i]};
      sort(d,d+3);
      //如果一个节点往外发散的三条边中，最大的两条加起来等于直径，说明他就在直径上！！
      if(d[1]+d[2]==maxd) cout<<i<<endl;
    }
    return 0;
}

这道题目的关键是：括号序列可以分成两类
1、回文样式的，从中间往外扩
2、ab合并样式的，需要用k，石子合并的思想哦~
两者组合一起

//集合的含义：从l--r之间满足称为对称序列的需要添加括号的方案数
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110,INF=1e7;

int n;
int f[N][N];//f[l][r],从l--r组成要添对称的需加的最少数量


bool is_match(char l,char r)
{
    if(l=='('&&r==')') return true;
    if(l=='['&&r==']') return true;
    return false;
}
int main()
{
    string s;
    cin>>s;
    n=s.size();

    for(int i=0;i<n;i++) f[i][i]=1;
    //所有1个括号的只需要增加一个括号就可以变成对称的
    //循环长度，循环左右区间
    for(int len=2;len<=n;len++)
        for(int i=0;i+len-1<n;i++)
        {
            int j=i+len-1;
            f[i][j]=INF;

            //两侧匹配上了，往里缩
            if(is_match(s[i],s[j]))
            f[i][j]=f[i+1][j-1];
          //  cout<<"f[0][0]"<<f[i][j]<<endl;
            f[i][j]=min(f[i][j],min(f[i+1][j],f[i][j-1])+1);

            for(int k=i;k<j;k++)
            {
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
        }
    cout<<f[0][n-1]<<endl;
    return 0;
}

//这个题需要用到一些数论的常识
//裴蜀定理：两个数的组合必定是gcd的倍数
//gcd>1 不能被组合的数有无限个
//gcd=1 定理：最大不能被表示的数字是(a-1)(b-1)-1

//完全背包优化版本
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
const int M = 10010;
bool f[M];
int w[N];
int n;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];

    int d=0;
    for(int i=1;i<=n;i++)
        d=gcd(w[i],d);
    //cout<<d<<endl;
    int res=0;
    if(d==1)
    {
        f[0]=true;
        for(int i=1;i<=n;i++)
            for(int j=w[i];j<=M;j++)
                 f[j] = f[j] | f[j-w[i]];
        for(int i=0;i<=M;i++)
            if(f[i]==false) res++;
        cout<<res<<endl;
    }
    else cout<<"INF"<<endl;
    return 0;
}

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

using namespace std;

typedef long long LL;

const int N=3;
int n,m;

void mul(int c[],int a[],int b[][N])
{
    int temp[N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;
    memcpy(c,temp,sizeof temp);
}
void mul(int c[][N],int a[][N],int b[][N])
{
    int temp[N][N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%m;
    memcpy(c,temp,sizeof temp);
}

int main()
{
    cin>>n>>m;
    //[f1,f2,s1] A = [fn,fn+1,sn]
    int f1[N]={1,1,1};
    int a[N][N]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };
    n--;
    while(n){
        if(n&1)mul(f1,f1,a); //res=rea*a
        mul(a,a,a); //a=a*a
        n>>=1;
    }
    cout<<f1[2]<<endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;

using namespace std;

const int N = 100010,M=2*N;
int h[N],e[M],ne[M],w[N],idx;
int n;
int res;
LL f[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

//f[u]存放的是以u为最高点的子树陀中的最大值
void dfs(int u,int father)
{
    f[u]=w[u];
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            dfs(j,u);
            //如果有负数的子树，我们是不要的！我们要的是最大值
           if(f[j]>0) f[u]+=f[j];
        }
    }

}
int main()
{
    memset(h, -1, sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);

    }

    dfs(1,-1);

    LL res = f[1];
    for(int i=2;i<=n;i++) res=max(res,f[i]);

    cout<<res<<endl;
    return 0;

}

添加多少个字母------转换一下，这样直接想比较抽象
一般都是找一串字母中有多少回文串，这样才正常，要往这上面想啊
删去多少个字母可以变成回文串
n-最长回文串数量 —剩下的就是多余的，可以删掉

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

using namespace std;

const int N=1010;
int f[N][N];//表示从L-R的回文序列的最大长度
char s[N];
int main()
{
    scanf("%s",s);
    int n = strlen(s);
    for(int len = 1;len<=n;len++)
    {
        for(int l=0;l+len-1<n;l++)
        {
            int r = l+len-1;
            if(len==1) f[l][r]=1;
            else
            {
                if(s[l]==s[r])f[l][r]=f[l+1][r-1]+2;
                if(f[l+1][r]>f[l][r]) f[l][r]=f[l+1][r];
                if(f[l][r-1]>f[l][r]) f[l][r]=f[l][r-1];
                if(f[l+1][r-1]>f[l][r])f[l][r]=f[l+1][r-1];
            }
        }
    }
    cout<<n-f[0][n-1]<<endl;
    return 0;
}

f[i][j]:考虑前i种糖果，且总和除以k的余数是j的方案

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

using namespace std;
const int N = 110;

int n,k;
int w[N];
int f[N][N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>w[i];
    //f[0][1]...[k-1]，余数不可能大于1，所以这些方案都不合法
    memset(f,-0x3f,sizeof f);
    //当一种糖果都不考虑，且余数为0的糖果总量为0
    f[0][0] = 0;
    //这里必须这么写：因为j代表的是个余数
    //j-w[i]是非常必要的，很有可能是负数，必须要转换成正数
    //不是普通背包里转换成当前背包容量是j，减去第i个包的重量
    //原理不太一致
    // (x+k)%k---转换成正数
    //(j-w[i])%k 这是那个x，一步都不能省略的！！
    for(int i=1;i<=n;i++)
        for(int j=0;j<k;j++)
        {
            f[i][j]=max(f[i-1][j],f[i-1][((j-w[i])%k+k)%k]+w[i]);
        }
    //从n种糖果考虑，且除以k的余数是0的最大糖果数量
    cout<<f[n][0]<<endl;
    return 0;

}