头像

ABlyh


访客:529

离线:1天前



ABlyh
10天前

代码

#include<iostream>
using namespace std;
int p[100100];
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        char op;
        cin>>op;
        int a,b;
        cin>>a>>b;
        if(op=='M')
        {
            a=find(a);
            b=find(b);
            p[a]=b;
        }
        else
        {
            a=find(a);
            b=find(b);
            if(a==b)
            cout<<"Yes"<<endl;
            else
            {
                cout<<"No"<<endl;
            }

        }

    }
}

核心

并查集




ABlyh
10天前

代码

#include<iostream>
using namespace std;
const int N=100210;
int cnt[N],son[N][26],idx;
char s[N];
void I(char s[])
{
    int p=0;
    for(int i=0;s[i]!=0;i++)
    {
        int u=s[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int Q(char s[])
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int u=s[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        char op;
        cin>>op>>s;
        if(op=='I')
        I(s);
        else cout<<Q(s)<<endl;
    }
}

核心

Trie




ABlyh
11天前

代码

#include<iostream>
using namespace std;
const int N=1000010;
int a[N],q[N];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i-q[hh]+1>k) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
    hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i-q[hh]+1>k) hh++;
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
}

核心

队列




ABlyh
11天前

代码

#include<bits/stdc++.h>
using namespace std;
    int n,q;
int a[100010];
int q1(int k)
{
    int L=1,R=n,mid;
    while(L<=R)
    {
        mid=L+(R-L>>1);
        if(a[mid]>=k)
            R=mid-1;
        else
            L=mid+1;
    }
    if(a[L]==k)
        return L-1;
    else
        return -1;
}
int q2(int k)
{
    int l=1,r=n,mid;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (a[mid]<=k) l = mid;
        else r = mid - 1;
    }
    if(a[l]==k)
        return l-1;
    else
        return -1;
}
int main()
{

    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=q;i++)
    {
        int k;
        cin>>k;
        cout<<q1(k);
        cout<<" "<<q2(k)<<endl;
    }
}

核心

二分查找




ABlyh
11天前

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int st[1000010];
int g[1010][1010];
queue<PII> q;
void dfs(int x,int y)
{
    q.push(make_pair(x,y));
    g[x][y]=0;
    while(q.size())
    {
        PII t=q.front();
        q.pop();
        int x1=t.first;
        int y1=t.second;
        for(int i=-1;i<=1;i++)
        {
            for(int j=-1;j<=1;j++)
            {
                if(g[x1+i][y1+j]==1)
                {
                    q.push(make_pair(x1+i,y1+j));
                    g[x1+i][y1+j]=0;
                }
            }
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            if(c=='W')
            {
                g[i][j]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j])
            {
                ans++;
                dfs(i,j);
            }

        }
    }
    cout<<ans;
}

核心

广度优先搜索




ABlyh
11天前

代码

#include<bits/stdc++.h>
using namespace std;
int g[101][101];
typedef pair<int,int> PII;
queue<PII> q;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m;
void dfs()
{
    q.push(make_pair(1,1));
    g[1][1]=1;
    while(q.size())
    {
        PII t=q.front();
        q.pop();
        int x1=t.first;
        int y1=t.second;
        for(int i=0;i<4;i++)
            if(!g[x1+dx[i]][y1+dy[i]]&&x1+dx[i]<=n&&y1+dy[i]<=m&&x1+dx[i]>=1&&y1+dy[i]>=1)
            {
                g[x1+dx[i]][y1+dy[i]]=g[x1][y1]+1;
                q.push(make_pair(x1+dx[i],y1+dy[i]));
            }
    }
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    dfs();
    cout<<g[n][m]-1;
}

核心

广度优先搜索




ABlyh
11天前

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
int n, m, ans = N;
//w[i]表示第i只小猫的重量
//sum[i]表示第i个缆车的重量
int w[N], sum[N];

//t表示当前搜索到的小猫
//k表示目前已经安排的缆车数量
void dfs(int t, int k)
{
    //最优性剪枝
    if(k >= ans) return;

    if(t == n)
    {
        ans = k;
        return;
    }

    //将当前的小猫安排在已有缆车中
    for(int i = 0; i < k; i++)
    {
        //如果当前小猫的重量 + 缆车i的重量 超过了 缆车的承重
        //可行性剪枝
        if(w[t] + sum[i] <= m)
        {
            sum[i] += w[t];
            dfs(t + 1, k);
            sum[i] -= w[t];
        }
    }

    //将当前的小猫安排在新缆车中
    //注意:k的编号是从0开始的,所以这里将小猫安排在新缆车k中
    sum[k] = w[t];
    dfs(t + 1, k + 1);
    //恢复现场
    sum[k] = 0;
}

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

    for(int i = 0; i < n; i++) cin >> w[i];

    //按小猫体重从大到小排序
    //优化搜索顺序,优先搜索分支较少的结点
    sort(w, w + n);
    reverse(w, w + n);

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}

核心

搜索与回溯




ABlyh
11天前

代码

#include<bits/stdc++.h>
using namespace std;
int f[1000][1000];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        for(int j=1;j<=a;j++)
        {
            for(int k=1;k<=b;k++)
            {
                cin>>f[j][k];
            }
        }
        for(int j=1;j<=a;j++)
        {
            for(int k=1;k<=b;k++)
            {
                f[j][k]=max(f[j-1][k],f[j][k-1])+f[j][k];
            }
        }
        cout<<f[a][b];
        cout<<endl;
    }
}

核心

DP



新鲜事 原文

ABlyh
11天前
@利洛er 你好菜啊



ABlyh
11天前

代码

#include <bits/stdc++.h>

using namespace std;
int f[5010][5010];
char a[10000];
char b[10000];
int main()
{
    int n;
    cin>>n;
    cin>>a+1;
    int m;
    cin>>m;
    cin>>b+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i]==b[j])
                f[i][j]=f[i-1][j-1]+1;
            else
                f[i][j]=max(f[i-1][j],f[i][j-1]);
    cout<<f[n][m];
    return 0;
}

核心

DP