2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site

news/发布时间2024/5/20 2:19:33

目录
  • 写在前面
  • I
  • B
  • K
  • F
  • M
  • E
  • D
  • C
  • 写在最后

写在前面

补题地址：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 大神磕四个四题全是大神出的我纯拖后腿的飞舞一个。

撒由那拉！

参考：

  • 连续数字异或和 - Mychael - 博客园
  • 2024 ICPC National Invitational Collegiate Programming Contest - 知乎

  1. https://oi-wiki.org/math/young-tableau/ ↩︎

  2. https://www.cnblogs.com/rainycolor/p/18080157 ↩︎

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ulsteruni.cn/article/08426523.html

如若内容造成侵权/违法违规/事实不符，请联系编程大学网进行投诉反馈email:xxxxxxxx@qq.com，一经查实，立即删除！

相关文章

会充电的CANoe-赋能新能源汽车，高效完成即插即充（PnC）智能充电功能测试

会充电的CANoe-赋能新能源汽车，高效完成即插即充（PnC）智能充电功能测试

ISO 15118-2标准中描述的PnC功能，可以实现插枪即充电，识别、计费信息、充电参数都通过高级别通信在EV和EVSE之间自动交换。简化了电动汽车的充电过程，提高了用户体验，为电动汽车行业带来了更智能、更便捷的充电解决方案。然而，电动汽车和充电站之间要实现自动通信和计费，…
阅读更多...
Nginx负载均衡、动静分离Tomcat案例实战

Nginx负载均衡、动静分离Tomcat案例实战

一、前言 1）Tomcat是一款开源的、免费的WEB软件服务器，是隶属于Apache基金会旗下的，主要是用于去发布网站代码、提供网页信息服务的。用户通过浏览器可以实现网站页面的访问。 2）Tomcat WEB软件默认可以处理静态网页（Apache、Nginx），同时也可以处理动态网页，主要是处理…
阅读更多...
dotnet 9 WPF 支持 Style 的 Setter 填充内容时可忽略 Value 标签

dotnet 9 WPF 支持 Style 的 Setter 填充内容时可忽略 Value 标签

本文记录 WPF 在 dotnet 9 的一项 XAML 编写语法改进点，此改进点用于解决编写 Style 的 Setter 进行给 Value 赋值时，不能将 Value 当成默认内容，需要多写 Value 标签的问题。通过此改进点可减少两行 XAML 代码在原先的 WPF 版本里面，对 Style 的 Setter 填充复杂的对象内容…
阅读更多...
WDS+MDT网络启动自动部署windows（十七）MDT中文变量，描述，组织单位OU

WDS+MDT网络启动自动部署windows（十七）MDT中文变量，描述，组织单位OU

简介 这简直就是歧视，在MDT使用变量时，数据库设置时，居然不能用中文。 计算机描述，我将在数据库中设置为使用人，主要是其他地方也不方便看。 描述是存在注册表中的，未来自动化也将会使用使用人这个字段，用来注册OCS这样，有标签，使用人字段的软件。 方向 解决MDT/BDD无…
阅读更多...
WDS+MDT网络启动自动部署windows（十六）计算机自动进入指定OU

WDS+MDT网络启动自动部署windows（十六）计算机自动进入指定OU

简介 新装计算机总是在默认电脑，不方便配置终端计算机策略权限。 要想办法让MDT装好的计算机，自动进入指定组织单位OU。 dsquery 大概意思是 domain server query ，就是域服务器搜索的意思。 在域控执行 dsquery ou 先看看OU是怎么用LDAP表示的。 从左到右，OU，逐级的组…
阅读更多...
OpenVX技术图例（二）

OpenVX技术图例（二）

OpenVX技术图例（二） 参考文献链接 https://software-dl.ti.com/jacinto7/esd/processor-sdk-rtos-jacinto7/latest/exports/docs/tiovx/docs/user_guide/index.html人工智能芯片与自动驾驶
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023