2023NOIP A层联测31总结

\(T1\) 暴力操作：

给你一个长度为 \(n\) 的序列 \(a\) ，你可以花费 \(c_x\) 使得 \(a_i\) 变为 \([a_i / x]\) ，你总共有 \(k\) 元。为最终序列的中位数最小是多少。保证 \(n\) 为奇数。

\(n , m \le 5*10^5\)

首先想到了二分一个答案，因为只要使得前 \((n + 1) / 2\) 个数小于一个数就满足条件，所以这个满足单调性。

处理 \(c\) 数组的时候只想到了 \(m^2\) 的做法，而且向下取整的那部分没有处理好，就挂了。

正解就是这样，处理 \(c\) 数组的时候只要处理因子就好了。

\(T2\) 异或连通：

给定一个 \(n\) 个点 \(m\) 条边的无向图，每次询问 \(x\) ，若 \(w_i \oplus x \ge K\) ，则这条边不存在， \(w_i\) 为第 \(i\) 条边的权值。 对于每个询问，输出互相连通的点对个数。

\(n , m \le 10^5\)

一开始想了一种离线的加边操作，保证每条边只加入一次，但是对于这个异或的操作好像不适用。

就打了个 \(n , m , q\le 10^3\) 的暴力。

其实就是按位操作，对于每一位如果满足条件，就把 \(i\) 加入，需要 \(Trie\) 树和可撤回并查集维护。

\(T3\) 诡异键盘：

你有一个键盘，有两种操作，

• 按下按键 \(i\le n\) 会打印出字符串 \(S_i\) 。
• 按下按键 \(n + 1\) 会删掉结尾的 \(K\) 个字符

求打印出 \(S\) 需要的操作次数。

这个题看一眼就知道不会做了，打算先放着。

正解现在还没补出来

\(T4\) 民主投票：

有 \(n\) 个人形成了一个以 \(1\) 为根的树。除了 \(1\) 以外，每个人都必须给他的祖先投一票。对于每个 \(i\in[1 , n]\) 请问有没有一种方案使得 \(i\) 的最终票数严格大于其他人的票数。

想到了二分求一个每个人的最小票数，那样只要子树 \(i\) 内的数大于所有最小票数的最大值，子树 \(i\) 就是成立的。

当时看到过了样例就没管了，感觉挺神奇的。

过了后面几个点，但是最小的点没过，早知道就打个拼盘了。

估分 ：\(30 + 20 +0 + [0 , 100] = [50 , 150]\)

实际得分： \(0 +20 + 0 +80 = 100\)

这次考试按照自己的策略去打了，就是自己该拿什么分就尽力去骗，只是可能代码实现能力确实不够强，导致 \(T1\) 失分了。