CF496B Secret Combination 题解

Arghariza · 2021-05-25 20:47:23 · 题解

• Solution

每个数字加一不影响数字顺序。

所以直接枚举 S_i,i\in\{1,2,...,n\} 在开头的情况，然后直接把 S 每个元素加到首位为 0 ，与已知的答案串字典序比较即可。

• 优化：

在暴力枚举开头的做法的基础上来一个指针 k ，指向此时数列首元素的下标，将 S_{n+1}\to S_{2n} 将前面的 S_1\to S_{n} 复制一遍，然后从 S_k\to S_{k+n-1} 进行字典序比较即可。

仍是 O(n^2) ，但按理说常数会小一些（（

当然这常数小和不小都能过

如果您懒得打比较字典序的话可以先记录下来，后面再 O(n\log n) 给它排序一遍。

\mathtt\color{lightgreen}AC\ Code