目录
写在前面
比赛地址：https://codeforces.com/contest/2019。
唉唉不敢打 div1 只敢开小号打 div2 太菜了。
A 签到
显然最优方案只有两种——取所有奇数位置或所有偶数位置。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n; std::cin >> n;
int cnt[2] = {0}, sum[2] = {0};
for (int i = 1; i <= n; ++ i) {
int x; std::cin >> x;
++ cnt[i % 2];
sum[i % 2] = std::max(sum[i % 2], x);
}
std::cout << std::max(cnt[0] + sum[0], cnt[1] + sum[1]) << "\n";
}
return 0;
}
B 排序，模拟
发现对于每个点，以及两点间的区间，仅需考虑两边分别有多少点即可就算出它们被多少线段覆盖。
则覆盖线段数不同的区间（单点也算）仅有 \(2n\) 级别，枚举这些区间并计算线段数量，然后使用 map 维护即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, q, x[kN];
LL cnt[kN];
std::map <LL, int> ans;
//=============================================================
LL query(LL k_) {
return ans[k_];
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> q;
for (int i = 1; i <= n; ++ i) std::cin >> x[i];
ans.clear();
for (int i = 1; i <= n; ++ i) {
cnt[i] = 1ll * i * (n - i + 1) - 1;
++ ans[cnt[i]];
}
for (int i = 1; i < n; ++ i) {
int l = x[i] + 1, r = x[i + 1] - 1;
LL sum = 1ll * i * (n - i);
ans[sum] += r - l + 1;
}
while (q --) {
LL k; std::cin >> k;
std::cout << query(k) << " ";
}
std::cout << "\n";
}
return 0;
}
/*
1
6 15
1 2 3 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
*/
C 数学，贪心
我去怎么还有一个结论在三个题里出现的。
发现 \(\sum n\le 10^5\)，考虑枚举每组的物品数量上限 \(c\)，并检查将已有物品按照该限制至少分多少组 \(M\)，则可求出补齐 \(M\) 组所需的最少的额外数量，然后再不断加整组即可。
那么至少分多少组呢？考虑经典结论：要求将 \(n\) 种颜色的物品按每组上限 \(c\) 个分组，保证每组内所有物品颜色不同，则有结论最少分组数为：
\[M = \max\left( \max {b_i}, \left\lceil \dfrac{\sum b_i}{c} \right\rceil\right) \]则补齐 \(M\) 组所需的最少的额外数量为：
\[c\times M - \sum a_i \]则仅需检查可额外加入的数量 \(k\) 的合法性，并求得还可以加多少整组即可，总时间复杂度 \(O(n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n;
LL k, a[kN];
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> k;
LL maxa = 0, suma = 0;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
maxa = std::max(maxa, a[i]);
suma += a[i];
}
LL ans = 1;
for (LL i = 2; i <= n; ++ i) {
LL mins = std::max(maxa, 1ll * (suma + i - 1) / i);
LL mincnt = i * mins;
if (mincnt > suma + k) continue;
ans = i;
}
std::cout << ans << "\n";
}
return 0;
}
D 模拟，思维
对上电波就比较好做的题。
先考虑对于每个起点 \(i\)，依次检查到时间 \(j\) 时是否合法。此时仅需要考虑 \(a_i \le j\) 的位置的限制，设这些位置中最靠左/右的位置分别为 \(L_i, R_i\)，则 \(i\) 合法当且仅当对于所有时间 \(j\)，有 \(|i - L_j| \le j\) 且 \(|i - R_j|\le j\)，即保证从 \(i\) 出发能到达所有 \(a_i \le j\) 的位置。
更进一步地，发现上述限制即限制了 \(i\) 与所有 \(L_i, R_i\) 距离的上界。则发现对于每个时刻 \(j\)，合法的 \(i\) 一定构成一段连续的区间，且这个区间一定是单调缩小的，于是每次时间增加时，更新 \(L_j, R_j\) 后大力检查上述区间端点作为起点是否合法即可。
总时间复杂度 \(O(n)\) 级别。
呃呃我赛时写的很丑很丑
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN], L[kN], R[kN];
std::vector<int> pos[kN];
int ansl, ansr;
//=============================================================
bool check1(int time1_, int time2_, int l_, int r_, int newl_, int newr_) {
if (time1_ == 0) {
return newr_ - newl_ + 1 <= time2_;
}
if (l_ <= newl_ && newr_ <= r_) return true;
int d1 = std::max(0, l_ - newl_);
int d2 = std::max(0, newr_ - r_);
return time2_ - std::min(r_ - l_ + 1, time1_) >= d1 + d2;
}
void check2(int time_, int l_, int r_) {
for (int i = ansl; i <= ansr; ++ i) {
if (l_ <= i && i <= r_) break;
if (i > r_) {
if (i - l_ + 1 > time_) ansl = ansr + 1;
break;
}
if (i < l_ && r_ - i + 1 <= time_) break;
++ ansl;
}
for (int i = ansr; i >= ansl; -- i) {
if (l_ <= i && i <= r_) break;
if (i < l_) {
if (r_ - i + 1 > time_) ansr = ansl - 1;
break;
}
if (i > r_ && i - l_ + 1 <= time_) break;
-- ansr;
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
for (int i = 1; i <= n; ++ i) pos[i].clear();
for (int i = 1; i <= n; ++ i) std::cin >> a[i], pos[a[i]].push_back(i);
int time = 0, l = n + 1, r = 0, yes = 1;
for (int i = 1; i <= n; ++ i) {
if (!pos[i].size()) continue;
yes &= check1(time, i, l, r, pos[i].front(), pos[i].back());
if (!yes) break;
time = i;
l = std::min(l, pos[i].front());
r = std::max(r, pos[i].back());
L[i] = l, R[i] = r;
}
if (!yes) {
std::cout << 0 << "\n";
continue;
}
ansl = 1, ansr = n;
for (int i = 1; i <= n; ++ i) {
if (pos[i].size()) check2(i, L[i], R[i]);
}
std::cout << std::max(0, ansr - ansl + 1) << "\n";
}
return 0;
}
/*
1
6
6 6 6 6 6 5
*/
E 树，贪心，暴力 or 长链剖分
显然若最终答案的叶节点均属于某层，则原树中该层的节点均可以保留。更进一步地可以发现，此时最终答案等价于选择该层所有节点到根的链建立的虚树。
一个显然的做法是从根节点开始按层 bfs，每次通过当前层的节点构造下一层。则仅需考察当前层节点 \(u\) 是否有子节点：
- 若有子节点，则子节点均属于下一层，直接枚举并加入即可；
- 否则，应当删除从当前节点到某个祖先节点的一条链，直至祖先节点仍有子节点在虚树中。
发现每个节点仅会被加入一次被删除一次，则可以在上述删除过程中直接暴力上跳。于是考虑在上述 bfs 过程中，维护每个节点有多少子节点还在虚树中，在暴力上跳过程中若将父节点所有子节点删完，则继续上跳即可。
当然也可以不暴力上跳，而是通过类似长链剖分的预处理，来减去上述被删掉的部分的贡献，详见其它题解。
总时间复杂度 \(O(n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int n, ans, maxdep, dep[kN], fa[kN];
std::vector<int> edge[kN], son[kN];
int cntson[kN];
//=============================================================
void dfs(int u_, int fa_) {
fa[u_] = fa_;
dep[u_] = dep[fa_] + 1;
maxdep = std::max(maxdep, dep[u_]);
for (auto v_: edge[u_]) {
if (v_ == fa_) continue;
son[u_].push_back(v_);
dfs(v_, u_);
}
}
void bfs() {
int sum = 1, now = 0;
std::vector<int> node[2];
node[0].push_back(1);
for (int i = 1; i < maxdep; ++ i) {
node[now ^ 1].clear();
for (auto u: node[now]) {
if (son[u].empty()) {
for (int p = u; p; p = fa[p]) {
-- sum, -- cntson[fa[p]];
if (cntson[fa[p]] > 0) break;
}
} else {
for (auto v: son[u])
node[now ^ 1].push_back(v), ++ sum;
cntson[u] = son[u].size();
}
}
ans = std::min(ans, n - sum);
now ^= 1;
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
maxdep = 0;
for (int i = 1; i <= n; ++ i) {
edge[i].clear(), son[i].clear();
dep[i] = cntson[i] = 0;
}
for (int i = 1; i < n; ++ i) {
int u, v; std::cin >> u >> v;
edge[u].push_back(v), edge[v].push_back(u);
}
dfs(1, 0);
ans = n - 1;
bfs();
std::cout << ans << "\n";
}
return 0;
}
F 贪心，枚举
写在最后
唉唉 AK div2 失败太菜了。
学到了什么：
- C：经典结论；
- D：考虑单个位置的合法性，然后根据性质考虑所有合法位置构成的集合的顺序；
- F：考虑调整法，证明选择某个元素在答案里一定不会更劣、