Difference between revisions of "ACM-ICPC 2017 Asia Tsukuba Regional"

From EOJ Wiki
Jump to navigation Jump to search
Line 22: Line 22:
  
 
Solved by Xiejiadong. 03:00:39(+1)
 
Solved by Xiejiadong. 03:00:39(+1)
 +
 +
题意:每次修改是把一整段变成同一个颜色,求最少多少次可以变成目标状态。
 +
 +
题解:如果把某一整段修改的话,显然剩下的就是把中间不一样的一段一段改。
 +
 +
那么,显然,整段的喷涂是不连续的一段一段组成的,我们可以用dp解决。
 +
 +
用$f[i]$表示,喷涂到第$i$位的最小代价,那么$f[i]=min{f[j]+cost(j+1,i)}+1$,当$a[i]=b[i]$时,$f[i]=f[i-1]$
 +
 +
$cost(j+1,i)$可以用前缀和解决,然后用单调队列维护dp,时间复杂度$O(n)$。
  
 
== Problem F ==
 
== Problem F ==

Revision as of 15:10, 24 September 2018

One,Two,Three,AK

Problem A

Solved by Xiejiadong. 00:09:42(+)

煞笔dp,温暖的签到。

Problem B

Solved by dreamcloud. 00:35:42(+)

Problem C

Solved by oxx1108. 00:58:09(+)

Problem D

Unsolved.

Problem E

Solved by Xiejiadong. 03:00:39(+1)

题意:每次修改是把一整段变成同一个颜色,求最少多少次可以变成目标状态。

题解:如果把某一整段修改的话,显然剩下的就是把中间不一样的一段一段改。

那么,显然,整段的喷涂是不连续的一段一段组成的,我们可以用dp解决。

用$f[i]$表示,喷涂到第$i$位的最小代价,那么$f[i]=min{f[j]+cost(j+1,i)}+1$,当$a[i]=b[i]$时,$f[i]=f[i-1]$

$cost(j+1,i)$可以用前缀和解决,然后用单调队列维护dp,时间复杂度$O(n)$。

Problem F

Unsolved.

Problem G

Solved by oxx1108. 04:56:50(+1)

Problem H

Unsolved.

Problem I

Solved by Xiejiadong. 03:22:13(+3)

Problem J

Unsolved.

Problem K

Upsolved by oxx1108.

ECNU Foreigners

ultmaster: 签到成功!kblack 再次扛起重任,拿下全场贡献最佳奖。

Problem A

Solved by zerol. 00:12 (+)

温暖的签到。

Problem B

Solved by ultmaster. 01:26 (+)

题意:把 $m$ 个点两两匹配成 $m/2$ 条直线,然后求最多的平行线对数。

题解:可能划分的数量大概只有 2E6。巧妙地把这些方案枚举出来了以后,逐一计算就可以了。

因为没有输出答案,错误地把 debug 信息当成了答案。自闭半小时。

Problem C

Solved by ultmaster. 00:38 (+1)

题意:非常类似于 CPU 中的流水线。每条指令在每个阶段的用时只跟指令有关,不跟阶段有关。求某个时间点各个指令都在第几个阶段(或在等待第几个阶段)。

题解:暴力算出每个东西进入流水线的时间。然后进入流水线之后每个周期的时间,是跟之前进入流水线的所有指令所需要的时钟周期的最大值有关的。至于如何判断是否已经结束是否在等待,大概只要模一下算一算就好了。同时要考虑到进入第一个阶段之前的情况(要先判断)。

Problem D

Problem E

Problem F

ultmaster: 题目读错背大锅。而且可能顺带抹杀了做出其他题的可能性。

Problem G

Solved by kblack. 02:28 (+)

Problem H

Problem I

Solved by kblack. 01:28 (+1)

Problem J

Solved by kblack. 03:33 (+)

Problem K