2026-01-02

CF

Problem - 855B - Codeforces（1500）（前后缀）

题意： 已知\(p,q,r\)，要求找到\(a_i,a_j,a_k\)，满足\(i\leq j\leq k\) ，使得\(x=p\times a_i+q\times a_j+r\times a_k\) ，为最大值
遍历找前缀和后缀最大值，时间复杂度\(O(n)\)：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
LL a[N], b[N], c[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,p,q,r;cin >> n >> p >> q >> r;for (int i = 1; i <= n;i++){cin >> a[i];b[i] = a[i] * q;c[i] = a[i] * r;a[i] *= p;}for (int i = 2; i <= n;i++){a[i] = max(a[i], a[i - 1]);}for (int i = n - 1; i >= 1;i--){c[i]=max(c[i],c[i+1]);}LL ans = a[1] + b[1] + c[1];for (int i = 2; i <= n;i++){ans = max(ans, a[i] + b[i] + c[i]);}cout << ans << endl;
}

Problem - 788A - Codeforces（dp好题）

\(f[i][0]\)：第 \(i\) 位为+；\(f[i][1]\)：第 \(i\) 位为-

注意：d数组是差值，大小从1到n-1

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=1e5+10;
LL a[N], d[N],f[N][2];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];}n--;for (int i = 1; i <= n;i++){d[i] = abs(a[i] - a[i + 1]);//记得取绝对值}for (int i = 1; i <= n;i++){f[i][0] = max(f[i-1][1]+d[i],d[i]);f[i][1] = max(f[i - 1][0] - d[i], 0LL);}LL ans = 0;for (int i = 1; i <= n;i++){ans = max(ans, max(f[i][0], f[i][1]));}cout << ans << endl;
}

Problem - 597B - Codeforces

题意： 算能包含的最多线段数
思路：按照右值排序，然后贪心计算数量即可
注意：这里对于pair先输入second，再输入first，这样就可以直接排序
pair<int,int> a[N]，对于pair来说，默认对first排序

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=5e5+10;
pair<int, int> a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 0; i < n;i++){cin >> a[i].second >> a[i].first;}sort(a, a + n);int ans = 0;int lst = 0;for (int i = 0; i < n;i++){if(lst<a[i].second){ans++;lst = a[i].first;}}cout << ans <<endl;
}