目录
写在前面
比赛地址：https://codeforces.com/contest/2031
退役？
累了。
妈的明天体测测完直接飞昆明感觉要爆了、、、
A 签到
保证给定序列不升，要求修改到不降，则将所有元素修改至相等一定是不劣的。则答案即 \(n - \max\limits_{x\in \{h_i\}} \operatorname{cnt}_x\)。
//
/*
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;
std::vector<int> h(n + 1);
std::map<int, int> mp;
for (int i = 1; i <= n; ++ i) std::cin >> h[i], mp[h[i]] ++;
int ans = n;
for (auto [x, y]: mp) {
ans = std::min(ans, n - y);
}
std::cout << ans << "\n";
}
return 0;
}
B 结论，枚举
手玩下容易发现对于有序的排列，将两个相邻元素交换之后，其他位置均不能再与它们进行交换，即每个数至多参与交换一次。
于是考虑对于给定排列顺序枚举，并贪心地进行修改，检查最后是否有序即可。
//
/*
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;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++ i) std::cin >> a[i];
for (int i = 1; i < n; ++ i) {
if (a[i] != i && abs(a[i] - a[i + 1]) <= 1) std::swap(a[i], a[i + 1]);
}
int flag = 0;
for (int i = 1; i <= n; ++ i) if (a[i] != i) flag = 1;
std::cout << (flag ? "NO" : "YES") << "\n";
}
return 0;
}
C 构造，数学
1 为平方数，则 \(n\) 为偶数的构造是显然的，仅需不断在数列尾部添加两个相同元素即可。
\(n\) 为奇数，则至少有一种元素出现了至少三次。设其中三个出现位置为 \(x, y, z(x<y<z)\)，则一定有 \((y-x)^2 + (z - y)^2 = (z - x)^2\)，即三段距离是一组勾股数。考虑到最小的一组勾股数为 3、4、5，则可知 \(n\) 为奇数时，当 \(n< 5^2 + 1 = 26\) 时一定无解。
考虑能否在上述勾股数基础上，在空白区域加上偶数的构造基础上构造出 \(n=27\) 的答案，发现是可以的，仅需构造成如下形式：
- 位置 1：
1； - 位置 2~9：套用偶数构造；
- 位置 10：
1； - 位置 11~22：套用偶数构造；
- 位置 23~27：
2 3 3 1 2。
对于 \(n>27\) 的答案，仅需再在数列尾部套用偶数的构造即可。
//
/*
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;
if (n % 2 == 0) {
for (int i = 1, j = 1; i <= n; i += 2, ++ j) std::cout << j << " " << j << " ";
std::cout << "\n";
} else if (n < 27) {
std::cout << -1 << "\n";
} else {
std::cout << 1 << " ";
int j = 2;
for (int i = 2; i <= 9; i += 2, ++ j) std::cout << j << " " << j << " ";
std::cout << 1 << " ";
for (int i = 11; i <= 22; i += 2, ++ j) std::cout << j << " " << j << " ";
std::cout << j << " " << j + 1 << " " << j + 1 << " " << 1 << " " << j << " ";
j += 2;
for (int i = 28; i <= n; i += 2, ++ j) std::cout << j << " " << j << " ";
std::cout << "\n";
}
}
return 0;
}
D 枚举，数据结构
根据题意可知，显然答案是单调不降的，在全局最大值之后的所有位置的答案，一定可以取到全局最大值。
考虑求前缀最大值 \(\operatorname{pre}\)，则对于每个起点 \(i\)，最优的策略一定是先跳到 \(\operatorname{pre}_i\) 上，然后可以向后跳到任意比 \(\operatorname{pre}_i\) 小的位置上，并取这些位置为起点的答案的最大值。
于是考虑倒序枚举所有位置 \(i\) 并维护答案，在此过程中使用树状数组维护：对于后缀 \(i\sim n\)，跳到对应大小的位置后，可以取到的答案的最大值的前缀最大值。然后模拟上述过程，使用树状数组维护即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
namespace bit {
#define lowbit(x) ((x)&(-x))
const int kNode = 5e5 + 10;
int lim, t[kNode];
void init(int n_) {
lim = n_;
for (int i = 1; i <= lim; ++ i) t[i] = 0;
}
void insert(int p_, int val_) {
for (int i = p_; i <= lim; i += lowbit(i)) {
t[i] = std::max(t[i], val_);
}
}
int query(int p_) {
int ret = 0;
for (int i = p_; i; i -= lowbit(i)) {
ret = std::max(ret, t[i]);
}
return ret;
}
}
//=============================================================
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;
std::vector<int> a(n + 1), premax(n + 1), ans(n + 1);
bit::init(n);
premax[0] = 0;
for (int i = 1; i <= n; ++ i) std::cin >> a[i], premax[i] = std::max(premax[i - 1], a[i]);
for (int i = n; i; -- i) {
ans[i] = premax[i];
ans[i] = std::max(ans[i], bit::query(premax[i] - 1));
bit::insert(a[i], ans[i]);
}
for (int i = 1; i <= n; ++ i) std::cout << ans[i] << " ";
std::cout << "\n";
}
return 0;
}
更细致地观察后，可以发现答案分成的若干段，满足：
- 每一段答案递增；
- 每一段的答案为该段第一个位置的值，也即该段的最大值；
- 每个位置的答案不小于前缀最大值；
- 每一段内的最大值，小于后面所有段的最小值（即后缀最小值）。
于是同样考虑倒序枚举所有位置并确定答案。若该位置对应的前缀最大值大于后缀最小值，则可取下一段的答案，否则需要新开一段，答案为前缀最大值。
总时间复杂度 \(O(n)\) 级别。
//
/*
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;
std::vector<int> a(n + 1), premax(n + 1), sufmin(n + 2), ans(n + 1);
premax[0] = 0, sufmin[n + 1] = n + 1;
for (int i = 1; i <= n; ++ i) std::cin >> a[i], premax[i] = std::max(premax[i - 1], a[i]);
for (int i = n; i; -- i) sufmin[i] = std::min(sufmin[i + 1], a[i]);
for (int i = n, nowans = premax[i]; i; -- i) {
if (premax[i] <= sufmin[i + 1]) nowans = premax[i];
ans[i] = nowans;
}
for (int i = 1; i <= n; ++ i) std::cout << ans[i] << " ";
std::cout << "\n";
}
return 0;
}
E dfs，树形 DP，构造
记 \(f_{u}\) 表示原树的以 \(u\) 为根的子树需要深度至少为多少的二叉树才可得到，显然可以递归建树，将子节点对应的二叉树合并后得到父节点对应的二叉树。
考虑对于节点 \(u\)，将其所有子节点 \(v\) 对应二叉树按照 \(f\) 的大小升序进行合并。对于所有大小为 \(f\) 的二叉树，记其数量为 \(\operatorname{cnt}_f\) 显然需要合并成 \(\left\lceil\frac{\operatorname{cnt}_f}{2}\right\rceil\) 个大小为 \(f+1\) 的子树——不断进行上述过程直至只剩一种二叉树 \(f'\)，且 \(\operatorname{cnt}_f'\le 2\)，则有 \(f_u = f' + 1\)。
因为合并后二叉树的数量为上取整，当 \(\operatorname{cnt}=1\) 时合并后数量不减少，则上述过程不能直接暴力进行。考虑合并时每次枚举当前二叉树大小的最小值与次小值，并计算最小值合并得到次小值的数量，直至合并至最大值，再计算最后合并得到的大小即可，这样可以保证总合并次数为 \(O(n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 100;
//=============================================================
int n, fa[kN], need[kN];
int nowtime, tim[kN], mp[kN];
std::vector<int> sons[kN];
std::set<int> q;
//=============================================================
void clear() {
++ nowtime;
}
void add(int x_, int val_) {
if (tim[x_] != nowtime) tim[x_] = nowtime, mp[x_] = 0;
mp[x_] += val_;
}
int get(int x_) {
if (tim[x_] != nowtime) tim[x_] = nowtime, mp[x_] = 0;
return mp[x_];
}
void dfs(int u_) {
for (auto v_: sons[u_]) dfs(v_);
q.clear(), clear();
for (auto v_: sons[u_]) {
q.insert(need[v_]);
add(need[v_], 1);
}
while (!q.empty()) {
int t = *q.begin();
if ((int) q.size() == 1) {
need[u_] = t + 1;
if (get(t) > 2) need[u_] += (int) (ceil(log2(1.0 * get(t))) - 1);
break;
}
q.erase(t);
int t1 = *q.begin();
if (t1 - t >= 20) add(t1, 1);
else add(t1, (get(t) + ((1 << (t1 - t)) - 1)) / (1 << (t1 - t)));
}
}
//=============================================================
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) sons[i].clear(), need[i] = 0;
for (int i = 2; i <= n; ++ i) {
std::cin >> fa[i];
sons[fa[i]].push_back(i);
}
dfs(1);
std::cout << need[1] << "\n";
}
return 0;
}
写在最后
学到了什么：
- D：多观察呃呃，别惦记你那 b 数据结构了；
- E：注意均摊时间复杂度。