长沙学院2023 第一次蓝桥训练题解

每道题都在洛谷上，每个题都有很详细的题解，可以先自行做，不会再看题解。

题目解析思路都写在代码中，中文题面就不单独解释题意了。

P2440 木材加工（二分答案）

链接：P2440 木材加工

解析 代码

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
typedef long long LL;
const int N = 1e5 + 10;
ll a[N], n, k;
bool check(int x){//判断我二分的这个数适合符合要求int sum = 0;for(int i = 1; i <=n; i ++){sum += a[i] / x;//整数除法自动向下取整}/* return sum >= k;等同于if(sum >= k) return true;//该长度符合要求我能切出k甚至更多的木材满足要求else return false;*/return sum >= k;
}
int main(){cin >> n >> k;for(int i = 1; i <= n; i ++) cin >> a[i];int l = 1, r = 1e8;//定义范围while(l <= r){int mid = (l + r) >> 1;//作用等同于 (l + r) / 2if(check(mid)) l = mid + 1;else r = mid - 1;}cout << r;return 0;
}

P3817 小A的糖果（贪心）

链接：P3817 小A的糖果

解析 代码

/*
核心思想 我所做的操作 对答案的影响怎么好怎么来
吃1号的糖果只能影响2号 如果吃2号的糖果 能影响到1号和3号
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
ll a[N],n,x;
int main()
{ll ans = 0;cin >> n >> x >> a[1]; //先读入a[1]if(a[1] > x){//a1已经超过x,至少得将其减小至xans += a[1] - x;a[1] = x;}for(int i = 2; i <= n; i ++){cin >> a[i];if(a[i] + a[i - 1] > x){ans += a[i] + a[i - 1] - x;a[i] = x - a[i - 1];//每次保证ai小于x}}cout << ans;return 0;
}

P5638 【CSGRound2】光骓者的荣耀（前缀和）

链接：P5638 【CSGRound2】光骓者的荣耀

解析 代码

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
ll a[N];
int main()
{int n, k;cin >> n >> k;for(int i=1;i<=n - 1;i++) {cin >> a[i];a[i] += a[i - 1];//前缀和}ll ans = a[n-1];for(int i = 1; i + k - 1 <= n - 1; i ++){//我们肯定不会跳到超过n号城市 i + k - 1 <= n - 1ans = min(ans, a[n - 1] - (a[i + k - 1] - a[i - 1]));}cout << ans;return 0;
}

P1115 最大子段和（贪心）

链接：P1115 最大子段和

解析 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main()
{int n, sum = 0, ans = -1e4;//ans初始化为负数scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);ans = max(ans, a[i]);if(sum + a[i] <= 0) sum = 0;//sum已经是负贡献了就将这段丢弃else {sum += a[i];ans = max(ans,sum);//每次都比较一下}}printf("%d",ans);return 0;
}

标题P1090 [NOIP2004 提高组] 合并果子 （贪心）

P1090 [NOIP2004 提高组] 合并果子

解析 代码

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
priority_queue<int, vector<int>, greater<int>>q;//小顶堆
int main()
{int n, x;cin >> n;for(int i = 1; i <= n; i ++){cin >> x;q.push(x);//加入队列}int ans = 0;/*每次取最小的两个果子，可以使得小果子的贡献次数多 大果子的贡献少达到花费的最小的目的*///top:取得队首 pop:将队首弹出for(int i = 1; i < n; i ++){int x1 = q.top(); q.pop();int x2 = q.top(); q.pop();ans += x1 + x2;q.push(x1 + x2);}cout << ans;return 0;
}

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles（动态规划）

链接：P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

解析 代码 （DP 版）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N];
int main()
{int n;cin >> n;for(int i = 1; i <= n; i ++){//输入数字三角形for(int j = 1; j <= i; j ++){//第i行恰好有i个数字cin >> f[i][j];}}for(int i = 2; i <= n; i ++){for(int j = 1; j <= i; j ++){f[i][j] += max(f[i - 1][j], f[i - 1][j - 1]);//只可能从两个方向来，1是上方，2是左上方 取最大值}}int ans = 0;for(int i = 1; i <= n; i ++){ans = max(ans, f[n][i]);//最终的最大值肯定是最底部的某个数}cout << ans;return 0;
}

解析 代码（记忆化搜索版）

/*
建议将dfs 深度优先搜索 学会再来看这篇题解
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, f[N][N], vis[N][N];
int dfs(int row, int col)//当前处在数字三角形的第几行第几列
{/*关键部分！因为我们从这一个数字向下搜索，那么能找到最大价值的路径是确定，不会因为前面是从别的地方来导致从这里出发找到的价值有变化，这就是dp的关键(无后效性)所以我们找到一次，就把答案记录下来，下次就不用再搜了，直接使用*/if(vis[row][col]) return f[row][col];vis[row][col] = 1; //这里我们开始寻找，就标记，下次再到这里就不用找了if(row == n) return f[row][col]; //找到最后一层就到底不用继续搜了f[row][col] += max(dfs(row + 1, col), dfs(row + 1, col + 1));//也是只有两种走法 取最大值return f[row][col];
}
int main()
{cin >> n;//输入数字三角形for(int i = 1; i <= n; i ++){for(int j = 1; j <= i; j ++) cin >> f[i][j];//第i行恰好有i个数字}cout << dfs(1, 1);return 0;
}