Difference between revisions of "Andrew Stankevich Contest 45 (ASC 45)"

From EOJ Wiki
Jump to navigation Jump to search
 
(5 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
Solved by ultmaster. 01:59 (+3)
 
Solved by ultmaster. 01:59 (+3)
  
罚时不是我贡献的。
+
ultmaster: 罚时不是我贡献的。
 +
 
 +
kblack: 没错就是我干的!
 +
 
 +
题意:求两个大小为 $n$ 的集合,使得这两个集合的 $\{x + y | x, y \in A, x \neq y\}$ 相等。
 +
 
 +
题解:打表找规律,发现只有 $2$ 的幂次才有可能。然后就过了。后来想想好像这个也不是太难构造。
  
 
=== Problem B ===
 
=== Problem B ===
Line 9: Line 15:
 
Solved by ultmaster & zerol. 04:05 (+14)
 
Solved by ultmaster & zerol. 04:05 (+14)
  
ultmaster 写错了若干个地方。疯狂 GG。
+
题意:题目是一堆复杂的概率。转化出来就是求最小的区间使得被阴影覆盖的长度大于一个给定值。
 +
 
 +
题解:滑动窗口即可。注意各种细节。ultmaster 写错了若干个地方。疯狂 GG。下面列举 TA 犯过的错误:
 +
 
 +
* 错误 1:ultmaster 发现自己不会写滑动窗口,然后为了一个 if 跟 zerol 辩论,最后输了。QAQ(其实这个还不算错误)
 +
* 错误 2:反着做(第二遍)的时候,$x,y$ 取反了,但没有交换,导致偏序反了。
 +
* 错误 3:ultmaster 发现 TA 的关同步是假的。而且文件读入的话,似乎关了也没有用?反正最后全改了 scanf。
 +
* 错误 4:就算是整数,因为读入用了浮点,所以在判断相等的时候还是要使用 EPS。
  
 
=== Problem C ===
 
=== Problem C ===
  
Upsolved by kblack. (-2)
+
Upsolved by kblack | ultmaster. (-2)
  
 
正确的 DP 状态是 (长度, 最后一个元素, 下界, A, 出现的数字的bits)之后枚举下一个数即可。使用BFS,状态不会遇到太多,代码写得略辣鸡,本地跑了60s。。。看来不够RUSH!
 
正确的 DP 状态是 (长度, 最后一个元素, 下界, A, 出现的数字的bits)之后枚举下一个数即可。使用BFS,状态不会遇到太多,代码写得略辣鸡,本地跑了60s。。。看来不够RUSH!
 +
 +
ultmaster: 也写了一个。明明方法是一样的,但是优化了好久。可能是笔记本性能有限吧?
  
 
=== Problem D ===
 
=== Problem D ===
Line 21: Line 36:
 
Solved by ultmaster. 00:47 (+)
 
Solved by ultmaster. 00:47 (+)
  
做过经典题 Random Walk 的人都知道,套路一下就好了。(当然做过忘了的人又找了好久的规律)
+
签到。做过经典题 Random Walk 的人都知道,套路一下就好了。(当然做过忘了的人又找了好久的规律)
  
 
=== Problem E ===
 
=== Problem E ===
Line 27: Line 42:
 
Upsolved by ultmaster.
 
Upsolved by ultmaster.
  
没时间了。
+
题意:旅行商问题。给一个序列要求调换顺序,相邻两者之间有一个代价。调换顺序也有要求,只能调换前一半和后一半,然后递归。
 +
 
 +
题解:$dp(i,j)$ 表示前缀 $i$,最后一个是 $j$ 的最小代价。转移是显然的。复杂度(不能证明)是 $O(n^2 \log n)$。
 +
 
 +
这题错误地想成了树形 DP。多给点时间或许能想出来。
  
 
=== Problem F ===
 
=== Problem F ===
  
 
Solved by zerol. 01:18 (+2)
 
Solved by zerol. 01:18 (+2)
 +
 +
题意:给一个无向图的边分配值(1~m),使得每个点的出边权值和各不相同。题目保证 1 与所有其他点都相连。
 +
题解:1 出去的边分配最大的若干值使得 1 的和一定最大。其它任意连,然后按其它点当前和从小到大,和 1 的边依次从小到大分配剩下的值。
 +
 +
交之前愣是看了好一会,但完全没有任何用处,没有初始化,后来初始化范围错了导致 RE,数组大小开得刚刚好也是没必要的(对于这种题),一下子加了 50 min。(很惭愧)
  
 
=== Problem G ===
 
=== Problem G ===
Line 52: Line 76:
  
 
Solved by kblack. 02:16 (+)
 
Solved by kblack. 02:16 (+)
 +
 +
题意:在一个多边形里塞两个圆。
 +
 +
题解:二分答案。把多边形所有边向里面平移 $r$,然后只要最远距离大于 $2r$ 就好了(因为是凸多边形,不然就变成 WF 题了)。这题数据范围很小,怎么暴力怎么来。
  
 
<del>ultmaster: 稳健的 kblack 一通暴力,一发过了。。。。(膜</del>
 
<del>ultmaster: 稳健的 kblack 一通暴力,一发过了。。。。(膜</del>
 
放入圆形的套路,二分半径 R,所有边往内部缩 R,然后看最远距离有没有 2R 即可。
 

Latest revision as of 16:15, 17 July 2019

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 一通暴力,一发过了。。。。(膜