Gym 102215K – Deck Sorting

题目链接:2019, XII Samara Regional Intercollegiate Programming Contest, K

首先我们可以确定的是如果三种卡牌不全有,那么答案一定是YES。因为如果只有一种,无论怎么放都是合法的;如果有两种,一种放第一堆,一种放第二堆,即可。

如果三种卡牌都有,那么我门要考虑放的策略。最终只有两种情况是合法的,一种是$[(a \cdots a, b \cdots b), (b \cdots b, c \cdots c)]$,一种是$[(a \cdots a, b \cdots b), (c \cdots c, {\rm none})]$。我们可以贪心地把原序列一段连续地相同的并成一个,得到一个新的序列,然后对每一位卡牌放入哪一对进行搜素。这里贪心地依据是当连续地相同颜色地摆在两堆都合法地时候,放在同一堆里比较节约空间。合并地这个操作非常关键,合并完之后搜索地时间复杂度就可以被很好地控制。

详见代码。

 

说点什么

avatar
50
  Subscribe  
提醒