Andrew Stankevich Contest 45 (ASC 45)

From EOJ Wiki
Revision as of 01:01, 12 March 2018 by Ultmaster (talk | contribs)
Jump to navigation Jump to search

Problem A

Solved by ultmaster. 01:59 (+3)

ultmaster: 罚时不是我贡献的。

kblack: 没错就是我干的!

题意:求两个大小为 $n$ 的集合,使得这两个集合的 $\{x + y | x, y \in A, x \neq y\}$ 相等。

题解:打表找规律,发现只有 $2$ 的幂次才有可能。然后就过了。后来想想好像这个也不是太难构造。

Problem B

Solved by ultmaster & zerol. 04:05 (+14)

题意:题目是一堆复杂的概率。转化出来就是求最小的区间使得被阴影覆盖的长度大于一个给定值。

题解:滑动窗口即可。注意各种细节。ultmaster 写错了若干个地方。疯狂 GG。下面列举 TA 犯过的错误:

  • 错误 1:ultmaster 发现自己不会写滑动窗口,然后为了一个 if 跟 zerol 辩论,最后输了。QAQ(其实这个还不算错误)
  • 错误 2:反着做(第二遍)的时候,$x,y$ 取反了,但没有交换,导致偏序反了。
  • 错误 3:ultmaster 发现 TA 的关同步是假的。而且文件读入的话,似乎关了也没有用?反正最后全改了 scanf。
  • 错误 4:就算是整数,因为读入用了浮点,所以在判断相等的时候还是要使用 EPS。

Problem C

Upsolved by kblack. (-2)

正确的 DP 状态是 (长度, 最后一个元素, 下界, A, 出现的数字的bits)之后枚举下一个数即可。使用BFS,状态不会遇到太多,代码写得略辣鸡,本地跑了60s。。。看来不够RUSH!

Problem D

Solved by ultmaster. 00:47 (+)

签到。做过经典题 Random Walk 的人都知道,套路一下就好了。(当然做过忘了的人又找了好久的规律)

Problem E

Upsolved by ultmaster.

没时间了。

Problem F

Solved by zerol. 01:18 (+2)

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by kblack. 02:16 (+)

题意:在一个多边形里塞两个圆。

题解:二分答案。把多边形所有边向里面平移 $2r$,然后只要最远距离大于 $r$ 就好了(因为是凸多边形,不然就变成 WF 题了)。这题数据范围很小,怎么暴力怎么来。

ultmaster: 稳健的 kblack 一通暴力,一发过了。。。。(膜