Google Code Jam 2020 Round1B Join the Ranks

题意

给你一个形如\(1,2,\cdots,R，1,2,\cdots,R,1\cdots\)的序列，共重复\(C\)次。你每次可以选择一个区间\([L,R]\)将其平移到序列首部，最终使得序列具有\([1,1,\cdots,1,2,2,\cdots,2,\cdots,R,R,\cdots,R]\)的形式。问最少需要多少次，并输出具体步骤。

解题思路

比赛的时候只来得及写前两道，这道题是赛后看dls录播后补的。啥都不说了，dlstxdy!

对于相邻且相同的元素，我们就把他合并成\(1\)个元素，要求的序列形式就变为\([1,2,\cdots,R]\)。

对于一个序列，把他的一段区间平移到序列的首部，很容易可以证出最多删掉两个元素。

比如对于\([[1,2],[3,1],2,3,1,2,3]\)，我们可以把第一个\([3，1]\)移到序列首部，得到\([3,1,1,2,2,3,1,2,3]\)，合并相邻且相同的元素后是\([[3,1],[2,3],1,2,3]\)，然后再把第一个\([2,3]\)移动到序列首部，得到\([2,3,3,1,1,2,3]\)，合并后是\([[2,3],[1,2],3]\)，然后再把第一个\([1,2]\)移动到序列首部，得到\([1,2,3]\)。

如果我们每次都删掉两个元素，那么使用的次数肯定是最少的。但是还有一种特殊情况，比如\(R=5,C=2\)的时候按上述方法缩到最后会得到\([5,1,2,3,4,5]\)的序列。这种情况下就把\([1,2,3,4,5]\)移动到序列首部，然后就可以得到\([1,2,3,4,5]\)，这样子也肯定是最优的。

然后因为\(R,C\)的取值范围比较小，直接模拟就完事了。

巴特西

Google Code Jam 2020 Round1B Join the Ranks

题意

解题思路

最新文章

热门文章