当前位置: 首页 > news >正文

201007

2024 ICPC Kunming E and 2024 ICPC Nanjing

ICPC Kunming

E

鉴定为啥都考察一点的杂交题。

这个题目的询问就像,我问测评机若干个式子,然后测评机告诉我这些式子的解,让我去解方程。

于是就暴力枚举所有可能的式子,能找到 \(n\) 和线性无关的式子就是 ok 的,否则就不 ok。

关于解这个线性方程,我是基于线性基来写的,这里只给出得到所有的方程后解方程的过程,判断解的存在性可以类似写:

constexpr int N = 250, L = 250;struct Node {std::bitset<L> u;int val;void set(int idx) {u.set(idx);}void setval(int v) {val = v;}Node &operator ^= (const Node &v) {u ^= v.u;this->val ^= v.val;return *this;}bool operator[] (int idx) {return u[idx];}bool any() {return u.any();}bool none() {return u.none();}void reset() {u.reset();}
} p[L + 5];int n, k;
std::vector<int> adj[N + 5];void reset() {for (int i = 0; i < n; ++i) {p[i] = Node();}
}bool insert(Node a) {for (int bit = n - 1; ~bit; --bit) {if (!a[bit]) {continue;}if (p[bit].any()) {a ^= p[bit];}else {for (int b = 0; b < bit; ++b) {if (a[b] && p[b].any()) {a ^= p[b];}}for (int b = bit; b < n; ++b) {if (p[b][bit]) {p[b] ^= a;}}p[bit] = a;return a.any();}}return false;
}std::vector<int> get(const std::vector<Node> &all) {reset();for (auto &ele : all) {insert(ele);}bool ok = true;for (int i = 0; i < n; ++i) {if (p[i].none()) {ok = false;break;}}std::vector<int> ret;for (int i = 1; i < n; ++i) {ret.emplace_back(p[i].val);}return ret;
}

这个题还要求找lca,直接沿着父节点往上,记录经过的点就可以。

总而言之这个题就是一坨,啥都要写一点

ICPC Nanjing

G

询问的限制就提示了二分。然后想到要在重心上做文章(以树的重心为根时, 所有子树的大小不超过整棵树的一半)。但实现起来是有细节的,这里说几个我踩过的坑:

  • 断开边确定新的连通块后要更新连通块的大小
  • 若与重心相邻的节点有 3 个,就不能随便选询问的点。当有三个点时(设为 \(x\) \(y\) \(z\) ),假设以 \(z\) 为根的子树是较大的,则我们不能保证 \(z\) 的子树大小加上重心这个点不超过整个连通块的一半,所以我们问 \(u\) \(v\) 就倒闭了。

B

一开始想无思路,但是队友说了一句“两个数能相消必须满足他们位置的奇偶性不相同”。那位置奇偶性不同的两个相同的数是否一定能相消呢?答案是能的。很显然最终状态必须满足相邻的数都不相同。那我们假设“最终状态存在位置奇偶性不同(设位置分别是\(l\)\(r\) 且不相邻)的两个相同的数没有相消”,则 \(l + 1\)\(r - 1\) 位置上的数必须和 \(l\)\(r\) 上的数相异,也就是说,\(l + 1\)\(r - 1\) 这两个位置上的数相同且未消掉,而且这两个位置的奇偶性也是相异的。同理这样递归下去,我们就会得到两个相邻的数相同,但是未被消去,这显然和最终状态是矛盾的。所以我们可以说“奇偶性不同的两个相同的数是否一定能相消”。

有了这个结论直接分奇偶统计不同数的数量然后贪心就好了。

C

弃疗了

明明之前还写过题解的,还是越打越菜了

http://www.hskmm.com/?act=detail&tid=26367

相关文章:

  • 苍穹外卖第一天(Maven、Git、Nginx反向代理)
  • Python中的数据结构
  • 2025家纺摄影公司/南通摄影公司权威推荐榜:创意拍摄与专业服务的口碑之选
  • 合成数据生成技术研讨会深度解析
  • 纯 C++ 开发的 Telegram Bot 框架
  • 六级自测
  • Python 中的链式操作——重点讲解链式调用
  • io设备概述
  • 多元线性回归-梯度下降法-吴恩达机器学习
  • 概率论小测试
  • AI 产品研发的一些思考
  • 3.模块化与MVVM设计模式
  • 2025舒适轮胎厂家、静音轮胎厂家企业品牌权威推荐榜:静音技术与驾乘体验口碑之选
  • 幻想是最廉价的止疼药
  • 20251005 耳朵龙字符串
  • 玩转树莓派屏幕之五:自定义LCD屏幕显示
  • AtCoder ARC207 总结
  • 2025.10.7模拟赛
  • 详细介绍:ZLG ZCANPro,ECU刷新,bug分享
  • 好好学习, 天天向上
  • 2.洋葱开发法
  • OpenStack搭建
  • OpenStack实验过程
  • 2025.10.7+7
  • oppoR9m刷Linux系统:VCOM模式备份系统与基带IMEI/NVRAM/QCN
  • 两个开源中国象棋引擎的编译
  • 推荐一款Swift开发框架- Aquarius
  • 1.如何导入Aquarius开发框架
  • 课程作业(10月8日)
  • 帮宣——可控核聚变