Difference between revisions of "2016 ACM-ICPC World Finals"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 12: Line 12:
  
 
Solved by ultmaster. 03:38 (+1)
 
Solved by ultmaster. 03:38 (+1)
 +
 +
题意:这个题是流水线的两部分。前一部分是一个简单最短路,后一部分是有 $n$ 个东西,每个东西有个权值 $w_i$,要划成 $k$ 组使得 组的大小乘以组内权值和 的和 最小。
 +
 +
题解:显然先将 $w_i$ 排序,相邻的划在一起会更好。记状态 $f(i,j)$ 为前 $i$ 组用了 $j$ 个的答案,那么 $f(i,j)=\min_{0 \le k < j} f(i-1,k)+(s_j-s_k)(j-k)$。问题在于 这个里面有 $s_j k$ 和 $s_k j$ 两项,不能快乐斜率优化。我们可以感受一下这个东西性质非常好,决策肯定是有某种单调性的,而且又是两维的。把样例的决策点打出来之后,大胆猜测符合 $p(i-1,j) \le p(i,j) \le p(i+1,j)$ 就可以采用 Knuth Optimization 解决了。
 +
 +
Knuth Optimization: 每一行从右往左扫,决策点取值就被右边和上面夹住了,总复杂度是 $O(n^2)$ 的。当然有人告诉我这叫四边形不等式(表示不知道什么是四边形不等式
  
 
== Problem C ==
 
== Problem C ==
Line 22: Line 28:
  
 
Solved by ultmaster. 01:10 (+1)
 
Solved by ultmaster. 01:10 (+1)
 +
 +
题意:没有人愿意写的模拟签到。
 +
 +
题解:用三个位表示三种状态,比如 1 表示肯定暗了,2 表示是好的,4 表示肯定亮了。然后对于每个可能的开始节点,跑完接下来的 $l$ 秒钟,将得到的位状态『与』起来(因为每个时刻都要满足);注意如果状态中出现 0 了,这整个情况就已经不可能了。对于所有可能的开始节点再将这些状态或起来。如果有 0 不可能,出现 1 2 4 之外的情况就是 ?,否则依次输出。
 +
 +
* 耐心点不要抄错。
 +
* 不要犯模 1440 忘了回卷的低级错误。
 +
* 写得快一点就有一血了。
  
 
== Problem E ==
 
== Problem E ==
  
 
Solved by ultmaster. 01:40 (+2)
 
Solved by ultmaster. 01:40 (+2)
 +
 +
题意:求最大的 b 使得 y 的 b 进制表示只使用了 0-9,而且将这个表示作为十进制来看不低于 l。
 +
 +
题解:试两种情况:
 +
 +
* 将最后的表示从 y 开始一个一个往上试,每试一个用二分搜索求 b。
 +
* 将 b 从 10 开始一个一个往上试,每试一个求出 b 进制表示跟 l 比较。
 +
 +
YY 一下能发现这两种情况很快就能碰头。只要二分不要写错就不会怀疑它的正确性。
  
 
== Problem F ==
 
== Problem F ==

Latest revision as of 14:20, 24 March 2019

Problem A

Solved by zerol. 04:30 (+1)

CF 突然炸了。就交在 kattis 上了。

题意:有一些糖果,每个糖果有一个比例,对于任意前若干天,天数和比例之积必须和该糖果的数量之差的绝对值在 1 之内。一开始给了若干天合法的吃糖果方案,问最多还能撑几天不破坏平衡性(当然也可以一直平衡下去)。

题解:计算出每一种糖果如果不去吃它能撑到那一天,然后每次吃那个最先凉掉的,如果发现早就凉了那就结束了。另外,容易程度会随着天数的增加而增加,如果前面很多天都没问题那就真的没问题了。

Problem B

Solved by ultmaster. 03:38 (+1)

题意:这个题是流水线的两部分。前一部分是一个简单最短路,后一部分是有 $n$ 个东西,每个东西有个权值 $w_i$,要划成 $k$ 组使得 组的大小乘以组内权值和 的和 最小。

题解:显然先将 $w_i$ 排序,相邻的划在一起会更好。记状态 $f(i,j)$ 为前 $i$ 组用了 $j$ 个的答案,那么 $f(i,j)=\min_{0 \le k < j} f(i-1,k)+(s_j-s_k)(j-k)$。问题在于 这个里面有 $s_j k$ 和 $s_k j$ 两项,不能快乐斜率优化。我们可以感受一下这个东西性质非常好,决策肯定是有某种单调性的,而且又是两维的。把样例的决策点打出来之后,大胆猜测符合 $p(i-1,j) \le p(i,j) \le p(i+1,j)$ 就可以采用 Knuth Optimization 解决了。

Knuth Optimization: 每一行从右往左扫,决策点取值就被右边和上面夹住了,总复杂度是 $O(n^2)$ 的。当然有人告诉我这叫四边形不等式(表示不知道什么是四边形不等式

Problem C

Solved by zerol. 00:20 (+)

温暖的签到。

Problem D

Solved by ultmaster. 01:10 (+1)

题意:没有人愿意写的模拟签到。

题解:用三个位表示三种状态,比如 1 表示肯定暗了,2 表示是好的,4 表示肯定亮了。然后对于每个可能的开始节点,跑完接下来的 $l$ 秒钟,将得到的位状态『与』起来(因为每个时刻都要满足);注意如果状态中出现 0 了,这整个情况就已经不可能了。对于所有可能的开始节点再将这些状态或起来。如果有 0 不可能,出现 1 2 4 之外的情况就是 ?,否则依次输出。

  • 耐心点不要抄错。
  • 不要犯模 1440 忘了回卷的低级错误。
  • 写得快一点就有一血了。

Problem E

Solved by ultmaster. 01:40 (+2)

题意:求最大的 b 使得 y 的 b 进制表示只使用了 0-9,而且将这个表示作为十进制来看不低于 l。

题解:试两种情况:

  • 将最后的表示从 y 开始一个一个往上试,每试一个用二分搜索求 b。
  • 将 b 从 10 开始一个一个往上试,每试一个求出 b 进制表示跟 l 比较。

YY 一下能发现这两种情况很快就能碰头。只要二分不要写错就不会怀疑它的正确性。

Problem F

Unsolved.

Problem G

Solved by kblack. 02:19 (+2)

题意:要一根不平行于 x 轴的直线使得相交的线段数最长。

题解:总可以调整使得目标直线至少经过一条线段的某个顶点,转一圈。

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by zerol. 02:40 (+1)

题意:有点复杂,自行读题。

题解:发现如果两个 k 层的接在一起的话可以看成一个 k 层的。所以只需要对于每一个可能的层数判断能不能做到就行了(中间多出来的可以全部视为 1 层的),从两头扫一下就行了。注意答案是 1 层的需要特判。


zerol: 这题是 U 送我的。

Problem L

Solved by kblack. 00:49 (+)

大鱼吃小鱼签到。

Problem M

Unsolved.