2026-03-05

CF

Problem - 1491C - Codeforces

差分：时间复杂度为\(O(n)\)
用lst存差分前缀和，贪心解决

记得多测清空b数组！！！

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=5010;
int b[N];
int a[N];void solve()
{int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];}for (int i = 1; i <= n + 2;i++){b[i] = 0;}LL lst = 0, ans = 0, now = 0;for (int i = 1; i <= n;i++){now = b[i] + lst;//[1,i-1]lst = now;//b[1]+b[2]……+b[i]if(now>a[i]-1){b[i + 1] += now - a[i] + 1;b[i + 2] -= now - a[i] + 1;now = a[i] - 1;}ans += a[i] - 1 - now;if(min(i+a[i],n)>=i+2){b[i + 2]++;b[min(i + a[i], n) + 1]--;}}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}

Problem - 1703G - Codeforces

这个代码贪心解法挺好想的

但是不能直接用suf[i+1]/2，因为要向下取整，所以要再开一个for循环，计算每一个a[j]/2，然后再求和
看似\(O(n^2)\)的时间复杂度，其实并非，因为对于1e9的大小，最多只能除30次2，所以加上剪枝之后，第二个for循环是\(O(1)\)，最多30次

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=1e5+10;
LL a[N], pre[N];void solve()
{int n;LL k;cin >> n >> k;LL ans = 0;for (int i = 1; i <= n;i++){cin >> a[i];pre[i] = pre[i - 1] + a[i];ans += a[i];}ans -= (n * k);int lst = n;for (int i = n; i >= 1;i--){LL cnt = 0;for (int j = i; j <= lst;j++){//最大也就到 30a[j] /= 2, cnt += a[j];}while(lst>0&&a[lst]==0)lst--;ans = max(ans, pre[i - 1] - (i - 1) * k + cnt);}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}