解题思路

1. 问题理解：我们需要根据给定的二进制字符串和其长度 $k$，找到它在 $SK(k)$ 序列中的位置。$SK(k)$ 是一个特定的二进制字符串序列，生成规则如下：

   • $SK(1) = [0, 1]$
   • $SK(n) = 0.SK(n-1) + 1.REV\{SK(n-1)\}$

2. 递归生成序列：可以通过递归生成 $SK(k)$ 序列，然后查找给定字符串的位置。但由于 $k$ 可以达到30，$2^{30}$ 的序列长度会导致内存和时间问题，因此需要更高效的算法。

3. 数学规律：观察 $SK(k)$ 的生成方式，可以发现：

   • $SK(n)$ 的前半部分是 $0.SK(n-1)$，后半部分是 $1.REV\{SK(n-1)\}$。
   • 给定二进制字符串的第一个字符决定它在 $SK(n)$ 的前半部分还是后半部分：
     • 如果是 '0'，则它在 $0.SK(n-1)$ 中，位置为在 $SK(n-1)$ 中的位置。
     • 如果是 '1'，则它在 $1.REV\{SK(n-1)\}$ 中，位置为 $2^{n-1}$ 加上 $SK(n-1)$ 的逆序位置。

4. 递归查找位置：可以利用上述规律递归地计算给定字符串在 $SK(k)$ 中的位置：

   • 如果 $k=1$，直接返回字符串对应的位置（"0"→1，"1"→2）。
   • 否则，根据第一个字符决定递归方向，并调整剩余字符串和位置。

解决代码

#include <iostream>
#include <string>
using namespace std;

// 计算位置的递归函数
int find_position(int k, const string& s) {
    if (k == 1) {
        return s[0] == '0' ? 1 : 2;
    }
    int half = 1 << (k - 1); // 计算2^(k-1)
    if (s[0] == '0') {
        return find_position(k - 1, s.substr(1));
    } else {
        int sub_pos = find_position(k - 1, s.substr(1));
        return half + (half - sub_pos + 1);
    }
}

int main() {
    int N;
    cin >> N;
    for (int case_num = 1; case_num <= N; ++case_num) {
        int k;
        string s;
        cin >> k >> s;
        int pos = find_position(k, s);
        cout << "Poslanec " << case_num << " se posadi na sedadlo cislo " << pos << "." << endl;
    }
    return 0;
}

代码解释

1. 函数 find_position：

   • 递归函数，用于计算给定二进制字符串 s 在 $SK(k)$ 中的位置。
   • 当 $k=1$ 时，直接返回 "0" 或 "1" 对应的位置（1或2）。
   • 对于 $k>1$，根据字符串的第一个字符决定递归方向：
     • 如果是 '0'，则递归处理剩余字符串在 $SK(k-1)$ 中的位置。
     • 如果是 '1'，则递归处理剩余字符串在 $SK(k-1)$ 的逆序中的位置，并加上 $2^{k-1}$。

2. 主函数 solve：

   • 读取输入数据，处理每个测试用例。
   • 调用 find_position 计算位置，并输出结果。

这种方法避免了显式生成整个 $SK(k)$ 序列，通过递归和数学规律高效地找到字符串的位置，适用于较大的 $k$ 值。