codeforces 686 div3

零、背景

上周参加了一场 codeforces div3 的比赛。
对于 codeforces 一般情况下只有 初级赛场 div1 和 高级赛场 div2 的比赛。
对于 div3 ，则是最简单，很少见的，而我依旧剩下一道题没时间做了。

看来还是需要多练习。

A. Special Permutation

题意：构造一个大小为 n 的数组，使得 str[i] != 1。

思路：方法很多。

方法一：第一个位置放最大值，其他位置都放 i+1。

方法二：如果有偶数个，交换相邻两个位置；
如果有奇数个，最后三个错开，其他位置交换相邻两个位置。

B. Unique Bid Auction

题意：给一个数组，求最小的只出现一次数字的下标。

思路：依旧有很多方法。

方法一：记录下标排序，寻找连续只有一个的数字。

方法二：使用 map 统计，然后找只出现一次的数字。

C. Sequence Transformation

题意：任意选择一个数字，每次可以删除一个区间，但是区间中不能有这个数字。
问最少可以删几次可以只剩下选择的数字。

思路：题意原先描述的有问题。

原先描述的是每次可以选择不同的数字进行删除，此时是一个很复杂的问题。

中间的时候，官方发公告说一旦选择一个数字，后面都不能变化了。
此时再看题意，就是一个大水题了。

枚举统计每个数字，计算当前数字的答案即可。

默认复杂度是 O(n^2)。
如果先对每个数字进行分组，则复杂度可以降为O(n)。

D. Number into Sequence

题意：给一个数字 n，构造一个最长数组，使得数组满足下面两个性质。

1）a1*a2...an=n
2) ai+1 % ai = 0

使用文字描述就是，所以数字相乘是 n，后一个数字是前一个数字的倍数。

思路：由于后一个数字是前一个数字的倍数，所以可以确定所有数字都是第一个数字的倍数。
想要数组最长，自然需要寻找幂数最多的因子，前面每个位置一个因子即可。

寻找因子可以预先筛一个素数表，然后log(n)的复杂度得到答案。

E. Number of Simple Paths

题意：给一个 n 个顶点 n 条边的无向连通图，问存在多少条路径。

思路：很有意思的一道题。

n-1条边就是一颗树，n条边就是树上存在一个环。

如果是一条树的话，可以确定存在 c(n,2)条路径。
那多了一条边，答案肯定会多一些这条边相关的路径。

那存在多少个呢？
此时需要缩点，将这个图缩小为一个环。

然后任意选择一条边来当做是新加入树上的边。

接着在图上画一下看心中了哪些边，加起来，就可以找到一个O(n)的公式来。

F. Array Partition

题意：给一个数组，问是否可以将数组划分三个区间[1~l],[l+1,r],[r+1,n]，使得max(1,l) = min(l+1,r) = max(r+1, n)。

思路：如果整个数组的最大值有三个，那显然可以构造出答案来。

其他情况就需要枚举左区间，然后判断是否存在右区间了。

枚举左区间的时候，最大值就确定了。
此时右区间可以通过二分查找后缀最大值来确定。
右区间确定后，使用线段树查找中间区间的最小值，判断是否满足答案。

七、最后

这次比赛最后两道题比较有意思。

对算法感兴趣的可以研究一下最后两道题。

比赛源代码：
https://github.com/tiankonguse/ACM/tree/master/codeforces/686/div3

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code