Andrew Stankevich Contest 45 (ASC 45)

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 | ultmaster. (-2)

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

ultmaster: 也写了一个。明明方法是一样的，但是优化了好久。可能是笔记本性能有限吧？

Problem D

Solved by ultmaster. 00:47 (+)

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

Problem E

Upsolved by ultmaster.

题意：旅行商问题。给一个序列要求调换顺序，相邻两者之间有一个代价。调换顺序也有要求，只能调换前一半和后一半，然后递归。

题解：$dp(i,j)$ 表示前缀 $i$，最后一个是 $j$ 的最小代价。转移是显然的。复杂度（不能证明）是 $O(n^2 \log n)$。

这题错误地想成了树形 DP。多给点时间或许能想出来。

Problem F

Solved by zerol. 01:18 (+2)

题意：给一个无向图的边分配值（1~m），使得每个点的出边权值和各不相同。题目保证 1 与所有其他点都相连。 题解：1 出去的边分配最大的若干值使得 1 的和一定最大。其它任意连，然后按其它点当前和从小到大，和 1 的边依次从小到大分配剩下的值。

交之前愣是看了好一会，但完全没有任何用处，没有初始化，后来初始化范围错了导致 RE，数组大小开得刚刚好也是没必要的（对于这种题），一下子加了 50 min。（很惭愧）

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by kblack. 02:16 (+)

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

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

ultmaster: 稳健的 kblack 一通暴力，一发过了。。。。（膜