Codeforces Round #686 (Div. 3) 题解

AC代码

A. Special Permutation

整体循环右移一位后输出即可。

B. Unique Bid Auction

用一个map统计信息,具体就是值为(key)的元素的出现次数为(value)

再用一个map统计信息,具体就是值为(key)的元素的最后一次出现在(value)

然后就遍历第一个map,看答案的值为多少,再根据第二个map找到下标。

C. Sequence Transformation

用一个map统计信息,具体就是当(x = key)时,答案为(value)

对于一个值(key),选择(x = key)的最小操作数就是看序列中值为(key)的元素将序列分割成多少个非空极大连续子序列。

模拟一下就完事了。

D. Number into Sequence

(n)分解质因数,若(n = Pi p_i^{k_i}),那么题目中的(k = max k_i),记(pos = argmax k_i)

输出的话,就输出(k_{pos} - 1)(p_{pos}),剩下的都堆到最后一个元素。

E. Number of Simple Paths

多出一条边会生成一个环。

对于环上的一个点(u),记(T(u))为以(u)为根但不经过其他环上节点的子树,其大小为(|T(u)|)

首先,(T(u))内部的点两两相互可达,生成(|T(u)|(|T(u)| - 1))条简单路径。

然后,对于环上两个不同的点(u)(v)(T(u))(T(v))中的点可以经过环相互可达,生成(2|T(u)||T(v)|)条路径。

所以可以先拓扑排序跑出环,并计算出子树大小,然后统计一下就完事了。

F. Array Partition

首先枚举(x),这个时候目标值已经可以确定了记为(v_1)

注意到此时第二段的最小值随着(y)的增加单调下降,所以可以二分(y)

假设当前第二段的最小值为(v_2)(v_2 e v_1)时就是普通的二分,但是(v_2 = v_1)时,还要保证第三段的最大值等于目标值才可以。

注意到此时第三段的最大值(v_3)随着(y)的增加单调下降,所以二分还是可行的,根据(v_1)(v_3)的相对大小修改端点即可。

第一段和第三段的最大值通过前缀最大值和后缀最大值就可以得出,第二段的最小值就线段树或者ST表随便实现个区间最小值查询就完事了,时间复杂度(O(nlog^2n)),足够优秀了。

总结

反正我不计分所以直接反向开题,F题一眼秒,贼开心。

万万没想到我E题写了半天还WA了,开心早了。

原文地址:https://www.cnblogs.com/zengzk/p/14033717.html