International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2018)

本文主要是介绍International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2018)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2018)

D. The Millennium Prize Problems

求有公约数x的所有数对之积，那么最大公约数为x的乘积只需要约数有x减掉最大公约数为2x,3x的数对之积。

E. Count Permutations

$d p [i] [j] [k]$ 记前i个已经有连续上升长度为j最后一个在后面的数里是第k小。

G. Robots race

LCT维护一个满足条件的最小生成树，加入新边时与树上链比较，判断是否可以替换，如果可以替换，cut&link。
貌似有更容易的方法。
注意到不同权值的边相互之间是独立的，只要判断相同权值的边能否同时在最小生成树上存在即可。维护权值小于 $x$ 的边加入进来之后图的联通状态（可持久化并查集）。

J. The test cases

倒着看，每次可以把 $x$ 变成 $\frac{x}{2}$ 或者 $\frac{x}{2}+\frac{N}{2}$ ，要从 $0$ 开始
遍历 $[0, n - 1]$ ，最后在1结束。那么不妨把 $x$ 换成 $n - x$ ， $x$ 可以变成 $\lceil \frac{x}{2}\rceil$ 或 $\lceil \frac{x}{2} \rceil + \frac{N}{2}$ 。x从0开始遍历，在 $n - 1$ 结束。那么就可以贪心了。
每次让x尽量小即可。