CF
Problem - 1473D - Codeforces
前缀最大值，后缀最大值
前缀最小值，后缀最小值
注意：要后缀要减去删掉的值
#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=2e5+10;
int premx[N], sufmx[N];
int premn[N], sufmn[N];
int a[N];void solve()
{int n,m;cin >> n >> m;string s;cin >> s;s = " " + s;int x = 0;for (int i = 1; i <= n;i++){if(s[i]=='-'){a[i] = a[i - 1] - 1;}else{a[i] = a[i - 1] + 1;}premx[i] = max(premx[i - 1], a[i]);premn[i] = min(premn[i - 1], a[i]);}sufmx[n + 1] = -1e9;sufmn[n + 1] = 1e9;for (int i = n; i >= 1;i--){sufmx[i] = max(sufmx[i + 1], a[i]);sufmn[i] = min(sufmn[i + 1], a[i]);}while(m--){int l, r;cin >> l >> r;int t = a[r] - a[l - 1];cout << max(premx[l - 1], sufmx[r + 1]-t) - min(premn[l - 1], sufmn[r + 1]-t) + 1 << endl;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1693B - Codeforces
贪心，从子结点开始，尽量扩大子结点
#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=2e5+10;
vector<int> e[N];
LL ans, l[N], r[N];
LL a[N];void dfs(int u){LL sum = 0;for (int i = 0; i < e[u].size();i++){int v = e[u][i];dfs(v);sum += a[v];}if(sum<l[u])a[u] = r[u], ans++;elsea[u] = min(r[u], sum);
}void solve()
{int n;cin >> n;ans = 0;for (int i = 1; i <= n;i++){e[i].clear();}for (int i = 2, x; i <= n; i++){cin >> x;e[x].push_back(i);}for (int i = 1; i <= n;i++){cin >> l[i] >> r[i];}dfs(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 - 201A - Codeforces
数学，算几个能发现，奇数时能保证得到最多的1
注意特判3！
#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=2e5+10;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int x;cin >> x;if(x==3){//特判cout << 5 << endl;return 0;}int p = 0;for (int i = 0; i<=10;i++){p = ((2 * i + 1) * (2 * i + 1) + 1) / 2;//能放一半（上取整）a[i] = p;//边长为 (2*i+1) 时，最多能放 p个 1}/*1->a[0] = 13->a[1] = 55->a[2] = 137->a[3] = 259->a[4] = 41*/int ans = 0;for (int i = 0;;i++){if(a[i]>=x){ans = i;break;}}cout << ans * 2 + 1 << endl;//cout << a[10] << endl;//a[10]=221，边长不会超过 10
}