标签
codeforces
字数
1040 字
阅读时间
6 分钟
C. Cards Partition
题意
本身有
同时有
思路
假定分成
同时，分成了
那么根据
代码
CPP
int solve() {
int n, k;
cin >> n >> k;
int sum = 0;
int mi = 0;
rep(i, 0, n) {
cin >> arr[i];
sum += arr[i];
mi = max(mi, arr[i]);
}
int ksum = sum + k;
int ans = -1;
for (int p = 1; p <= n; p++) {
int m = ksum / p;
// 分成的m份都要大于数组的最大值
// 分成的m份和p大小，要在sum和sum+k中间
if (m >= mi && m * p >= sum && m * p <= ksum) ans = p;
}
return ans;
}D. Speedbreaker
题意
[[../../../数据结构与算法/贪心]] 给定数组，第一秒选定一个点作为初始点，以后得每一秒都可以向左或右占领一格，要求在
思路
从左右开始找，假定
那么每次占领最外层的点，然后更新那些点对应的合适区间，所有的区间并起来就是答案
代码
CPP
##include <bits/stdc++.h>
using namespace std;
##define endl "\n"
##define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
##define rep(i, j, k) for (int i = (j); i < (k); i++)
##define all(x) x.begin(), x.end()
##define pii pair<int, int>
const int N = 2e5 + 5;
int arr[N];
int solve() {
int n;
cin >> n;
rep(i, 1, n + 1) cin >> arr[i];
/*
从两边开始，如果区间[l,r]的arr[l]arr[r]大于或等于len
那么对于两边，区间内任意一点开始都可以，合适的区间变成原本的合理区间与当前的左右边界的arr的区间取交集
*/
int ll = 1, rr = n;
int l = 1, r = n;
while (l <= r) {
int len = r - l + 1;
int l_l = l - arr[l] + 1, l_r = l + (arr[l] - 1);
int r_l = r - (arr[r] - 1), r_r = r + arr[r] - 1;
ll = max({ll, l_l, r_l});
rr = min({rr, l_r, r_r});
if (arr[l] >= len && arr[r] >= len) {
l++, r--;
} else if (arr[l] >= len) {
l++;
} else if (arr[r] >= len) {
r--;
} else {
return 0;
}
}
return rr - ll + 1;
}
int main() {
IOS;
int t;
cin >> t;
while (t--) {
cout << solve() << endl;
}
return 0;
}E. Tree Pruning
题意
给树，要求每次减去叶子，让所有的叶子结点在同一层，求最少次数
思路
对于想让所有叶子结点在
也就是说
- 所有深度比deep深的结点都要减去
- 所有子树深度比deep浅的结点都要减去
代码
CPP
##include <bits/stdc++.h>
using namespace std;
##define endl "\n"
##define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
##define rep(i, j, k) for (int i = (j); i < (k); i++)
##define all(x) x.begin(), x.end()
##define pii pair<int, int>
const int N = 5e5 + 10;
vector<int> g[N];
int depth_cnt_sum[N];
int son_depth_cnt_sum[N];
int mxdep = 0; // 整棵树的最大深度
// 返回最深的儿子深度
int dfs(int i, int f, int dep) {
depth_cnt_sum[dep]++;
mxdep = max(mxdep, dep);
int sonmxdep = dep;
for (int j = 0, v; j < g[i].size(); j++) {
v = g[i][j];
if (v == f) continue;
sonmxdep = max(sonmxdep, dfs(v, i, dep + 1));
}
son_depth_cnt_sum[sonmxdep]++;
return sonmxdep;
}
void init(int n, int mx) {
mxdep = 0;
for (int i = 0; i <= mx; i++) {
depth_cnt_sum[i] = 0;
son_depth_cnt_sum[i] = 0;
}
for (int i = 1; i < n; i++) g[i].clear();
}
// 1. 所有深度比deep深的结点
// 2. 所有子树深度比deep浅的结点
int get(int deep) {
return depth_cnt_sum[mxdep] - depth_cnt_sum[deep] + son_depth_cnt_sum[deep - 1];
}
void solve() {
int n;
cin >> n;
rep(i, 0, n - 1) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0, 1);
for (int i = 1; i <= mxdep; i++) {
depth_cnt_sum[i] += depth_cnt_sum[i - 1];
son_depth_cnt_sum[i] += son_depth_cnt_sum[i - 1];
}
int ans = 1e9;
for (int deep = 1; deep <= mxdep; deep++) {
ans = min(ans, get(deep));
}
cout << ans << endl;
init(n + 1, mxdep);
}
int main() {
IOS;
int t;
cin >> t;
init(N, N - 1);
while (t--) solve();
return 0;
}贡献者
lulaalu