第十五届蓝桥杯省赛真题C++

### 第十五届蓝桥杯省赛 C++ 真题解析 #### 握手问题 握手问题是第十五届蓝桥杯省赛中的经典题目之一。该问题的核心在于理解组合数学的应用以及如何通过编程实现高效的计算逻辑[^1]。具体来说，此问题可以通过枚举或者动态规划的方式解决。 以下是基于动态规划的解法示例： ```cpp #include <iostream> #include <vector> using namespace std; const int MOD = 1e9 + 7; long long dp[1005]; int main() { int n; cin >> n; dp[0] = 1; for (int i = 2; i <= n; i += 2) { for (int j = 0; j < i; ++j) { dp[i] = (dp[i] + dp[j] * dp[i - 2 - j]) % MOD; } } cout << dp[n]; return 0; } ``` 上述代码实现了握手问题的一种解决方案，其中 `dp` 数组用于记录不同人数下的握手方案数。 --- #### 团建问题 团建问题涉及树形结构的构建与深度优先搜索（DFS）遍历操作。利用 `map<int, vector<int>>` 数据结构能够高效地表示节点之间的关系，并支持快速查询和修改邻接表[^2]。 下面是针对团建问题的一个完整代码示例： ```cpp #include <bits/stdc++.h> using namespace std; // 定义全局变量 map<int, vector<int>> tree; bool visited[100005]; long long sum[100005], ans = 0; void dfs(int u) { visited[u] = true; for(auto& v : tree[u]){ if(!visited[v]){ dfs(v); sum[u] += sum[v]; // 子树求和 } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for(int i=1;i<n;++i){ int u,v; cin >> u >> v; tree[u].push_back(v); // 构建无向图 tree[v].push_back(u); } fill(sum+1,sum+n+1,1); // 初始化每个节点贡献为1 dfs(1); // 假设根节点为1号节点 for(int i=1;i<=n;i++) ans += abs(sum[i]-sum[1]); // 计算最终答案 cout << ans/2; // 防止重复计数除以2 return 0; } ``` 这段代码展示了如何使用 DFS 来处理树上的子树求和问题并得出最终结果。 --- #### 总结 以上两道题目分别代表了蓝桥杯竞赛中常见的两类考点——组合数学与图论基础。对于初学者而言，掌握这些基本知识点及其应用方式至关重要。