蓝桥杯算法框架

### 蓝桥杯常用算法模板 蓝桥杯竞赛中的算法设计通常涉及多种经典算法的应用，其中包括但不限于广度优先搜索（BFS）、动态规划、贪心算法以及几何计算等内容。以下是基于常见问题类型的算法框架示例： #### 1. 广度优先搜索（BFS） 广度优先搜索是一种逐层扩展的搜索方法，在解决最短路径等问题时尤为有效[^1]。 ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; struct Node { int x, y; }; int main() { int n, m; // 图大小 cin >> n >> m; vector<string> grid(n); // 输入图 for(int i=0;i<n;i++) cin>>grid[i]; queue<Node> q; bool visited[n][m]; memset(visited, false, sizeof(visited)); // 初始状态入队列 q.push({0, 0}); visited[0][0] = true; while(!q.empty()) { Node current = q.front(); q.pop(); // 扩展四个方向 static const int dx[] = {0, 0, -1, 1}; static const int dy[] = {-1, 1, 0, 0}; for(int d=0;d<4;d++) { int nx = current.x + dx[d], ny = current.y + dy[d]; if(nx >=0 && nx <n && ny>=0 && ny<m && !visited[nx][ny] && grid[nx][ny]!='#') { q.push({nx, ny}); visited[nx][ny]=true; } } } return 0; } ``` 此代码展示了如何通过 BFS 实现二维网格上的最短路径求解。 --- #### 2. 动态规划（DP） 动态规划适用于具有重叠子问题和最优子结构特性的优化问题。以下是一个经典的背包问题实现： ```cpp #include <bits/stdc++.h> using namespace std; const int MAX_W = 1e3+5; long long dp[MAX_W]; int main(){ int N,W; cin>>N>>W; vector<int> w(N),v(N); for(auto &it:w)cin>>it; for(auto &it:v)cin>>it; fill(dp,dp+W+1,-1e9); dp[0]=0; for(int i=0;i<N;i++) for(int j=W;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); cout<<*max_element(dp,dp+W+1)<<endl; return 0; } ``` 上述代码实现了零一背包问题的核心逻辑[^3]。 --- #### 3. 几何计算 针对平面内的几何问题，例如圆形覆盖或距离判断，可以采用如下模板： ```cpp #include <cmath> #include <cstdio> // 定义点类 struct Point { double x, y; } p[1000]; double dist(Point a, Point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool isCovered(double cx,double cy,double cr,int xi,int yi,int ri){ double distance=sqrt(pow(cx-xi,2)+pow(cy-yi,2))-ri-cr; return distance<=0?true:false; } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%lf%lf", &(p[i].x),&(p[i].y)); double cx,cy,cr; int count=0; for(int i=0;i<m;i++){ scanf("%lf %lf %lf",&cx,&cy,&cr); bool flag=true; for(int j=0;j<n&&flag;j++)if(isCovered(cx,cy,cr,p[j].x,p[j].y,0)==false){flag=false;} if(flag)count++; } printf("%d\n",count); return 0; } ``` 该代码片段用于处理多个圆之间的相互关系，如是否被完全覆盖的问题。 --- #### 4. 数学运算与素数筛法 在许多情况下，快速筛选质数或者进行大整数分解是非常重要的技能之一： ```cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e6+5; bool prime_flag[MAX_N]; void sieve_of_eratosthenes(){ memset(prime_flag,true,sizeof(prime_flag)); prime_flag[0]=prime_flag[1]=false; for(long long i=2;i*i<MAX_N;i++)if(prime_flag[i])for(long long j=i*i;j<MAX_N;j+=i)prime_flag[j]=false; } int main(){ sieve_of_eratosthenes(); int T,N; cin>>T; while(T--){ cin>>N; if(prime_flag[N])cout<<"Prime"<<'\n'; else cout<<"Not Prime"<<'\n'; } return 0; } ``` 这段程序利用埃拉托斯特尼筛法来高效地判定给定范围内哪些数字是质数。 ---