【第15届蓝桥杯C/C++B组】试题&参赛经历&经验&个人题解

阅读本书更多章节>>>>

文章目录

试题 A: 握手问题试题 B: 小球反弹试题 C: 好数试题 D：R 格式试题 E：宝石组合试题F：数字接龙试题G：爬山试题H：拔河我的感想

试题 A: 握手问题

分	试题 A: 握手问题 本题总分：5 分
问题描述	小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。 在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手（且仅有一次）。但有 7 个人，这 7 人彼此之间没有进行握手（但这 7 人与除这 7 人以外的所有人进行了握手）。 请问这些人之间一共进行了多少次握手?注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。
答案提交	这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

我的答案

#include<iostream>#include<vector>using namespace std;int Solution(){int ans=0;for(int i=49;i>=7;--i){ans+=i;cout<<i<<endl;}return ans;//1204}int main(){cout<<Solution();return 0;}

GPT答案

这个问题可以用组合数学的知识来解决。

首先，总共有 50 个人，每个人要与除自己以外的其他所有人进行一次握手，那么总的握手次数为 (502)(250)。

但是有 7 个人彼此之间没有进行握手，这意味着这 7 个人之间本应该进行 (72)(27) 次握手，但是实际上没有进行握手。

所以最终的握手次数为 (502)−(72)(250)−(27)。

计算结果为：

(502)−(72)=50×492−7×62=1225−21=1204(250)−(27)=250×49−27×6=1225−21=1204

所以最终答案为 1204。

试题 B: 小球反弹

分	试题 B: 小球反弹 本题总分：5 分
问题描述	有一长方形，长为 343720 单位长度，宽为 233333 单位长度。 在其内部左上角顶点有一小球（无视其体积），其初速度如图所示且保持运动速率不变，分解到长宽两个方向上的速率之比为 dx : dy = 15 : 17。 小球碰到长方形的边框时会发生反弹，每次反弹的入射角与反射角相等， 因此小球会改变方向且保持速率不变（如果小球刚好射向角落，则按入射方向原路返回）。 从小球出发到其第一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍五入保留两位小数。
答案提交	这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个小数，在提交答案时只填写这个小数，填写多余的内容将无法得分。

我的答案

#include<iostream>#include<vector>#include<algorithm>using namespace std;long double Solution(){long double length=343720.0,width=233333.0;long double dx=15.0,dy=17.0;long double step=411764.1176470588;//411764int t=0;long double dist=0;while(true){t++;dist+=step;while(dist>length+3){dist-=length;}if(abs(dist-length)<0.0001)break;}cout<<"t="<<t<<endl;cout<<"dist="<<dist<<endl;int x=15*15;int y=17*17;int x_y=x+y;double k=sqrt(x_y);long double total=t*step;cout<<"total="<<total<<endl;cout<<"k="<<k<<endl;long double ans=total*k/dx;cout<<endl;return ans;}int main(){cout<<fixed<<Solution();//550162599.885198return 0;}

这题由于太复杂gpt算不了，就不给出gpt的生成内容了

试题 C: 好数

描述	试题 C: 好数 时间限制: 1.0s 内存限制: 256.0MB 本题总分：10 分
问题描述	一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 · · · ）上的数字是奇数，偶数位（十位、千位、十万位 · · · ）上的数字是偶数，我们就称之 为“好数”。 给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。
输入格式	一个整数 N。
输出格式	一个整数代表答案。
样例输入 1	24
样例输出 1	7
样例输入 2	2024
样例输出 2	150
样例说明	对于第一个样例，24 以内的好数有 1、3、5、7、9、21、23，一共 7 个。
评测用例规模与约定	对于 10% 的评测用例，1 ≤ N ≤ 100。对于 100% 的评测用例，1 ≤ N ≤ 1e7。

我的答案

#include<iostream>#include<vector>#include<algorithm>using namespace std;int Solution(){int n;cin>>n;int ans=0;for(int i=1;i<=n;i+=2){int dont=0;int t=i;bool add=true;while(t>0){int wei=t%10;wei%=2;if(wei==dont){add=false;break;}dont=wei;t/=10;}if(add)ans++;}return ans;}int main(){cout<<Solution();return 0;}

GPT的评价

这段代码试图统计从 1 到给定的正整数 n 之间的好数的数量。在这段代码中，它使用了一个名为 Solution 的函数来计算好数的数量。

这段代码的思路是从 1 开始遍历到 n，对每个数字进行判断是否为好数。在判断是否为好数时，它使用了一个布尔变量 add 来表示当前数字是否为好数，并在遍历数字的每一位时进行更新。具体来说，它遍历了每个数字的每一位，如果相邻位上的数字奇偶性相同（即相邻位都是奇数或者都是偶数），则将 add 设置为 false，表示当前数字不是好数，否则将 add 设置为 true，表示当前数字是好数。最后统计所有好数的数量并返回。

这段代码的逻辑是正确的，可以用于计算好数的数量。但是，它的时间复杂度较高，因为对于每个数字，需要遍历其每一位来判断奇偶性。当 n 很大时，这种方法会很慢。在实际应用中，我们通常会选择更高效的算法来解决这个问题，比如动态规划。

GPT给出的答案

我们可以使用动态规划来解决这个问题。定义一个二维数组 dp[i][j]，其中 i 表示数字的位数，j 表示最高位数字。dp[i][j] 表示在位数为 i 时，最高位数字为 j 的好数的数量。

首先，我们需要确定状态转移方程。假设 i 位数的好数数量为 dp[i]，则有以下几种情况：

如果当前位数是奇数位（个位、百位、万位…），那么当前位数的好数数量取决于前一位偶数位的好数数量，因为无论前一位的数字是什么，当前位都可以选择奇数位的数字（1、3、5、7、9）。如果当前位数是偶数位（十位、千位、十万位…），那么当前位数的好数数量取决于前一位奇数位的好数数量，因为无论前一位的数字是什么，当前位都可以选择偶数位的数字（0、2、4、6、8）。

根据以上分析，我们可以得出状态转移方程：

dp[i][j] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5] + dp[i - 1][6] + dp[i - 1][7] + dp[i - 1][8] + dp[i - 1][9]

其中，如果当前位数是奇数位，则 dp[i][j] 只与前一位偶数位的好数数量有关；如果当前位数是偶数位，则 dp[i][j] 只与前一位奇数位的好数数量有关。

最后，我们将所有位数为奇数位或偶数位的好数数量相加，即为从 1 到 N 之间的好数的数量。

#include <iostream>#include <vector>using namespace std;// 计算从 1 到 N 之间的好数的数量int countGoodNumbers(int N) {    const int MOD = 1e9 + 7;    // 初始化 dp 数组    vector<vector<long long>> dp(20, vector<long long>(10, 0));    // 初始条件：1 位数时，好数的数量为 5（1、3、5、7、9）    for (int j = 1; j <= 9; ++j) {        dp[1][j] = 1;    }    // 动态规划计算好数的数量    for (int i = 2; i <= 19; ++i) {        for (int j = 1; j <= 9; ++j) {            if (i % 2 == 1) { // 当前位数为奇数位                // 前一位是偶数位的好数数量                for (int k = 0; k <= 9; k += 2) {                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;                }            } else { // 当前位数为偶数位                // 前一位是奇数位的好数数量                for (int k = 1; k <= 9; k += 2) {                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;                }            }        }    }    // 计算好数的总数量    long long ans = 0;    for (int i = 1; i <= 19; ++i) {        for (int j = 1; j <= 9; ++j) {            ans = (ans + dp[i][j]) % MOD;        }    }    return ans;}int main() {    int N;    cin >> N;    cout << countGoodNumbers(N) << endl;    return 0;}

试题 D：R 格式

描述	试题 D: R 格式 时间限制: 1.0s 内存限制: 256.0MB 本题总分：10 分
问题描述	小蓝最近在研究一种浮点数的表示方法：R 格式。 对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。 给定一个转换参数 n，将浮点数转换为 R 格式整数的做法是：1. 将浮点数乘以 2^n; 2. 四舍五入到最接近的整数。
输入格式	一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。
输出格式	输出一行表示答案：d 用 R 格式表示出来的值。
样例输入	2 3.14
样例输出	13
样例说明	3.14 × 2^2 = 12.56，四舍五入后为 13。
评测用例规模与约定	对于 50% 的评测用例：1 ≤ n ≤ 10，1 ≤ 将 d 视为字符串时的长度 ≤ 15。 对于 100% 的评测用例：1 ≤ n ≤ 1000，1 ≤ 将 d 视为字符串时的长度 ≤ 1024；保证 d 是小数，即包含小数点。

我的思路

这题不会写，没办法了，直接暴力。感觉应该是用高精度来实现，但是我忘了高精度乘法咋写了…

我的代码

#include<iostream>#include<vector>#include<algorithm>using namespace std;void Solution(){int n;long double d;cin>>n>>d;long double val=pow(2,n);long long result=d*val+0.5f;cout<<result;}int main(){Solution();return 0;}

GPT写的跟我一样，都是错误答案

试题 E：宝石组合

描述	试题 E: 宝石组合 时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分
问题描述	在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。 小蓝共找到了 N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量： 其中 LCM 表示的是最小公倍数函数。小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。
输入格式	第一行包含一个整数 N 表示宝石个数。 第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。
输出格式	输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。
样例输入	5 1 2 3 4 9
样例输出	1 2 3
评测用例规模与约定	对于 30% 的评测用例：3 ≤ N ≤ 100，1 ≤ Hi ≤ 1000。 对于 60% 的评测用例：3 ≤ N ≤ 2000。 对于 100% 的评测用例：3 ≤ N ≤ 10^5，1 ≤ Hi ≤ 10^5。

S = H a H b H c ⋅ L C M ( H a , H b , H c ) L C M ( H a , H b ) ⋅ L C M ( H a , H c ) ⋅ L C M ( H b , H c ) S=H_aH_bH_c\cdot\frac{LCM(H_a,H_b,H_c)}{LCM(H_a,H_b)\cdot LCM(H_a,H_c)\cdot LCM(H_b,H_c)} S=Ha​Hb​Hc​⋅LCM(Ha​,Hb​)⋅LCM(Ha​,Hc​)⋅LCM(Hb​,Hc​)LCM(Ha​,Hb​,Hc​)​

我的思路

​ 本来想用哈希表来剪枝，不知道为什么当时没写出来，一直报错，devc++我又不知道哪里错了，没办法 反正也是骗分，直接暴力了。

GPT的思路和我的一样，都是：

1.先对宝石的 “闪亮度” 进行排序，从小到大排列。

2.枚举所有可能的三种宝石组合，可以采用三重循环来实现，其中第一个循环选择第一种宝石，第二个循环选择第二种宝石，第三个循环选择第三种宝石。

3.对于每种组合，计算它们的精美程度。精美程度可以定义为三种宝石的乘积除以它们的最小公倍数。最小公倍数可以通过最大公约数来求得。

我的答案

#include<iostream>#include<vector>#include<algorithm>#include<unordered_map>#include<map>#include<utility>using namespace std;int gcd(int a,int b){if(!b)return a;return gcd(b,a%b);}int lcm(int a,int b){return a/gcd(a,b)*b;}void Solution(){int n;cin>>n;vector<int>g(n);for(int &a:g)cin>>a;sort(g.begin(),g.end());int a=0,b=0,c=0;int maxx=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(j!=i){for(int k=0;k<n;k++){if(k!=j&&k!=i){int q,w,e,r;q=lcm(g[i],g[j]);w=lcm(g[i],g[k]);e=lcm(g[j],g[k]);r=lcm(q,g[k]);int tem=g[i]*g[j]*g[k]*r/q/w/e;if(tem>maxx){maxx=tem;a=g[i];b=g[j];c=g[k];}}}}}}cout<<a<<' '<<b<<' '<<c;return;}int main(){Solution();return 0;}

试题F：数字接龙

描述	试题 F: 数字接龙 时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分
问题描述	小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为 N × N 的格子棋盘上展开，其中每一个格子处都有着 0 到 K-1 之间的整数。游戏规则如下： 1. 从左上角 (0, 0) 处出发，目标是到达右下角 (N-1, N-1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。 2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0, 1, 2, …, K-1, 0, 1, 2, …, K-1, 0, 1, 2, …。 3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。 4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1)，那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。 为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如上图 2 所示；因此行进路径可以用一个包含 0 到 7 之间的数字字符串表示，如上图 1 是一个迷宫示例，它所对应的答案就是：41255214。 现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 -1。
输入格式	第一行包含两个整数 N、K。接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。
输出格式	输出一行表示答案。如果存在答案输出路径，否则输出 -1。
样例输入	3 3 0 2 0 1 1 1 2 0 2
样例输出	41255214
样例说明	行进路径如图 1 所示。
评测用例规模与约定	对于 80% 的评测用例：1 ≤ N ≤ 5。对于 100% 的评测用例：1 ≤ N ≤ 10，1 ≤ K ≤ 10。

我的思路

​ 一眼是图论的题，再看一眼以为是普通的DFS或者BFS，最后想好决定使用DFS解决。第一印象感觉没啥难的，但是中间有一个不可以出现交叉的线路，这个设定卡了我很久，最后才想到使用set来纪录是否交叉，感觉最后的答案会超出时间复杂度或者内存，但是样例能过。这个题是我考试时候写的第三题，写了快一个多小时才写完。当时都想放弃了，还有点后悔学过图论，因为图论的题都是一步错就全错，非常耽误时间。

我的代码

#include<iostream>#include<vector>#include<algorithm>#include<functional>#include<set>#include<utility>using namespace std;string Solution(){vector<vector<int>>move{{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0}};int n,k;cin>>n>>k;int totalsize=n*n-1;vector<vector<int>>g(n,vector<int>(n));for(auto &a1:g)for(auto &a2:a1)cin>>a2;vector<vector<bool>>vis(n,vector<bool>(n,false));set<pair<double,double>>st;string ans="";function<void(int,int,string)>dfs=[&](int i,int j,string s){if(s.size()==totalsize){if(i==n-1&&j==n-1){if(ans==""||!lexicographical_compare(ans.begin(),ans.end(),s.begin(),s.end()))ans=s;}return;}int nxt=(g[i][j]+1)%k;for(int u=0;u<8;u++){int x=i+move[u][0];int y=j+move[u][1];if(x>=0&&x<n&&y>=0&&y<n&&!vis[x][y]&&g[x][y]==nxt){if(u%2==1){double rx=i+move[u-1][0];double ry=j+move[u-1][1];double lx=i+move[u+1][0];double ly=j+move[u+1][1];double tx=(rx+lx)/2.0;double ty=(ry+ly)/2.0;pair<double,double>insp;insp.first=tx;insp.second=ty;auto it=st.find(insp);if(it!=st.end())continue;else{st.insert(insp);vis[x][y]=true;//与下面重复了 char fr='0'+u;string tem=s+fr;dfs(x,y,tem);st.erase(insp);vis[x][y]=false;}}else{vis[x][y]=true;char fr='0'+u;string tem=s+fr;dfs(x,y,tem);vis[x][y]=false;}}}};if(n==1)return "";vis[0][0]=true;dfs(0,0,"");return ans==""?"-1":ans;}//F/*3 30 2 01 1 12 0 2*/int main(){cout<<Solution();return 0;}

GPT的点评

这段代码实现了对数字接龙问题的求解，通过深度优先搜索（DFS）来找到符合条件的路径。具体来说，它遍历了从起点到终点的所有可能路径，并使用一个集合 st 来记录已经访问过的格子，以避免重复访问。在搜索过程中，通过递归调用 dfs 函数，不断更新路径，并根据规则判断下一步可以移动到哪个格子。如果找到了满足条件的路径，则将其记录下来，并在搜索结束后输出。

总体来说，这段代码是一个较为合理的实现，应该能够成功解决数字接龙问题。

GPT的代码

要解决数字接龙问题，可以采用深度优先搜索（DFS）的方法来寻找路径。具体步骤如下：

从左上角 (0, 0) 出发，向右下方向进行搜索。在每个格子上，尝试所有可能的移动方向，并检查是否满足接龙规则。使用递归深度优先搜索，直到找到一条满足条件的路径或者搜索到底部无法继续。注意记录已经访问过的格子，避免重复访问。

下面是基于上述思路的代码实现：

#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;// 定义八个方向的移动向量const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};// 检查移动是否在边界内bool isValid(int x, int y, int N) {    return x >= 0 && x < N && y >= 0 && y < N;}// 深度优先搜索函数bool dfs(vector<vector<int>>& board, vector<vector<bool>>& visited, int x, int y, int K, string& path) {    if (path.length() == K) // 已经找到一条路径        return true;    for (int i = 0; i < 8; ++i) {        int nx = x + dx[i];        int ny = y + dy[i];        if (isValid(nx, ny, board.size()) && !visited[nx][ny] && board[nx][ny] == (path.length() % K)) {            visited[nx][ny] = true;            path.push_back('0' + board[nx][ny]);            if (dfs(board, visited, nx, ny, K, path))                return true;            path.pop_back();            visited[nx][ny] = false;        }    }    return false;}// 主函数，解决数字接龙问题string solve(vector<vector<int>>& board, int N, int K) {    vector<vector<bool>> visited(N, vector<bool>(N, false));    string path;    visited[0][0] = true;    path.push_back('0' + board[0][0]);    if (dfs(board, visited, 0, 0, K, path))        return path;    else        return "-1";}int main() {    int N, K;    cin >> N >> K;    vector<vector<int>> board(N, vector<int>(N));    for (int i = 0; i < N; ++i)        for (int j = 0; j < N; ++j)            cin >> board[i][j];    cout << solve(board, N, K) << endl;    return 0;}

试题G：爬山

描述	试题 G: 爬山 时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分
问题描述	小明这天在参加公司团建，团建项目是爬山。在 x 轴上从左到右一共有 n 座山，第 i 座山的高度为 。他们需要从左到右依次爬过所有的山，需要花费的体力值为 。然而小明偷偷学了魔法，可以降低一些山的高度。他掌握两种魔法，第一种魔法可以将高度为 H 的山的高度变为 ，可以使用 P 次；第二种魔法可以将高度为 H 的山的高度变为 ，可以使用 Q 次。并且对于每座山可以按任意顺序多次释放这两种魔法。小明想合理规划在哪些山使用魔法，使得爬山花费的体力值最少。请问最优情况下需要花费的体力值是多少？
输入格式	输入共两行。第一行为三个整数 n，P，Q。第二行为 n 个整数
输出格式	输出共一行，一个整数代表答案。
样例输入	4 1 1 4 5 6 49
样例输出	18
样例说明	将第四座山变为 ⌊√49⌋ = 7，然后再将第四座山变为 ⌊7/2⌋ = 3。体力值为 4 + 5 + 6 + 3 = 18。
评测用例规模与约定	对于 20% 的评测用例，保证 n ≤ 8，P = 0。对于 100% 的评测用例，保证 n ≤ 100000，0 ≤ P ≤ n，0 ≤ Q ≤ n，0 ≤ hi ≤ 100000。

我的思路

​ 一眼动态规划。但是由于前面图论浪费了太多时间，剩余时间肯定写不完。没办法只能使用优先队列+贪心来实现了。测试用例能过，应该能骗点分。

我的代码

#include<iostream>#include<vector>#include<queue>#include<algorithm>using namespace std;int Solution(){int n,P,Q;cin>>n>>P>>Q;priority_queue<int,vector<int>>pq;for(int i=0;i<n;i++){int a;cin>>a;pq.push(a);}for(int i=0;i<P;i++){int val=pq.top();pq.pop();val=sqrt(val);pq.push(val);}for(int i=0;i<Q;i++){int val=pq.top();pq.pop();val/=2;pq.push(val);}int ans=0;while(!pq.empty()){ans+=pq.top();pq.pop();}return ans;}int main(){cout<<Solution();return 0;}

GPT的思路

这个问题可以使用动态规划来解决。我们可以定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示前 i 座山使用 P 次第一种魔法和 Q 次第二种魔法时，总体力消耗的最小值。然后我们可以根据当前山的高度以及剩余魔法使用次数进行状态转移，最后得到的 dp[n][P][Q] 就是答案。

具体的状态转移方程如下：

对于每座山，我们有两种选择：不使用魔法或者使用第一种或第二种魔法。如果我们选择不使用魔法，则当前山的高度就是 h[i]，体力消耗为 dp[i-1][j][k] + h[i]。如果我们选择使用第一种魔法，则当前山的高度变为 ⌊√h[i]⌋，体力消耗为 dp[i-1][j-1][k] + ⌊√h[i]⌋。如果我们选择使用第二种魔法，则当前山的高度变为 ⌊h[i]/2⌋，体力消耗为 dp[i-1][j][k-1] + ⌊h[i]/2⌋。

最后我们在所有可能的选择中选取体力消耗最小的值作为 dp[i][j][k] 的值。

下面是代码实现：

#include <iostream>#include <vector>#include <algorithm>#include <cmath>using namespace std;int main() {    int n, P, Q;    cin >> n >> P >> Q;    vector<int> h(n);    for (int i = 0; i < n; ++i) {        cin >> h[i];    }    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(P + 1, vector<int>(Q + 1, 0)));    for (int i = 1; i <= n; ++i) {        for (int j = 0; j <= P; ++j) {            for (int k = 0; k <= Q; ++k) {                // 不使用魔法                dp[i][j][k] = dp[i - 1][j][k] + h[i - 1];                // 使用第一种魔法                if (j > 0) {                    int new_height = sqrt(h[i - 1]);                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][k] + new_height);                }                // 使用第二种魔法                if (k > 0) {                    int new_height = h[i - 1] / 2;                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k - 1] + new_height);                }            }        }    }    cout << dp[n][P][Q] << endl;    return 0;}

试题H：拔河

分	试题 H: 拔河 时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分
问题描述	小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为 ai。在闲暇之余，小明决定在班级里组织一场拔河比赛。为了保证比赛的双方实力尽可能相近，需要在这 n 名同学中挑选出两个队伍，队伍内的同学编号连续:，其中。两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。
输入格式	输入共两行。第一行为一个正整数 n。第二行为 n 个正整数 。
输出格式	输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。
样例输入	5 10 9 8 12 14
样例输出	1
样例说明	其中一种最优选择方式：队伍 1：队伍 2：力量值和分别为 10 + 9 + 8 = 27，12 + 14 = 26，差距为
评测用例规模与约定	对于 20% 的评测用例，保证 n ≤ 50。 对于 100% 的评测用例，保证 n ≤ 10^3，ai ≤ 10^9。

我的思路

​ 当时做的时候读错题了，以为编号不连续，最后随便写了个答案交了。这没办法，代码就不展示了。

GPT的答案

这个问题可以使用动态规划来解决。首先，我们需要计算出所有可能的子数组的力量值之和，并保存下来。然后，我们可以使用动态规划来找到两个力量值之和尽可能接近的两个子数组。

具体步骤如下：

遍历数组，计算每个子数组的力量值之和，保存在一个二维数组中。对于每个子数组，计算其力量值之和与前面所有子数组的力量值之和的差值，并保存在一个新的二维数组中。使用动态规划来找到力量值之和尽可能接近的两个子数组。可以定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 个子数组中，选取 j 个子数组时的最小力量值之和差距。动态规划的状态转移方程为：dp[i][j] = min(dp[i-1][j], abs(sum[i] - sum[k] - dp[k][j-1]))，其中 sum[i] 表示前 i 个子数组的力量值之和，k 为从 j-1 到 i-1 的遍历。最终的答案即为 dp[n][2]。

下面是实现代码：

#include <iostream>#include <vector>#include <algorithm>#include <cmath>using namespace std;int minPowerDifference(vector<int>& powers) {    int n = powers.size();    // 计算每个子数组的力量值之和    vector<int> sum(n + 1, 0);    for (int i = 1; i <= n; ++i) {        sum[i] = sum[i - 1] + powers[i - 1];    }    // 计算力量值之和的差值并保存    vector<vector<int>> diff(n + 1, vector<int>(n + 1, 0));    for (int i = 1; i <= n; ++i) {        for (int j = i; j <= n; ++j) {            diff[i][j] = sum[j] - sum[i - 1];        }    }    // 动态规划找到力量值之和尽可能接近的两个子数组    vector<vector<int>> dp(n + 1, vector<int>(3, INT_MAX / 2));    dp[0][0] = 0;    for (int i = 1; i <= n; ++i) {        for (int j = 1; j <= 2; ++j) {            for (int k = j - 1; k <= i - 1; ++k) {                dp[i][j] = min(dp[i][j], abs(diff[i][i] - dp[k][j - 1]));            }        }    }    return dp[n][2];}int main() {    int n;    cin >> n;    vector<int> powers(n);    for (int i = 0; i < n; ++i) {        cin >> powers[i];    }    cout << minPowerDifference(powers) << endl;    return 0;}

我的感想

​ 蓝桥杯结束了，学了这么久的算法，虽然写的不是特别好，大多都是直接暴力，但是希望能进国赛吧。感觉这次出的题比去年的要简单，图论那道题其实直接输出-1都能骗不少分。学了好久的动态规划居然一道题也没写。感觉爬山这题应该是能写的，很普通的动态规划而已。最后拿什么奖我在评论区里面说。

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/zhengce/2024-04-18/160173.html，文章来源：网络cs，作者：焦糖，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！