Difference between revisions of "Asia Yokohama Regional Contest 2018"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by 2 users not shown)
Line 24: Line 24:
  
 
Solved by kblack. 02:34 (+)
 
Solved by kblack. 02:34 (+)
 +
 +
题意:求最短的串,使得他不是提供的两个串的子序列。
 +
 +
题解:考虑贪心匹配子序列的情况,先解决一个串,$f_i$ 表示暴力匹配到 $i$ 最短需要多长串,从后往前算,算的时候优先走 0 就是字典序最小了,两个串那就搞个两维状态。
  
 
== Problem E ==
 
== Problem E ==
Line 36: Line 40:
  
 
Solved by kblack. 02:56 (+)
 
Solved by kblack. 02:56 (+)
 +
 +
题意:最小步数将一个序列调整完先不降再不升的序列。
 +
 +
题解:要达到目的,可以从小到大将每个数字移动到最左或最右,每步都是必要的,删除后不会对其他产生影响,从大到小瞎**算算。
  
 
== Problem H ==
 
== Problem H ==
Line 47: Line 55:
 
== Problem J ==
 
== Problem J ==
  
Unsolved.
+
Upsolved by zerol.
 +
 
 +
题意:给一棵结点有颜色的树。要求支持:修改一个结点的颜色,询问把某个颜色的结点都连通需要的最少的树上的边数。
 +
 
 +
题解:对于每一中颜色的结点维护一个 set,然后答案就是所有 dfs序 相邻的点对(包括 dfs序 第一个和最后一个)的距离除个二。
  
 
== Problem K ==
 
== Problem K ==

Latest revision as of 10:55, 3 March 2019

Problem A

Solved by zerol. 00:33 (+)

比大小签到。

Problem B

Solved by ultmaster. 01:09 (+)

题意:从一个集合里选一些数使得构成等差数列最长。

题解:d[i][j] 表示到 i,上一个是 j,最长是多少。转移的时候在一个 map 里反查一下,就是 $O(n^2 \log n)$ 了。

Problem C

Solved by zerol. 01:39 (+1)

题意:想象一个中间过道只能容纳一人的火车,过道两边有两排座位,每个人在每个单位时间内只能移动一格,同时每一个格子内至多只能有一个人,问需要多少时间能使所有人从出口离开。

题解:计算出所有人的不考虑阻塞的离开时间。然后排序后模拟一下,保证同一个时间至多只有一个人离开,答案就是最后一个人的离开时间。

Problem D

Solved by kblack. 02:34 (+)

题意:求最短的串,使得他不是提供的两个串的子序列。

题解:考虑贪心匹配子序列的情况,先解决一个串,$f_i$ 表示暴力匹配到 $i$ 最短需要多长串,从后往前算,算的时候优先走 0 就是字典序最小了,两个串那就搞个两维状态。

Problem E

Unsolved. (-2)

Problem F

Unsolved.

Problem G

Solved by kblack. 02:56 (+)

题意:最小步数将一个序列调整完先不降再不升的序列。

题解:要达到目的,可以从小到大将每个数字移动到最左或最右,每步都是必要的,删除后不会对其他产生影响,从大到小瞎**算算。

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Upsolved by zerol.

题意:给一棵结点有颜色的树。要求支持:修改一个结点的颜色,询问把某个颜色的结点都连通需要的最少的树上的边数。

题解:对于每一中颜色的结点维护一个 set,然后答案就是所有 dfs序 相邻的点对(包括 dfs序 第一个和最后一个)的距离除个二。

Problem K

Unsolved.

题意:田忌赛马。让你给出一种方案使得在赢得场次最多的前提下,字典序尽可能大。

题解(口胡):我们考虑逐位确定。先把当前的答案求出来(我们首先不能损失这个答案)。求答案的方法就是:把两个序列都按顺序排,对于每一匹马找尽可能小的能战胜它的。最后确定方案的时候我们考虑当前位上是要被打败还是不要被打败(就是选一个最小的可以打败它的放在上面,然后其余的再跑一遍上面的求答案的方法,看答案是否不变)。

  • 如果要被打败,那么我们就二分查找最大的马可以使答案不变。
  • 如果不被打败,那这一位我们已经不要了,所以显然也是马越小越好,但是字典序又要大,所以也二分查找最大的马使得后面还能不变。

复杂度是 $O(n^2 \log n)$。