A.小竹与妈妈

#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int a,b,x;
	cin>>a>>b>>x;
	
	cout<<(x-b)/a<<endl;
	return 0;
} 

B.走丢的小竹

#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+10;
vector<int> points[N];
int n,m,q;

int main()
{
	cin>>n>>m>>q;
	
	for(int i=1;i <= n;i++)
	{
        int x;
		cin>>x;
		points[x].push_back(i);
	}
	
	while(q--)
	{
		int x;
		cin>>x;
		
		printf("%d\n",n-points[x].size());
	}
	
	return 0;
}

C.小竹关禁闭

方法一：状态表示：f[i]表示只考虑前i个物品，且选上第i个物品最大长度. 当i <= k+1时f[i]=a[i],当i > k+1时f[i]=max(f[i],f[j]+a[i]),其中j从1到第i-k-1. 时间复杂度o(n*n)

#include<algorithm>
#include<cstring>
using namespace std;
const int N=4010;
int a[N],f[N];
int n,k;

int main()
{
	cin>>n>>k;
	
	for(int i=1;i <= n;i++) cin>>a[i];
	
	for(int i=1;i <= n;i++)
	{
		if(i <= k+1) f[i]=a[i];
		else 
        {
            for(int j=1;j <= i-k-1;j++)
                f[i]=max(f[i],f[j]+a[i]);
        }
	}
	
    int res=0;
    for(int i=1;i <= n;i++) res=max(res,f[i]);
    
	cout<<res<<endl;
	return 0;
} 

方法一：状态表示：f[i]表示只考虑前i个物品的最大长度. 此时第i个物品可选可不选两种情况 时间复杂度o(n)

#include<algorithm>
#include<cstring>
using namespace std;
const int N=4010;
int a[N],f[N];
int n,k;

int main()
{
	cin>>n>>k;
	
	for(int i=1;i <= n;i++) cin>>a[i];
	
	for(int i=1;i <= n;i++)
	{
		if(i < k+1) f[i]=max(f[i-1],a[i]);
		else f[i]=max(f[i-k-1]+a[i],f[i-1]);
	}
	
	cout<<f[n]<<endl;
	return 0;
} 

D.游戏购买！

两遍bfs 时间复杂度：O(n*m)

#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=2010;
int w[N][N];
vector<PII> legal;
int n,m,x;
int sx,sy,ex,ey;

void bfs(int sx1,int sy1,int d[][N])
{
	PII q[N*N];
	int hh=0,tt=-1;
	q[++tt]={sx1,sy1};
	d[sx1][sy1]=0;
	
	int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
	
	while(hh <= tt)
	{
		PII t=q[hh++];
		
		for(int i=0;i < 4;i++)
		{
			int x=t.x+dx[i],y=t.y+dy[i];
			if(x < 0 || x >= n || y < 0 || y >= m) continue;
			if(d[x][y] != -1) continue;
			if(w[x][y] == -1) continue;
			q[++tt]={x,y};
			d[x][y]=d[t.x][t.y]+1;
		}
	}
}

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

	cin>>sx>>sy>>ex>>ey;
	sx--,sy--,ex--,ey--;
	
	for(int i=0;i < n;i++)
	for(int j=0;j < m;j++)
	{
		cin>>w[i][j];
		
		if(w[i][j]  > x) 
		legal.push_back({i,j});
	}
	
	if(!legal.size())
	{
		cout<<-1<<endl;
		return 0;
	} 
	
	int d1[N][N],d2[N][N];
	memset(d1,-1,sizeof d1);
	memset(d2,-1,sizeof d2);
	bfs(sx,sy,d1);
	bfs(ex,ey,d2);
	
	bool flag=false;
	int ans=1e9;
	for(auto r:legal)
	{
		if(d1[r.x][r.y] > 0 && d2[r.x][r.y] > 0)
		{
			flag=true;
			ans=min(ans,d1[r.x][r.y]+d2[r.x][r.y]);
		}
	}
	
	if(flag) cout<<ans<<endl;
	else cout<<-1<<endl;
	
	return 0;
}


 

E.寻找小竹！

第一种方法:(图的存储，线性筛法，最大公约数，dfs)

#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e6+10,M=5e6+10;
vector<int> edges[N];
int c[N];
int dp[N];
bool st[M];
int minp[M];
int primes[M];
int cnt;
int n;

bool ok(int a,int b)
{
    int d=__gcd(a,b);
    vector<int> v;
    
    while(d > 1)
    {
        int mi=minp[d];
        v.push_back(mi);
        
        while(d%mi == 0) d/=mi;
    }
    
    return v.size() >= 2;
}

void dfs(int u,int fa)
{
    dp[u]=1;
    
    for(auto t:edges[u])
    {
        if(t == fa) continue;
        dfs(t,u);
        if(ok(c[u],c[t])) dp[u]+=dp[t];
    }
}

void screen_primes()
{
    for(int i=2;i <= M;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            minp[i]=i;
            st[i]=true;
        }
        
        for(int j=0;primes[j] <= M/i;j++)
        {
            st[primes[j]*i]=true;
            minp[primes[j]*i]=primes[j];
            if(i%primes[j] == 0) break;
        }
    }
}

int main()
{
    screen_primes();
    
    cin>>n;
    
    for(int i=1;i <= n;i++) scanf("%d",&c[i]);
    
    for(int i=0;i < n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    
    dfs(1,-1);
    
    int ans=1;
    for(int i=1;i <= n;i++)
    ans=max(ans,dp[i]);
    
    cout<<ans<<endl;
    
    return 0;
}

第二种方法（并查集（外加子集大小的维护）,埃氏筛法，最大公约数）

#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e6+10,M=5e6+10;
vector<int> edges[N];
int c[N];
int dp[N];
bool st[M];
int minp[M];
int primes[M];
int cnt;
int n;

bool ok(int a,int b)
{
    int d=__gcd(a,b);
    vector<int> v;
    
    while(d > 1)
    {
        int mi=minp[d];
        v.push_back(mi);
        
        while(d%mi == 0) d/=mi;
    }
    
    return v.size() >= 2;
}

void dfs(int u,int fa)
{
    dp[u]=1;
    
    for(auto t:edges[u])
    {
        if(t == fa) continue;
        dfs(t,u);
        if(ok(c[u],c[t])) dp[u]+=dp[t];
    }
}

void screen_primes()
{
    for(int i=2;i <= M;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            minp[i]=i;
            st[i]=true;
        }
        
        for(int j=0;primes[j] <= M/i;j++)
        {
            st[primes[j]*i]=true;
            minp[primes[j]*i]=primes[j];
            if(i%primes[j] == 0) break;
        }
    }
}

int main()
{
    screen_primes();
    
    cin>>n;
    
    for(int i=1;i <= n;i++) scanf("%d",&c[i]);
    
    for(int i=0;i < n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    
    dfs(1,-1);
    
    int ans=1;
    for(int i=1;i <= n;i++)
    ans=max(ans,dp[i]);
    
    cout<<ans<<endl;
    
    return 0;
}