简单模板题代码

· · 个人记录

模板1 \text{Flood Fill}

#include<bits/stdc++.h>
using namespace std;
struct Pair{
    int x,y;
};
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n;
vector < vector <bool> > mp;
int cnt=0;
bool check(Pair h)
{
    return h.x>=1&&h.x<=n&&h.y>=1&&h.y<=n&&(mp[h.x][h.y]==false);
}
void Bfs(Pair st)
{
    deque <Pair> dq;
    dq.push_back(st);
    while(!dq.empty())
    {
        Pair cur=dq.front();
        mp[cur.x][cur.y]=true;
        for(int i=0;i<4;i++)
        {
            Pair q={cur.x+dx[i],cur.y+dy[i]};
            if(check(q))
                dq.push_back(q);
        }
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    mp.resize(n+1,vector <bool> (n+1,false));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int p;
            scanf("%d",&p);
            mp[i][j]=p;
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!mp[i][j]){
                cnt++;
                BFS({i,j});
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}

模板2 \text{Is Prime?}

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n)
{
    if(n<=1)
        return false;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}

模板3 \text{Sieve of primes}

#include<bits/stdc++.h>
using namespace std;
vector <bool> a(100010,true); 
void sieve(void)
{
    a[1]=false;
    for(int i=2;i<=100010;i++)
        if(a[i])
            for(int j=i*2;j<=100010;j+=i)
                a[j]=false;
}

模板4 进制转换1 （\text{to Octal}）

#include<bits/stdc++.h>
using namespace std;
long long to_ll(char ch)
{
    if(ch>='0'&&ch<='9')
        return ch-'0';
    else
        return ch-'A'+10;
}
int main()
{
    int k;
    scanf("%d",&k);
    string str;
    cin>>str;
    long long ans=0;
    int cnt=0;
    for(int i=str.length()-1;i>=0;i--)
    {
        ans+=pow(k,cnt)*to_ll(str[i]);
        cnt++;
    }
    printf("%lld\n",ans);
    return 0;
}

模板5 最长不下降子序列（O(n~ log_2~n)）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    vector <int> a(n+1),f(n+1,-1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(f[ans]<=a[i]){
            f[++ans]=a[i];
        }else{
            int left=1,right=ans;
            while(left<=right)
            {
                int mid=(left+right)/2;
                if(f[mid]<a[i]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
            f[left]=a[i];
        }
    }
    printf("%d\n",ans);
    return 0;
}

模板6 背包问题

01背包
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long q,n;
    scanf("%lld%lld",&q,&n);
    vector <long long> c(n+1),w(n+1);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&w[i],&c[i]);
    vector <long long> dp(q+1,0);
    for(int i=1;i<=n;i++)
        for(int j=q;j>=w[i];j--)
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
    printf("%lld",dp[q]);
    return 0;
}
完全背包
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,t;
    scanf("%lld%lld",&t,&n);
    vector <long long> v(n+1),w(n+1);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&w[i],&v[i]);
    vector <long long> dp(t+1,0);
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=t;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    printf("%lld\n",dp[t]);
    return 0;
}
重量背包（01）
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long q,n;
    scanf("%lld%lld",&q,&n);
    vector <long long> w(n+1);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&w[i]);
    vector <long long> dp(q+1,0);
    for(int i=1;i<=n;i++)
        for(int j=q;j>=w[i];j--)
            dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
    printf("%lld",dp[q]);
    return 0;
}
重量背包（完全）
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,t;
    scanf("%lld%lld",&t,&n);
    vector <long long> w(n+1);
    for(int i=1;i<=n;i++)
        scanf("%lld",&w[i]);
    vector <long long> dp(t+1,0);
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=t;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
    printf("%lld\n",dp[t]);
    return 0;
}

模板7 并查集

#include<bits/stdc++.h>
using namespace std;
vector<int>root;
int find(int x)
{
    if(root[x]==x)
        return x;
    else
        return root[x]=find(root[x]);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    root.resize(n+1);
    for(int i=1;i<=n;i++)
        root[i]=i;
    while(m--)
    {
        int z,x,y;
        scanf("%d%d%d",&z,&x,&y);
        if(z==1){
            x=find(x),y=find(y);
            if(x!=y)root[x]=y;
        }
        else printf("%c\n",find(x)==find(y)?'Y':'N');
    }
    return 0;
}