目录
写在前面
比赛地址：https://codeforces.com/contest/1954
本来有机会上大分但是唐了 E 没调出来呃呃。
小号比大号分高了呃呃以后想休闲直接打大号了哈哈
A
数学。
若要将 \(n\) 个位置全部涂成颜色 \(i\)，则一定要修改 \(n - \operatorname{count}(i)\) 次。
则一个显然想法是最小化 \(\max_{1\le i\le m} \operatorname{count}(i)\)，由鸽巢原理可知 \(\max_{1\le i\le m} \operatorname{count}(i) = \left\lceil \frac{n}{m} \right\rceil\)。
则当且仅当 \(k < n - \left\lceil \frac{n}{m} \right\rceil\) 输出 YES，否则 NO。
//
/*
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, m, k; std::cin >> n >> m >> k;
std::cout << ((k < n - ceil(1.0 * n / m)) ? "YES" : "NO") << "\n";
}
return 0;
}
B
枚举。
手玩下发现有解当且仅当原 beatuiful 数列所有位置并不全相等，且由性质可知，此时数列一定满足：
- 修改为全部相等数列后，所有位置均为 \(a_1\)。
- 不存在两个连续的不等于 \(a_1\) 的位置。
记所有非 \(a_1\) 的位置为 \(p_1, p_2, \cdots, p_k\)，则将数量修改为非 beautiful 有两种方案：
- 将 \(p_i\) 调整到数列首或数列尾。
- 调整使得两个 \(p_i\) 相邻。
考虑记 \(p_0 = 0\)，\(p_{k + 1} = n + 1\)，则答案即为：
\[\min_{1\le i\le k + 1} \left(p_{i} - p_{i - 1} - 1\right) \]//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, 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;
std::vector<int> pos;
pos.push_back(0);
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
if (a[i] != a[1]) pos.push_back(i);
}
pos.push_back(n + 1);
if (pos.size() == 2) {
std::cout << -1 << "\n";
} else {
int ans = n;
for (int i = 1, sz = pos.size(); i < sz; ++ i) {
ans = std::min(ans, pos[i] - pos[i - 1] - 1);
}
std::cout << ans << "\n";
}
}
return 0;
}
/*
1
8
1 1 2 1 2 1 1 1
*/
C
数学，贪心。
考虑有这样两个数：
\[\begin{cases} x = \sum\limits_{i = 1}^{n} 10^{n - i}\times x_i \\ y = \sum\limits_{i = 1}^{n} 10^{n - i}\times y_i \end{cases}\]考虑拆一下多项式乘法，则有：
\[\begin{aligned} x \times y &= \left(10^{n - 1} \times x_1 + \sum\limits_{i = 2}^{n} 10^{n - i}\times x_i\right) \times \left(10^{n - 1} \times y_1 + \sum\limits_{i = 2}^{n} 10^{n - i}\times y_i \right)\\ &= 10^{2n - 2}\times x_1 y_1 + 10^{n - 1} \times \sum\limits_{i = 2}^{n} 10^{n - i}\times (y_1 x_i + x_1 y_i) + \left(\sum\limits_{i = 2}^{n} 10^{n - i}\times x_i\right)\times \left(\sum\limits_{i = 2}^{n} 10^{n - i}\times y_i\right) \end{aligned}\]发现上式中第一项不受修改影响，因为有与指数相乘的原因，第二项的影响比第三项大得多，于是仅需考虑按照位数递减，最大化第二项的影响即可。
于是一个显然的想法是从高到低枚举各位 \(i(1\le i\le n)\)，找到第一个 \(x_i \not= y_i\) 的位置 \(i\)。记第 \(i\) 位较大的数为 \(A\)，另一个数为 \(B\)，由上式可知为了最大化 \((y_1x_i + x_1y_i)\) 仅需调整使得 \(j>i\) 各位 \(j\) 中满足 \(B_j > A_j\) 即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 110;
//=============================================================
std::string x, y;
bool tag[kN];
//=============================================================
void modify(int pos_, int len_, std::string &s_, std::string &t_) {
for (int i = pos_; i < len_; ++ i) {
if (s_[i] > t_[i]) {
std::swap(s_[i], t_[i]);
}
}
}
//=============================================================
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 >> x >> y;
for (int i = 0, len = x.length(); i < len; ++ i) tag[i] = 0;
for (int i = 0, len = x.length(); i < len; ++ i) {
if (x[i] == y[i]) continue;
else if (x[i] > y[i]) modify(i + 1, len, x, y);
else modify(i + 1, len, y, x);
break;
}
std::cout << x << "\n" << y << "\n";
}
return 0;
}
D
数学，DP。
妈的真有用到同一个结论的题啊哈哈
考虑对于一组选出的球 \(b_1, b_2, \cdots b_{m}\) 应如何分组才可令分组数量最少。
- 发现若无法令各组均为 2，则剩下的球一定为数量最多的一种。
- 则一种最优的分配方案是每次选出数量最多的一种，与数量最少的一种，然后从中各选出一个配成一组。
这个分配方式怎么这么熟悉？翻了下刚打的湖南多校发现有道还更强的题：https://codeforces.com/gym/512144/problem/C，要求将 \(n\) 种颜色的物品按每组 \(k\) 个分组，则有结论最少分组数为：
\[\max\left( \max {b_i}, \left\lceil \dfrac{\sum b_i}{k} \right\rceil\right) \]在本题中 \(k=2\)。
则若已知选择的所有球中数量最多的球的数量，再考虑球的总数即可求得最少分组数。发现题目给定额外性质：\(\sum a_i \le 5000\)，球的总数很少，于是考虑直接大力枚举 \(\max b_i\)，再大力枚举球的个数，并考虑有多少种方案选出满足条件的一组球。
于是先将 \(a\) 升序排序，然后考虑 DP，记 \(f_{i, j}\) 表示从升序排序后的 \(a_1\sim a_n\)，选出满足 \(\sum b_i = j\) 的子序列 \(b\) 的方案数，\(g_i\) 表示钦定选出的最大数量的球为 \(i\) 的对答案的贡献。初始化 \(f_{0, 0} = 1\)，则有：
\[\begin{aligned} &\forall 1\le i\le n, a_i\le j,\ f_{i, j} = f_{i - 1, j - a_i}\\ &\forall 1\le i\le n,\ g_{i} = \sum_{a_i\le j} f_{i, j}\times \max\left( a_i, \left\lceil \dfrac{j}{2} \right\rceil\right) \end{aligned}\]答案即为 \(\sum_{1\le i\le n} g_i\)。
发现这个式子太背包了，套路地滚动数组即可。总时间复杂度 \(O(n\times \sum a_i)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5010;
const LL p = 998244353;
//=============================================================
int n, s, a[kN];
LL ans, sum[kN];
//=============================================================
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
s += a[i];
}
sum[0] = 1;
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++ i) {
for (int j = s; j >= a[i]; -- j) {
LL size = std::max(1ll * a[i], (LL)ceil(1.0 * j / 2.0));
LL delta = sum[j - a[i]] * size % p;
ans = (ans + delta) % p;
sum[j] = (sum[j] + sum[j - a[i]]) % p;
}
// std::cout << ans << "---\n";
}
std::cout << ans << "\n";
return 0;
}
E
枚举，数据结构。
唉场上实现拉了没做出来亏死。
手玩发现每次操作后数列的变化形式如下：
- 进行若干次操作后，某些位置变为非正，数列被分为若干独立的子区间。
- 对每个子区间独立地重复上述操作。
发现操作的顺序是无所谓的，甚至操作的对象也是无所谓的，因为每次操作会影响整个极大区间，可以保证每次合法的操作都是有贡献的。
于是考虑每轮按顺序枚举当前所有区间，然后对当前所有区间仅进行一次操作。发现当第 \(i\) 轮操作结束时，当前所有区间一定为满足 \(a_j> k\times i\) 的极大区间。考虑记满足 \(a_j > m\) 的所有极大区间数量为 \(\operatorname{count}(m)\)，则对于某个确定的 \(k\)，答案可以形式化地表示为：
\[\sum_{1\le k\times i < \max a} \operatorname{count}(k\times i) \]发现上式是一个调和级数的形式，可以 \(O(v\ln v)\) 地枚举所有有贡献的项，仅需考虑如何快速预处理 \(\operatorname{count}\)。考虑通过按权值递减不断地向数列中加数，在此过程中维护有多少个极大区间 \(c\)。如当前插入到权值为 \(v\) 的位置 \(p\)，考虑加入 \(p\) 后会使得区间数量增加，还是会合并当前某些区间导致区间数量减少：
- 首先令 \(c:= c+ 1\)。
- 检查数列中 \(p\) 的前驱 \(\operatorname{pre}_p\)：若 \(\operatorname{pre}_p = p - 1\) 或不存在则令 \(c:=c - 1\)。
- 检查数列中后继 \(\operatorname{next_p}\)：若 \(\operatorname{next}_p = p + 1\) 或不存在则令 \(c:=c - 1\)。
上述过程可直接使用 set 维护，预处理后再调和级数地枚举贡献并求得答案即可。则总时间复杂度 \(O(v\ln n + v\ln v)\) 级别，其中 \(v = \max a_i\)。
注意为了防止 RE，必须先在 set 中插入极小极大值。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, maxa, a[kN];
std::vector <int> pos[kN];
std::set<int> s;
LL nowcnt, cnt[kN], ans[kN];
//=============================================================
void init() {
s.insert(-kN);
s.insert(kN);
}
void insert(int pos_) {
++ nowcnt;
std::set<int>::iterator next = s.upper_bound(pos_);
std::set<int>::iterator pre = std::prev(next);
if ((*pre) == pos_ - 1) -- nowcnt;
if ((*next) == pos_ + 1) -- nowcnt;
s.insert(pos_);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
maxa = std::max(maxa, a[i]);
pos[a[i]].push_back(i);
}
init();
for (int i = maxa; i; -- i) {
for (auto p: pos[i]) insert(p);
cnt[i] = nowcnt;
}
// for (int i = 1; i <= maxa; ++ i) std::cout << cnt[i] << " ";
for (int i = maxa; i; -- i) {
for (int j = 0; i * j < maxa; ++ j) {
ans[i] += 1ll * cnt[i * j + 1];
}
}
for (int i = 1; i <= maxa; ++ i) std::cout << ans[i] << " ";
return 0;
}
F
咕咕~
写在最后
学到了什么：
- D：真能做到原啊草
- E：
set查询元素，求前驱后继，可用于添加数列元素过程中区间合并。为了防止 RE 必须先在set中插入极小极大值。