题解：P17188 [ICPC 2017 Hong Kong R] Sets

· · 题解

一道找规律题，赛时没加神秘位数限制 RE 了，吃了 7 发罚时，最终拼尽全力无法战胜。

思路

首先我们根据样例不难发现，对于所有的 N\ge 3，任何一个 S_i 都是一个连续的自然数区间。我们定义 S_i 的最小值为 l_i，最大值为 r_i，十分显然地：

\begin{cases} l_i = 2\times l_{i - 1} + 1 \\ r_i = 2\times r_{i - 1} - 1 \end{cases}

:::success[证明]{open} 根据题意，S_i 的最小值肯定为 S_{i - 1} 的最小值与次小值之和，也即 l_{i - 1} + (l_{i - 1} + 1)，最大值同理。 :::

注意到 S_i 的大小是呈指数级增长的，因此我们完全可以使用 O(\log K)（对于 N = 3 时为 O(K)，但题目保证此时 K\le 10^5，因此仍能接受）的复杂度进行暴力维护 l_i,r_i，递推计算 L_K 位于哪个 S_i 中。

这里假设 L_K 在 S_t 中，则我们可以接着计算 L_K 在 S_t 中的下标 pos = K - (\sum_{i=1}^{t - 1} r_i - l_i + 1)，因此 L_K = l_t + pos - 1。

注意 N = 1 时 L = \{1\}，N = 2 时 L = \{1,2,3\}，出现这两种情况时 L 有限，需要判断是否有解。

代码注意事项

代码

import sys

sys.set_int_max_str_digits(0)
data = sys.stdin.read().split()
for i in range(0, len(data), 2):
    n, k = int(data[i]), int(data[i + 1])
    if n == 1:
        print(1 if k == 1 else -1)
    elif n == 2:
        print(k if k <= 3 else -1)
    else:
        l, r, tot = 1, n, 0
        while tot < k:
            tot += r - l + 1
            l, r = l * 2 + 1, r * 2 - 1
            # print(tot, l, r)
        l, r = (l - 1) // 2, (r + 1) // 2
        tot -= r - l + 1
        pos = k - tot
        print(l + pos - 1)