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

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "== Problem A == Solved. 题意:选择三个数$x$,$y$,$z$,使得$x+y+z=n$并且$x|n$,$y|n$,$z|n$,要求$x*y*z$最小。 题解:显然,$x$,$y$,$z$三个数越接近...")
 
Line 68: Line 68:
 
== Problem G ==
 
== Problem G ==
  
Unsolved.
+
Upsolved by dreamcloud.
 +
 
 +
题意:
 +
 
 +
题解:
  
 
== Problem H ==
 
== Problem H ==

Revision as of 01:35, 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

Unsolved.

Problem I

Unsolved.

Problem J

Solved.

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

题解:签到题。

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

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