Loading... 官方题解:[Solution](https://codeforces.com/blog/entry/95583) ## A ### 简要题意 你有 $n$ 种武器,每种武器使用一次可以造成 $a_i$ 的伤害,并且同一种武器不能连续用两次(但是**可以重复使用**)。现在有一个 HP 为 $H$ 的遗迹守卫,问你最少多少次A掉它。 ### 题解 确实是我傻逼,题看错了 WA 了三发,好在是 VP。 我们肯定会交替使用伤害最高的两种武器,伤害分别为 $x, y$。假设一个操作回合我们用这两种武器,那么一共会造成 $x+y$ 的伤害。假如 $H \equiv 0 \mod {(x+y)}$,那么答案就是 $ans = 2 \times \frac{H}{x+y}$。如果不整除,只需要讨论余数在 $x$ 内还是外,分别对应 $+1$ 和 $+2$。 虽然是一道简单题,但还是要认真总结。因为看错了题,而且切的太慢了。 ## B ### 简要题意 给你一个数组,你需要将其升序排序。但是对于第 $i$ 个数,你只能交换 $j \in [i + x, n]$ 中的数。问是否存在合法方案。 ### 题解 可能是个牛逼题,我看见 zqy 秒掉了这个题,duang 28min 才切,iodwad 直接没切。不知道是为什么。我也吃了三发罚时(我是垃圾 首先 $n \geq 2 \cdot x$ 的肯定有解,相当于没有这个限制,每个数都可以先跳到一个 $ > i+x$ 的地方再跳回一个 $ \leq i + x$ 的地方。 否则的话,只有头 $n-x$ 个数和尾 $n-x$ 个数可以互换位置。那么只需要判断中间的那些数是不是跟有序的数组一样就行了。 智慧树上智慧果,智慧树下你和我。 ## C ### 简要题意 给一棵 $n$ 个点的树,现在你可以割至少 $1$ 条、至多 $k-1$ 条边,要求割了边之后形成的各个连通块内的点的异或和相等。问是否存在合法方案。 ### 题解 好像 C 题比 B 题好切。 什么条件下,每个连通块内的点的异或和会相等?首先你知道 $a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$ 且 $n \equiv 0 \mod {2}$ ,那么说明 $a_1 = a_2 = \dots = a_n$。如果 $n \equiv 1 \mod{2}$ ,那么异或起来应该等于 $a_i$。 $n \equiv 0 \mod{2}$ 的情况比较平凡,直接 `puts("YES")` 即可。我们来讨论第二种情况,也就是说,我们要把整棵树分成奇数个连通块,可以认为就是分成 $3$ 个就行。 我们要叉掉两条边,假如能找到一条边叉掉以后连通块异或和相等,只需要检查 $K \neq 2$ 即可。 具体地如何找这两条边,我们只需要先找到一棵子树异或和 $=x$,然后再找第二条即可。 ## D ### 简要题意 CF 文件交互题 给一棵 $n$ 个点的树,定义 $Dist(u,v)$ 为 $u \to v$ 路径上的边构成的边权集合的 $\gcd$,且 $u \neq v$。 每一你可以询问交互库 $x$ 个点的点集 $X$,交互库会返回 $X$ 中,$\max\{Dist(u,v)\}, u,v \in X$ 。也就是说,交互库会找到 $X$ 中 $Dist$ 最大的一个点对 $(u,v)$ 并且返回它们的 $Dist$。 最多可以询问交互库 $12$ 次。你需要找到整棵树中 $Dist(u,v)$ 最大的那个点对 $(u,v)$。若有多个,任意一个都合法。 交互格式: 询问:`? k v_1 v_2 ... v_k` 回答:`! u v` ### 题解 不是很懂,看了题解恍然大悟。 这个 $Dist$ 的定义看起来很高端,但实际上,要 $Dist$ 最大,肯定就是两个点相邻,然后那条边的边权在树上最大..... 然后就二分一下就行了,$n \leq 10^3$ 问 $12$ 次肯定能过。 ## E ### 简要题意 给定一个 $n$ 个数的数组,要求找一个连续子区间,满足该子区间的区间 $\&$ 和 $>$ 区间异或和。求该子区间的最大长度。 ### 题解 首先 $\&$ 出来要不是 $0$,那肯定是该区间所有数的二进制在那一位上全是 $1$。 其次还要满足 $\&$ 出来要大于异或和。那如果该区间长度为奇数,那么 $\&$ 和有可能与异或和相等。所以只有长度为偶数的子区间合法。 现在要做的事就是找到一个位满足这个条件:在某一个子区间上这一位全是 $1$。如果高位满足条件,那么低位都可以不考虑。 但是出现了一个问题,不一定 $\&$ 出来比异或和大。强制规定更高为的异或和为 $0$ ,这样在枚举到更高位时情况没有算漏。 代码也非常精简: ```cpp for (int i = 19; ~i; -- i) { for (int j = 1; j <= n; ++ j) { And[j] = And[j - 1] + ((a[j] >> i) & 1), Xor[j] ^= ((And[j] & 1) << i); } memset(pre, -1, sizeof(pre)); pre[0] = 0; for (int j = 1; j <= n; ++ j) { if (pre[Xor[j]] == -1) pre[Xor[j]] = j; else { int k = pre[Xor[j]]; if (And[j] - And[k] == j - k) ans = std::max(ans, j - k); else pre[Xor[j]] = j; } } } ``` 最后修改:2021 年 10 月 19 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏