Codeforces Round 888 (Div. 3)

Codeforces Round 888 (Div. 3)

T1

​ 思路：直接模拟。

T2

​ 思路：首先记录原始数组的奇偶性，然后将奇数、偶数分为不同两组进行排序，然后再根据原数组的奇偶性按顺序填入奇数偶数，最后判断整个数组是否非递减。

T3

思路：我们已知开始在 \(a_1\) ，最后在 \(a_n\) 。那么当 \(a_1 \ne a_n\) 时，只需要满足路径中前 \(k\) 个数为 \(a_1\) ，后 \(k\) 个数为 \(a_n\) 。如果 \(a_1 = a_n\) ，只需要满足共有 \(k\) 个数为 \(a_1\) 即可。

T4

思路：通过前缀和数组我们可以得到 \(n-1\) 个数字。此时分两种情况来讨论:

​ 1.前缀和数组的尾缺失了。

​ 2.前缀和数组缺失了其余位置数。

​ 情况1：尾部缺失，如果得到的 \(n-1\) 个数字可以与排列中的不同数字一一对应，那么加上尾部后能够组成序列。

​ 情况2：中间缺失的话，这 \(n-1\) 个数当中有一个数代表了原数组中的 \(a_i + a_{i+1}\) 。如果 \(n-2\) 个数能与原序列当中不同数字相对应，且剩下的两个没有对应数字相加为余下的那一个数，则能够组成序列。综上，只需要记录一下有多少个数字能与序列匹配然后再判断即可。

T5

思路：典型的记忆化搜索题目，\(dp_i\) 表示求第 \(i\) 种药剂所花费的最小金币数，\(cost_i\) 表示第 \(i\) 种药剂所花费的最小金币数，\(flag_i\) 表示是否已经算出了 \(cost_i\) ，用容器 \(b_i\) 表示合成第 \(i\) 种药剂所需要的药剂。若 \(cost_i\) 已经求出来了，则标记一下，下次直接返回 \(cost_i\) 即可。\(cost_i = \min \{cost_i,\sum_{j=0}^{b_i.size()-1}(cost_{e_{i,j}})\}\) 。

T6

思路：（ $a_i $ 异或 \(x\)）&（ \(a_j\) 异或 \(x\)）由于异或相同的 \(x\) ，而且 \(x\) 能自己随意选，那么找最大值就相当于只要找到 \(a_i\) 异或 \(a_j\) 的最小值。

因为如果 \(a_i\) 与 \(a_j\) 某一位不相同，那么这一位不论异或1还是0，最后都会得到1和0，然后相与为0，只有某一位相同才能通过改变x在该位的值使得这一位异或后等于1.

上述就相当于 \(a_i\) 同或 \(a_j\) 后最大，那么也就是 \(a_i\) 异或 \(a_j\) 后最小。

然后有个结论，\(n\) 个数的最小异或对答案就是排序后最小的相邻异或和。

最后 \(x\) 的值就是从 \(0 \sim k-1\) 位遍历。

T7

思路：一条路径的起点与终点。我们很据 \(h_{起点}+初始能量\) 的大小来排序，从小到大依次查询，边也按边权排序，对于每次查询，将所有的边权小于等于 初始能量 \(h_{起点}+\) 的边两边的点在并查集中合并，最后如果起点终点在同个集合中就说明起点能到终点，否则就不能。