目录
写在前面
补题地址：https://codeforces.com/gym/105143
正式赛全程犯大病打铜了呃呃，以下按个人向难度排序。
AIEEEEE！忍者为何！队长=san 实际战犯！罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罪罚罚罪罚罪罚罪罚罪罚罪罚罪罚
南无阿弥陀佛……不由得土下座……只得切断谢罪！庸碌大半生，邀请赛取我性命，再无意难平。撒由那拉！
「2024·ICPC·National·Invitational·Collegiate·Programming·Contest, Wuhan·Site 电子狂言俳句乱舞·殒命珞珈山上」#1 完
I
签到。
场上 dztle 大神一眼秒了。
首先忽略初始时就位于原串最右侧的 1。
发现最优的策略是每次将不位于字符串最右侧的、最右侧的连续一段 1 调整到字符串最右侧，于是仅需统计此时字符串中有多少段连续的 1 即可。
//
/*
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);
std::string s; std::cin >> s;
while (s.back() == '1') s.pop_back();
int cnt = 0;
for (int i = 0, lst = -2, len = s.length(); i < len; ++ i) {
if (s[i] == '1') {
if (lst != i - 1) ++ cnt;
lst = i;
}
}
std::cout << cnt;
return 0;
}
B
贪心。
赛时这题一直想怎么均分所有数想了一堆假做法挂了三发纯战犯。然后 dztle 看了一眼秒了，紫砂了。
首先发现 \(n\) 次操作实际上可以将整个数列调整成任意形态，于是仅需考虑如何分配 \(\sum a_i\) 得到最终答案的形态即可。
考虑枚举二进制位从高位向低位贪心，一个显然的想法是尽可能不让高位在答案中出现，于是考虑答案中是否可以不出现某位。
对于第 \(i(0\le i\le \log v)\) 位，若可以仅通过之后的若干位构造出 \(n\) 个和为 \(\sum a_i\) 的数，即满足 \(\sum a_i\le n\times (2^{i} - 1)\)，则该位是不必要的；否则必定有一个数该位为 1，则应尽可能地令所有数该位均为 1，从而减少使用之后若干位构造的负担。
按照上述思路贪心地分配即可。
//
/*
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 n; std::cin >> n;
LL sum = 0, ans = 0;
for (int i = 1; i <= n; ++ i) {
int x; std::cin >> x;
sum += x;
}
for (LL i = 30; i >= 0; -- i) {
LL j = (1ll << i);
if (sum <= 1ll * n * (j - 1)) continue;
ans += j;
sum -= 1ll * std::min(1ll * n, sum / j) * j;
}
std::cout << ans;
return 0;
}
K
找规律。
打表题，场上替 dztle 大神打了个表大神一眼秒了，本场唯一的贡献。
发现有：
\[\bigoplus_{i=1}^{n} i = \begin{cases} n&(n\bmod 4 = 0)\\ 1 &(n\bmod 4 = 1)\\ n + 1 &(n\bmod 4 = 2)\\ 0&(n\bmod 4 = 3)\\ \end{cases}\]喜欢证明可以参考：https://www.cnblogs.com/Mychael/p/8633365.html
则当 \(n=0\) 时先手拿 \(n\) 必胜，\(n=1\) 时先手拿 \(1\) 必胜。
当 \(n=3\) 时先手无法操作必败，\(n=4\) 时先手无论如何操作，后手取走另一侧均会获胜，则先手必败。
//
/*
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);
// for (int i = 1, s = 0; i <= 100; ++ i) {
// s ^= i;
// std::cout << i << " " << s << "\n";
// }
int T; std::cin >> T;
while (T --) {
int n; std::cin >> n;
if (n % 4 == 0 || n % 4 == 1) std::cout << "Fluttershy\n";
else std::cout << "Pinkie Pie\n";
}
return 0;
}
F
交互，单调性。
这个矩阵的形态学名叫杨氏矩阵[1]，在算法作业上见过并且当时发现了下述结论[2]于是跟队友说了下，可能对场上出了本题有了一点贡献，本场唯 1.0001 的贡献。
发现对于某个权值 \(v\)，其在每一行的所有出现位置一定构成一段连续的区间。且其在第 \(i\) 行与第 \(i+1\) 行中出现的位置构成的区间 \([l_i, r_i], [l_{i + 1}, r_{i + 1}]\) 一定满足：
\[l_{i + 1}\le l_{i}\le r_{i + 1} \le r_{i} \]即有：
\[(l_{i + 1}\le l_i)\land (r_{i + 1}\le r_i) \]发现 \(l_1\sim l_n\) 和数列 \(r_{1}\sim r_n\) 均为非递减数列，构成了一个阶梯形，以该阶梯形为分界，左上为小于 \(v\) 的所有位置，右下为大于 \(v\) 的所有位置，则权值 \(v\) 的排名即为右下角位置的数量。
由阶梯形这个性质，求每种权值 \(v\) 的排名，可以考虑维护一个初始位于最后一行左侧的指针，倒序枚举每行，并维护指针使之指向第一个大于 \(v\) 的元素，即可统计每行有多少数大于 \(v\) 从而得到排名。发现该过程中指针仅会单调右移和上移 \(O(n)\) 次。
解决了对任意权值求排名的问题，仅需在外层加个二分答案枚举权值即可解决本题。值域为 \(O(n^2)\) 级别，则总时间复杂度 \(O(n\log n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
int n, k, ans;
//=============================================================
int query(int x_, int y_, int val_) {
std::cout << "? " << x_ << " " << y_ << " " << val_ << "\n";
std::cout.flush();
int ret; std::cin >> ret;
return ret;
}
bool check(int lim_) {
int s = 0;
for (int x = n, y = 1; x; -- x) {
while (y <= n && query(x, y, lim_) == 1) ++ y;
s += n - y + 1;
}
return s < k;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
// std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n >> k;
for (int l = 1, r = n * n; l <= r; ) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
std::cout << "! " << ans;
return 0;
}
M
贪心。
因为是字典序比较，于是仅需关注在当前数列中如何合成出最大的一个数。
发现每次合并都需要一个奇数和一个偶数并合成一个新的奇数，则考虑将所有偶数降序排序，枚举当前合成最大的数的最后一步中所需的偶数 \(x\)，检查能否合成出奇数 \(x + 1\) 或 \(x - 1\) 即可。显然，若无法得到这两个奇数，说明无法合成大于等于 \(2\times x - 1\) 的数，则偶数 \(x\) 一定不会参与之后的合并。
又发现合并得到一个数 \(v\) 所需的原数列中的数实际上可以递归求得，且个数至多为 \(O(\log v)\) 级别，于是可以考虑递归地检查能否得到某个数。具体地：
- 若原数列中存在 \(v\)，则合法。
- 否则若 \(v\) 为偶数或 \(v\) 为 1，则 \(v\) 无法被合成，非法。
- 否则若 \(v\) 为奇数，递归地检查能否同时得到 \(\left\lfloor\frac{v}{2}\right\rfloor\) 与 \(\left\lfloor\frac{v}{2}\right\rfloor + 1\) 即可。
特别注意上述第三条中的条件同时，即最终递归求得的所需的各种数的数量，不得大于原数列中对应数的数量。于是需要在上述过程中哈希表维护原数列中每种权值的出现次数，在上述检查过程中需要动态维护每个数出现次数，若检查失败需要还原哈希表。最后输出答案时仅需输出哈希表中所有元素即可。
偷懒写个 unordered_map，总时间复杂度 \(O(n\log v)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n;
std::unordered_map<LL, int> cnt;
std::vector<LL> even, modified, ans;
//=============================================================
int count(LL val_) {
if (!cnt.count(val_)) return 0;
return cnt[val_];
}
void add(LL val_) {
if (!cnt.count(val_)) cnt[val_] = 0;
++ cnt[val_];
}
void sub(LL val_) {
-- cnt[val_];
if (cnt[val_] == 0) cnt.erase(val_);
modified.push_back(val_);
}
bool get(LL val_) {
if (count(val_)) return sub(val_), true;
if (val_ == 1 || val_ % 2 == 0) return false;
return (get(val_ / 2ll) && get(val_ / 2ll + 1));
}
bool check(LL val_) {
modified.clear();
if (get(val_)) return true;
for (auto x: modified) add(x);
return false;
}
//=============================================================
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) {
LL a; std::cin >> a;
if (a % 2 == 0) even.push_back(a);
add(a);
}
std::sort(even.begin(), even.end(), std::greater<LL>());
for (auto x: even) {
if (!count(x)) continue;
sub(x);
if (check(x + 1)) {
add(2ll * x + 1);
} else if (check(x - 1)) {
add(2ll * x - 1);
} else {
add(x);
}
}
for (auto x: cnt) {
for (int i = 1; i <= x.second; ++ i) {
ans.push_back(x.first);
}
}
std::cout << ans.size() << "\n";
for (std::vector<LL>::reverse_iterator it = ans.rbegin(); it != ans.rend(); ++ it) {
std::cout << *it << " ";
}
return 0;
}
/*
4
1 1 2 2 4
*/
E
D
C
写在最后
给 dztle 大神磕四个四题全是大神出的我纯拖后腿的飞舞一个。
撒由那拉！
参考：