Difference between revisions of "Andrew Stankevich Contest 45 (ASC 45)"
| Line 6: | Line 6: | ||
kblack: 没错就是我干的！ | kblack: 没错就是我干的！ | ||
| + | |||
| + | 题意：求两个大小为 $n$ 的集合，使得这两个集合的 $\{x + y | x, y \in A, x \neq y\}$ 相等。 | ||
| + | |||
| + | 题解：打表找规律，发现只有 $2$ 的幂次才有可能。然后就过了。后来想想好像这个也不是太难构造。 | ||
=== Problem B === | === Problem B === | ||
| Line 11: | Line 15: | ||
Solved by ultmaster & zerol. 04:05 (+14) | 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 === | === Problem C === | ||
| Line 23: | Line 34: | ||
Solved by ultmaster. 00:47 (+) | Solved by ultmaster. 00:47 (+) | ||
| − | + | 签到。做过经典题 Random Walk 的人都知道，套路一下就好了。（当然做过忘了的人又找了好久的规律） | |
=== Problem E === | === Problem E === | ||
| Line 54: | Line 65: | ||
Solved by kblack. 02:16 (+) | Solved by kblack. 02:16 (+) | ||
| + | |||
| + | 题意：在一个多边形里塞两个圆。 | ||
| + | |||
| + | 题解：二分答案。把多边形所有边向里面平移 $2r$，然后只要最远距离大于 $r$ 就好了（因为是凸多边形，不然就变成 WF 题了）。这题数据范围很小，怎么暴力怎么来。 | ||
<del>ultmaster: 稳健的 kblack 一通暴力，一发过了。。。。（膜</del> | <del>ultmaster: 稳健的 kblack 一通暴力，一发过了。。。。（膜</del> | ||
| − | |||
| − | |||
Revision as of 01:01, 12 March 2018
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 一通暴力，一发过了。。。。（膜