小乔(☆_☆)

编辑于 2020-05-11 13:13

【题解】牛客练习赛58 精

update：C题数据已加强，比赛时的代码不进行rejudge，请大家重新提交测试。

难度评定：CF Div2

A：牛能和宝石

solution 1:

让我们考虑四个宝石 ${a_i,a_j,b_k,b_l)}$ 满足 ${a_i<=a_j,b_i<=b_j}$ ,显然其满足 ${max(a_i+b_l,a_j+b_k)<=max(a_i+b_k,a_j+b_l)}$ 。根据这个结论，把数组 ${a}$ 正序数组 ${b}$ 逆序即是最优配对，排个序时间复杂度 ${O(nlogn)}$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43089067

solution 2:

我们将数组 ${a}$ 排序，数组 ${b}$ 放入数据结构维护，然后二分答案，假设当前答案为 ${mid}$ ，我们倒序遍历数组 ${a}$ ，然后贪心的想，我们每次拿出的是数组 ${a}$ 中最大的，那么贪心的方案是在数组 ${b}$ 中还未匹配的集合中找出一个元素 ${b_i}$ 与当前遍历的元素 ${a_i}$ ,满足 ${b_i+a_i<=mid}$ ，并且 $b_i$ 尽可能的大，如果不能匹配说明当前答案 ${mid}$ 不符合，根据判断结果缩小范围继续判断。这种方法的时间复杂度为 ${O(nlog^2n)}$ ，显然比上述方法代码量大且更慢，但好处是不用动脑子就可以想出来。

B：牛妹和01串

显然，最优的方案就是从前往后贪心，检查当前串中出现了一个 ${0}$ 和一个 $1$ ，我们就把它划分为一个新的段，时间复杂度 $O(n)$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43089071

C：矩阵消除游戏

首先,我们使得 $k=min(k,min(n,m))$ ，因为当 ${k=n||k=m}$ 时我们就可以将所有行或所有列全部选择了。
然后，观察到数据范围极小，我们可以考虑枚举选择了多少行，再计算每一列中剩余元素的和进行排序，在根据值从小到大进行选择即可。因为 ${n,m}$ 同阶，所以时间复杂度为 $O(2^n(n^2+nlogn)))$
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43089020

D：迷宫

模拟一下牛妹走迷宫的策略，我们可以得出以下结论：

${1.}$ 牛妹不会向左走，因为牛妹一旦向左走一步，其右边一定是一个空格子，那么下一步牛妹又会走回原来的格子。

${2.}$ 牛妹不会向上走，如果牛妹当前可以向上走，说明其当前不可以向右走，说明其当前一定是向右走一段后或者向下走过一段，如果向下走过一段，那么走上去没有意义。如果向右走过一段，可以先向左走。那么这样都会造成牛妹在两个格子之间反复横跳。

根据以上结论，问题转换为：有一个 ${n*m}$ 的迷宫，牛妹只能向右和向下走，但优先向右走，是否可以添加一些障碍使得牛妹能从格子 ${(1,1)}$ 走到格子 ${(n,m)}$

现在考虑求解，设 ${dp_{i,j}}$ 表示牛妹走到格子 ${(i,j)}$ 所添加的最少格子数，可以得到转移,考虑两个非空格子： ${dp_{i,j}->dp_{i,j+1}}$
${dp_{i,j}+(mp[i][j+1]=='0')->dp_{i+1,j}}$
时间复杂度 ${O(n*m)}$
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43089044

E：最大GCD

显然，最优策略是我们只在区间 ${l，r}$ 中找出一个元素与 ${a_i(l<=i<=r)}$ 使得 ${gcd(a_i,x)}$ 最大化。
考虑到 ${x}$ 和 ${a_i}$ 的范围，那么考虑到 ${gcd(a_i,x)}$ 一定是 ${x}$ 的一个因子，而 ${1e5}$ 数据下的因子并不算多。
我们可以枚举 ${x}$ 的因子分别计算答案。
那么问题在于我们怎么实现，实现的方法有很多，因为不带修改，这里我介绍一种离线方式。
对于一个查询 ${l}$ ${r}$ ${x}$ ,我们将它分成若干个查询 ${l}$ ${r}$ ${p}$ ${id}$ 对于所有的 ${p}$ 满足 ${x}$ ${mod}$ ${p==0}$ ， ${id}$ 表示查询的编号。那么总的查询量最大为 ${nsqrt(A)}$ ，其中 ${A}$ 是查询中出现的最大的 ${x}$ 。
如何处理这么多的查询呢？对于每个不同的 ${p}$ ，将所有含因子 ${p}$ 的位置插入 ${vector}$ 容器，然后将所有查询按左端点排序，这里可以使用桶排序，或者考虑到单个 ${p}$ 中的查询量也是 ${O(n)}$ 级的，直接 ${sort}$ 排序也行。
然后从大到小枚举含有因子 ${p}$ 的位置，当枚举到位置 ${i}$ ，我们把所有关于 ${p}$ 的查询中 ${l<=i}$ 的查询全部弹出来，弹出来的时候判断是否 ${r>=i}$ ，如果大于，说明该区间包含因子 ${p}$ ，我们再更新第 ${id}$ 个查询的答案取最大值。
遍历所有因子 ${p}$ 即可得出答案，由于无论查询数量还是因子的数量都是 ${sqrt(A)}$ 级的，所以总的时间复杂度为 ${O(nsqrt(n))}$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43088999

F：XOR TREE

考虑一段长度为 ${k}$ 路径上的点集： ${v_1,v_2,v_3...v_k}$ ,我们先把每个点也算作路径，那么对于路径上一个点 ${v_i(1<=i)}$ ，考虑它在异或和中的出现次数，那么我们需要选择一个左端点 ${l}$ 和一个右端点 ${r}$ ，满足 ${1<=l<=i<=r<=k}$ ，这样的组合方法一共有 ${i*(k-i+1)}$ 种，因为是异或和，所以我们只需要观察 ${i*(k-i+1)}$ 的奇偶性。
当 ${k}$ 是一个偶数，如果 ${i}$ 是一个奇数，那么 ${k-i}$ 也是一个奇数，则 ${k-i+1}$ 是一个偶数，反正 ${k-i+1}$ 是一个偶数，那么结论是：无论 ${i}$ 取何值 ${i*(k-i+1)}$ 都是一个偶数，相当于这种情况下异或和为 ${0}$ 。
当 ${k}$ 是一个奇数，如果 ${i}$ 是一个奇数，那么 ${k-i}$ 是一个偶数，则 ${k-i+1}$ 是一个奇数。如果 ${i}$ 是一个偶数，那么 ${k-i+1}$ 的奇偶性已经不重要了。那么结论是：只有当 ${i}$ 为奇数时， ${v_i}$ 才对异或和有贡献。
那么就只需要求奇数位置的异或和再异或一个总的异或和（去掉单个点的价值），我们就可以得出每个查询的答案。
那么这题放在树上，其实没多大差别，我们树剖一下，线段树或者树状数组维护一下，就可以做出这道题了。时间复杂度 ${O(nlog^2n)}$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43089028