2018 Multi-University Training Contest 1

Problem A

Solved.

题意：选择三个数$x$,$y$,$z$，使得$x+y+z=n$并且$x|n$,$y|n$,$z|n$,要求$x*y*z$最小。

题解：显然，$x$,$y$,$z$三个数越接近越优秀

那么当我们根据$1=\frac{1}{3}+\frac{1}{3}+\frac{1}{3}=\frac{1}{2}+\frac{1}{4}+\frac{1}{4}$对$n$分$\%3==0$和$\%4==0$讨论即可

剩余的情况就是不可行的

Problem B

Solved.

题意：将好几段括号序列首位拼接，是的括号匹配数量最大。

题解：我们先把自己串里面能匹配的括号全部匹配掉，这样，所有的串就会变成由若干个")"和若干个“（”拼接而成的串

然后我们要尽可能得把这些串首尾相连使得他们匹配的多

这里用贪心来解决，似乎和EOJ Monthly 2018.7 C 是类似的...但是仍然不会证明，结论是猜的，但是很好体会？(可以找出题人oxx来补一下证明)

• 在保证左括号比右括号多的情况下，按照右括号数量升序

• 尽可能得把左括号的多的放在前面

• 右括号多于左括号的情况下，按照左括号数量降序

Problem C

Solved.

题意：将给出的点连成三角形，使得没有相交的线段。

题解：题目保证了三点不共线

那么也就是说一个相同的坐标上最多有两个点

这样一来，我们可以先排个序，然后直接三个一组就能保证了

出题人想用凸包？所以$n\le 1000$......直播翻车现场

Problem D

Solved.

题意：要求构造一个长度为 n 且字典序最小的序列，使得若干指定区间内无重数。

题解：显然是最小的尽可能地放在前面，考虑贪心

我们对所有的区间排序，保证区间左端点递增

然后贪心的把当前可以放的最小值放在当前位置（可以用二分+树状数组或者二分+线段树维护，我忘记怎么在树状数组上二分了，就写了线段树QAQ）

对于扫不到的位置，全部置为$1$即可

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Upsolved by dreamcloud.

Problem H

Upsolved by Xiejiadong.

题意：给出一个数列$a$，求$RMQ$形态与$a$相同的、所有数都是在$[0,1]$区间内均匀分布的数列$b$的和的期望。

题解：先构建出$a$的笛卡尔树，与$a$的笛卡尔树同构的个数，就是树的拓扑序数量$\frac {n!}{\prod^{n}_{i=1} size_i}$，对于$a$直接构造笛卡尔树，然后遍历即可

而$\sum b_i$的期望显然是$\frac {n}{2}$，将两个答案相乘即可

Problem I

Unsolved.

Problem J

Solved.

题意：将时间做时区的变化。

题解：签到题。

乍看起来是一道满是细节的题目，突然醒悟对于麻烦的时区，我们直接用实数读入

这样一来这道题目似乎就简单多了？