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

201007

news 2026/6/11 21:05:04

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\) 这两个位置上的数相同且未消掉，而且这两个位置的奇偶性也是相异的。同理这样递归下去，我们就会得到两个相邻的数相同，但是未被消去，这显然和最终状态是矛盾的。所以我们可以说“奇偶性不同的两个相同的数是否一定能相消”。

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