Difference between revisions of "2018 Multi-University Training Contest 1"

From EOJ Wiki
Jump to navigation Jump to search
 
Line 69: Line 69:
  
 
Upsolved by dreamcloud.
 
Upsolved by dreamcloud.
 
题意:
 
 
题解:
 
  
 
== Problem H ==
 
== Problem H ==

Latest revision as of 04:10, 29 August 2018

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.

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

题解:签到题。

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

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