CF
Problem - 1695C - Codeforces
一道小清新的题，要找一条和为0的路径，因为都是1和-1
所以只需要找到从（1，1）到（n，m）的最小路径和mn[n][m]和最大路径和mx[n][m]
如果满足mn[n][m]<=0<=mx[n][m]，即找的到
#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 = 1010;
int mn[N][N], mx[N][N], a[N][N];void solve()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}for (int i = 1; i <= n; i++){mx[i][1] = mx[i - 1][1] + a[i][1];mn[i][1] = mn[i - 1][1] + a[i][1];}for (int j = 1; j <= m; j++){mx[1][j] = mx[1][j - 1] + a[1][j];mn[1][j] = mn[1][j - 1] + a[1][j];}for (int i = 2; i <= n; i++){for (int j = 2; j <= m; j++){mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + a[i][j];mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + a[i][j];}}if ((n + m - 1) & 1 || mn[n][m] > 0 || mx[n][m] < 0){cout << "NO\n";}else{cout << "YES\n";}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 607A - Codeforces（二分）（dp好题）
\(dp_i\)：记录从第\(i\) 个往前，有几个存活
最后答案要求输出被摧毁的最少数量
#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=1e6+10;
pair<int, int> a[N];
int dp[N];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].first >> a[i].second;}sort(a+1, a + n+1);for (int i = 1; i <= n;i++){int x = a[i].first - a[i].second;//左侧int p = lower_bound(a + 1, a + n + 1, make_pair(x, -1)) - a;dp[i] = dp[p-1] + 1;}int ans = 0;for (int i = 0; i <= n;i++){ans = max(ans, dp[i]);}cout << n-ans << endl;
}
Problem - 1336A - Codeforces
每个点的幸福值，应该是其深度-子树大小
所以只需要用dfs计算每个点深度以及子树大小
最后排序，选择k个点即可
注意：因为计算的sz[i]，包括本身，所以-1
#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];
int sz[N],dep[N],a[N];bool cmp(int a,int b){return a > b;
}void dfs(int u,int fa){sz[u] = 1;for (int i = 0; i < e[u].size();i++){int v = e[u][i];if(v==fa)continue;dep[v] = dep[u] + 1;dfs(v,u);sz[u] += sz[v];}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;for (int i = 1; i < n;i++){int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}dfs(1,0);for (int i = 1; i <= n;i++)a[i] = dep[i] - sz[i] + 1;sort(a + 1, a + 1 + n,cmp);LL ans = 0;for (int i = 1; i <= k;i++){ans += a[i];}cout << ans << endl;
}