CF1641B Repetitions Decoding

· · 题解

Preface

骄傲地使用多年没写的链表过了此题。

Analysis

首先，如果原序列中某一种值出现了奇数次肯定不行。我们下面构造偶数必然可行。

我们先观察一个样例：

look :1 2 3 1 3 4 2 4
step1:1 2 3 1(2 2)3 4 2 4
step2:1 2 3 1 2(3 3)2 3 4 2 4
look :1 2 3 1 2 3|3 2 3 4 2 4
step3:1 2 3 1 2 3|3 2 3(2 2)4 2 4
end  :1 2 3 1 2 3|3 2 3 2|2 4 2 4

也就是说，我们找到 a_1 之后第一个 a_i=a_1，然后在 a_i 位置后操作使得 a[i,2i-1]=a[1,i-1]，接下来从 a_{2i} 开始（每次操作后重新标号）重复此操作即可。

由于每种值均出现偶数次，此方法必然可行。并且设 f_i 表示原长度为 i 的操作总次数：

f_0=0 \\ f_n\le n-2+f(n-2) \end{cases}

易知 f_n\le\dfrac{n(n-2)}{4}，满足题意。

我们用链表也能够轻松让时间复杂度同阶于操作数。

Code

Link