简单模板题代码

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}