2026年编程兔冬令营集训第一场作业

1、素数处理

2、深度搜索

3、动态规划

1、埃式筛法
#include<bits/stdc++.h>
using namespace std; 
bool isPrime[100000005];
int main(){
	long long i,j,n,m,ans=0;
	cin>>n;
	if(n>=2) {
		ans=1;
		for(i=3;i<=n;i+=2) if (!isPrime[i]){ //优化从3开始
			ans++;
			for(j=i*i;j<=n;j+=i) isPrime[j] = true; 
		}
	}
	cout<<ans<<endl;
	return 0;
} 

2、埃式筛法
#include<bits/stdc++.h>
using namespace std;
bool isPrime[100005];
int main(){
	int n,ans =0,t=0;
	cin>>n;
	for(long long i=2;i<=n;++i){
		if (isPrime[i]){
			++t; //非素数累计 
			ans = max(ans,t);//记录答案最大值 
		}else{
			t=0; //碰到素数，累计清零 
			// 注意i*i的范围 
			for(long long j=i*i;j<=n;j+=i) isPrime[j] = 1;
		}
	}
	cout<<ans<<endl;
	return 0; 
}




3、单点对单点dfs。按照题目的要求按照左、上、右、下顺序进行搜索，需要找第一条出路，所有使用DFS。
优化走过的点进行标志，避免重复走过。
#include <iostream>
using namespace std;
char a[25][25];//存贮地图
int r[405][3];//存贮路径
int n;
void show(int k){
    for(int i = 1;i < k;i++)
        cout<<"("<<r[i][1]<<","<<r[i][2]<<")->";
    cout<<"("<<r[k][1]<<","<<r[k][2]<<")"<<endl;
}
//从x、y点开始逐步探测 
void dfs(int x,int y,int k){
	r[k][1] = x; r[k][2] = y;
    a[x][y] = '1';//探测过的点，设置为不可探测，防止重复的探测 
    if(x == n && y == n) show(k);// 找到出路，进行打印 
    }else{
        //左、上、右、下探测，且不越界 
        if(y - 1 >= 1 && a[x][y - 1] == '0') dfs(x,y - 1,k+1);
        if(x - 1 >= 1 && a[x - 1][y] == '0') dfs(x-1,y,k+1);
        if(y + 1 <= n && a[x][y + 1] == '0') dfs(x,y + 1,k+1);
        if(x + 1 <= n && a[x + 1][y] == '0') dfs(x+1,y,k+1);
    }
} 
int main(){
    cin>>n;
    //0表示能走，1表示不能走 
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            cin>>a[i][j];    
    dfs(1,1,1);
    return 0;
}



4、单点对多点dfs。

#include<bits/stdc++.h> 
using namespace std;
bool a[110][110];
bool flag[110];
int n,e;
void init()
{
	cin>>n>>e;
	memset(flag,0,sizeof(flag));
	memset(a,0,sizeof(a));
	int x,y;
	for(int i=1;i<=e;++i)
	{
		cin>>x>>y;
		a[x][y]=1;//无向图处理双向 
		a[y][x]=1;
	}
}
void dfs(int x)
{
	cout<<x<<' ';
	flag[x]=1;//把遍历点设为已访问 
	for(int i=1;i<=n;++i) //寻找相邻连通的下一个节点 
	  if(!flag[i]&&a[x][i]==1) dfs(i);//如果找到以这个节点接着遍历 
}
int main()
{
	init();
	dfs(1);
	return 0;
}

5、这道题跟大家期末测试的“上楼梯”很像。复习一下“上楼梯”的递归公式
dp[i] = dp[i-1]+dp[i-2];
上面的题是求方案总数，新的题是求总的最大值/最小值。
dp[i] = dp[i]+max(dp[i-1],dp[i-2]);
#include<bits/stdc++.h>
using namespace std;
int dp[100010],n,A,B,C;
int main(){
	cin>>n>>A>>B>>C;
	for (int i = 1; i <= n; i++){
    	int tmp = ((long long)A * i * i + B * i + C) % 20000;
    	dp[i] = tmp - 10000;
    }
    for (int i = 2; i <= n+1; i++){
    	dp[i] = max(dp[i-1],dp[i-2]) + dp[i];
    }
    cout<<dp[n+1];
	return 0;
}


6、背包问题dp，暴力(2^n)，dp(V*n)

#include<bits/stdc++.h>
using namespace std;
int V,n,ans;
int a[31];  
int dp[20005]={0};  
int main ()
{
    int i,j;
	cin>>V>>n;
	ans = 0;
	for(i=0;i<n;i++) cin>>a[i];
	for(i=0;i<n;i++) if (a[i]<=V)
	{
		//如果前面的物品能凑出j的体积，则加上a[i]后能凑出j+a[i]的体积
		//注意j从大到小 
		for(j=V-a[i];j>0;j--) if (dp[j])
		{
			dp[j+a[i]]  =1;
			ans = max(ans, j+a[i]);
			
		}
		dp[a[i]] =1;
		ans = max(ans, a[i]);
	}	
   	cout<<V-ans<<endl;
    return 0;
}




7、也是类背包问题，用暴力枚举可以通过40分(2^n)。
假设dp[x][y]表示x条边可以组成长度为y的方案数。
对边进行排序，对于每一条边a[i]有选或者不选进行出路。dp[x][y]的公式有
x=3->x>3的情况，有dp[3][y+a[i]]+=dp[3][y];
x=2->x=3的情况，有dp[3][y+a[i]]+=dp[2][y];
x=1->x=2的情况，有dp[2][y+a[i]]+=dp[1][y];
x=0->x=1的情况，有dp[1][a[i]]++;
#include<bits/stdc++.h>
using namespace std;
long long V,n,ans=0,mod = 998244353;
int a[5005];  
long long dp[4][5005]={0};  
int main ()
{
    int i,j,t,sum=0;
	cin>>n;
	ans = 0;
	for(i=0;i<n;i++) cin>>a[i];
	//排序从小到大，方便后面处理前i个的最大值是a[i] 
	sort(a,a+n);
	for(i=0;i<n;i++) 
	{	
		for(j=min(5001,sum);j>=0;--j) {
			t=min(5001,j+a[i]);
			//边数已经>=3的 
			if (dp[3][j]>0){
				if (j>a[i]) ans = (ans +dp[3][j]) % mod;
				dp[3][t] = (dp[3][t]+dp[3][j]) % mod;
			}
			//边数已经=2的 
			if (dp[2][j]>0){
				if (j>a[i]) ans = (ans +dp[2][j]) % mod;
				dp[3][t] = (dp[3][t]+dp[2][j]) % mod;
			}
			//边数已经=1的 
			if (dp[1][j]>0) dp[2][t] = (dp[2][t]+dp[1][j]) % mod;
		}
		sum+=a[i];
		//边数=1 
		dp[1][a[i]]++;
	}	
   	cout<<ans<<endl;
    return 0;
}