比赛链接

https://codeforces.com/contest/2019

A题

思路

分别求出奇数位和偶数位的最大值，之后进行比较即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 5;
int n;
int a[N];
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}int maxx1 = 0, maxx2 = 0, ans1 = 0, ans2 = 0;for (int i = 1, j = 2; i <= n; i += 2, j += 2){maxx1 = max(maxx1, a[i]);ans1++;if (j <= n){ans2++;maxx2 = max(maxx2, a[j]);}}cout << max(maxx1 + ans1, maxx2 + ans2) << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

B题

思路

我们考虑预处理出每一个区间对答案产生的贡献。考虑每个区间以第$a_i$个为端点，到$a_{i+1}$中间的数对答案产生的贡献。

对第$i$个端点的贡献和为$(n-i+1)\times (i-1)+(n-i)$，即以$a_i$为端点产生的贡献。

对第$a_i+1$到$a_{i+1}$之间的数对答案产生的贡献为$i\times (n-i)$。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, q, k;
int a[N];
void solve()
{cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a[i];}map<int, int> mp;mp[n - 1] += (a[2] - a[1]);mp[n - 1]++;for (int i = 2; i < n; i++){int op = n - i + 1;int cnt = i - 1;mp[cnt * op + (n - i)]++;mp[(op - 1) * (cnt + 1)] += (a[i + 1] - a[i] - 1);}while (q--){cin >> k;cout << mp[k] << " ";}cout << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

C题

思路

可以分两种情况进行讨论。

根据题意，我们最多可以将卡牌分为$n$组。

我们规定$sum$表示原先卡牌个数的总和，$maxx$表示卡牌个数最多的那个卡牌类型的数量。

当$k=0$的时候，只需要对原先的卡牌进行分组即可。我们假设可以将每$i$个卡牌分为一组，如果$sum\%i==0$并且$sum/i\ge maxx$，则可以将卡牌分为每$i$个一组。我们直接对答案进行暴力枚举即可。

当$k>0$的时候，我们依旧假设可以将每$i$个卡牌分为一组，对于我们最后一组的卡牌，会有$sum\%i$个，如果我们想要将其补全，需要再添加$op=i-sum\%i$个卡牌。如果$k<op$，则不可将卡牌分为每$i$个一组。否则，我们令$res=(sum+op)/i+(k-op)/i$，如果$res\ge maxx$，则$i$为可行的答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, k, sum;
int a[N];
void solve()
{cin >> n >> k;sum = 0;for (int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}int maxx = *max_element(a + 1, a + 1 + n);if (k == 0){int ans = 1;for (int i = 1; i <= n; i++){if (sum % i == 0 && sum / i >= maxx){ans = i;}}cout << ans << endl;}else{int ans = 1;for (int i = 2; i <= n; i++){int op = i - sum % i;if (op == i)op = 0;if (op > k)continue;int res = (sum + op) / i + (k - op) / i;if (res < maxx)continue;ans = i;}cout << ans << endl;}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

D题

思路

这里提供一个线段树的做法。

我们假设以点$i$为起点，向两端不断扩散。对于$i$点左边的点$j$，其必须在$j$点左端的点前被征服。对于$i$点右边的点$k$，其必须在$k$点右端的点前被征服。

因此，我们可以预处理出前缀最小值和后缀最小值。

对于每一个起点$i$，必然有一套单独的$vector<int>dfn$表示每一个点最晚可以在什么时刻被征服，而这个$dfn$值便是前面说的$i$点左边点的前缀最小值，和$i$点右边点的后缀最小值。

我们对于每一个$df{n}_i$，将区间$[df{n}_i,n]$全部加上一个正整数$1$。表示在$[df{n}_i,n]$这个时间节段的每一个节点已经被征服了多少个点。

处理完$dfn$之后，我们对$1$到$n$的区间，每一个点都减去对应的时间。即第$i$个点减去$i$。

如果最后出现大于$0$的情况，则表示第$i$个点无法作为起点。

因此我们可以用线段树动态维护区间最大值，区间查询操作为加减，枚举每一个$i$作为起点时是否可行，直接统计答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[N], nxt[N];
vector<int>p(N);
struct segmenttree
{struct node{int l, r, maxx, tag;};vector<node>tree;segmenttree(): tree(1) {}segmenttree(int n): tree(n * 4 + 1) {}void pushup(int u){auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];root.maxx = max(left.maxx, right.maxx);}void pushdown(int u){auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];if (root.tag != 0){left.tag += root.tag;right.tag += root.tag;left.maxx = left.maxx + root.tag;right.maxx = right.maxx + root.tag;root.tag = 0;}}void build(int u, int l, int r){auto &root = tree[u];root = {l, r};if (l == r){root.maxx = -p[r];}else{int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}}void modify(int u, int l, int r, int val){auto &root = tree[u];if (root.l >= l && root.r <= r){root.maxx += val;root.tag += val;return;}pushdown(u);int mid = root.l + root.r >> 1;if (l <= mid) modify(u << 1, l, r, val);if (r > mid) modify(u << 1 | 1, l, r, val);pushup(u);}int query(int u, int l, int r){auto &root = tree[u];if (root.l >= l && root.r <= r){return root.maxx;}pushdown(u);int mid = root.l + root.r >> 1;int res = -inf;if (l <= mid) res = query(u << 1, l, r);if (r > mid) res = max(res, query(u << 1 | 1, l, r));return res;}
};
void init()
{iota(p.begin(), p.end(), 0);
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}segmenttree smt(n);smt.build(1, 1, n);nxt[n] = a[n];for (int i = n - 1; i >= 1; i--){nxt[i] = min(nxt[i + 1], a[i]);}for (int i = 1; i <= n; i++){smt.modify(1, nxt[i], n, 1);}int ans = 0, last = inf;for (int i = 1; i <= n; i++){smt.modify(1, nxt[i], n, -1);smt.modify(1, 1, n, 1);if (smt.query(1, 1, n) <= 0) ans++;smt.modify(1, 1, n, -1);last = min(last, a[i]);smt.modify(1, last, n, 1);}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;init();for (int i = 1; i <= test; i++){solve();}return 0;
}

E题

思路

统计每一个节点所能到达的最大深度。

枚举以第$i$层为结果计算答案，则第$i$层的答案为深度$>i$的节点的个数$+$最大深度$<i$的节点的个数。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
int depth[N], maxdeep[N], cnt[N], pre[N];
vector<int> mp[N];
void dfs(int u, int fu, int deep)
{depth[u] = deep;maxdeep[u] = deep;cnt[deep]++;for (int j : mp[u]){if (j == fu) continue;dfs(j, u, deep + 1);maxdeep[u] = max(maxdeep[u], maxdeep[j]);}
}
void solve()
{cin >> n;for (int i = 0; i <= n; i++){depth[i] = maxdeep[i] = cnt[i] = pre[i] = 0;mp[i].clear();}for (int i = 1, u, v; i < n; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dfs(1, -1, 1);for (int i = 1; i <= n; i++){pre[maxdeep[i]]++;cnt[i] += cnt[i - 1];}int ans = inf;for (int i = 1; i <= n; i++){pre[i] += pre[i - 1];ans = min(ans, pre[i - 1] + n - cnt[i]);}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}