备战蓝桥杯-洛谷

今天打算写一些洛谷上面的题目

P10904 [蓝桥杯 2024 省 C] 挖矿

https://www.luogu.com.cn/problem/P10904

看了大佬写的题解才写出来这道题的：题解：P10904 [蓝桥杯 2024 省 C] 挖矿 - 洛谷专栏

思路：

这是一道贪心的题目，用前缀和的方式，用l和r记录两个方向的前缀和，遍历m次步数，并且计算反方向（m-2*i）能挖到多少矿，注意这些矿的位置可能会有重复的

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#define int long long
const int N = 2e6 + 10;
int l[N], r[N];
signed main()
{int n, m,cnt=0,t=0;int ans=0;std::cin >> n >> m;for (int i = 1;i <= n;i++){int x;std::cin >> x;if (x < 0){l[-x] ++;}else if (x > 0){r[x] ++;}elsecnt ++;}for (int i = 1;i <= m;i++){l[i] += l[i - 1];r[i] += r[i - 1];}for (int i = 1;i <= m;i++){t = l[i];if ((m - 2 * i) > 0){t += r[m - 2 * i];}ans = std::max(t, ans);t = r[i];if ((m - 2 * i) > 0){t += l[m - 2 * i];}ans = std::max(t, ans);}std::cout << ans + cnt<<"\n";return 0;
}

P10902 [蓝桥杯 2024 省 C] 回文数组

P10902 [蓝桥杯 2024 省 C] 回文数组 - 洛谷 | 计算机科学教育新生态

这道题也是贪心题目，我也是在看了大佬的题解之后写出来的：题解：P10902 [蓝桥杯 2024 省 C] 回文数组 - 洛谷专栏

思路：加一和减一的效果是一样的，所以在这里只用考虑加一的做法，两个相邻的数加一肯定比单独加一的步骤少，所以先考虑相邻两个数加一的方案，再考虑单个数加一的方案

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define int long long
const int N = 1e6 + 10;
int a[N], b[N];
signed main()
{int n;std::cin >> n;for (int i = 1;i <= n;i++){std::cin >> a[i];}for (int i = 1;i <= (n + 1) / 2;i++){if (a[i] < a[n - i + 1]){b[i] = a[n - i + 1] - a[i];}else{b[n - i + 1] = a[i] - a[n - i + 1];}}int ans = 0;for (int i = 1;i <= n;i++){int minn = std::min(b[i], b[i + 1]);b[i] -= minn;b[i + 1] -= minn;ans += minn;ans += b[i];}std::cout << ans;return 0;
}