题目解释

题目要求我们将一个用十六进制数表示的二进制序列（长度为 $n$ 的 $01$ 字符串）通过左右平移一个相同的字符串，用其中的 $1$ 覆盖掉原字符串中的 $0$，从而使原字符串变成全 $1$。输入包含一个整数 $n$（表示二进制字符串的长度）和多个十六进制数（用空格分隔，表示这个 $01$ 字符串的内容）。要求输出能使字符串变为全 $1$ 的所有平移方案，方案应优先输出右移，且每个方向只需输出移动次数最少的方案。如果无法完成覆盖，输出 $0$。

思路:

先将十六进制转成二进制，然后要么往左移动若干位，要么往右移动若干位。枚举这两种情况即可。注意二进制可能很大，无法直接使用内置int或者long类型。C++需要使用bitset,python直接使用内置的大整数。Java需要手写bitset.

题解

这道题的核心思想是将一个用十六进制表示的字符串转换为二进制，然后通过左右移动这个二进制串，尝试用其中的 1 来覆盖原二进制串中的 0，最终希望使其变为全 1 的序列。具体操作步骤如下：

1. 输入处理：我们首先将输入的十六进制数转换为二进制数表示的字符串，并将其存储在一个大小为 1024 的 bitset 中（C++ 中用 bitset 存储）。
2. 构造目标序列：目标是一个全 1 的二进制字符串，所以我们用另一个 bitset，将它的所有位置都设为 1。
3. 左右移位操作：
   • 向左移动：将字符串向左移动若干位，检查移动后的字符串是否能够覆盖所有的 0。
   • 向右移动：同样地，检查右移若干位后的情况。
4. 结果计算：枚举左右移动的所有可能位置，找出能够使原字符串变为全 1 且移动次数最少的方案。如果存在多个方案，优先输出右移方案。如果不能通过平移使字符串全为 1，则输出 0。
5. 输出：最后输出移动的方向、移动的次数，以及覆盖原二进制串时的具体情况。

代码详解

1. 输入转换：输入十六进制字符串，先将其转换为对应的整数，然后再将其转为二进制位并存储到 bitset 中。
2. 移位操作：分别枚举右移和左移的情况，通过移位后与目标全 1 串进行位运算，检查能否通过移位变为全 1。
3. 结果输出：根据找到的最优右移或左移方案，输出移动次数及最终能覆盖的位置。

具体见代码注释

代码

python

利用大整数性质解决

n = int(input())
arr = list(input().split())
# 十六进制转二进制
brr = [bin(int(x, 16))[2:].zfill(16) for x in arr]
# 拼接成一个字符串
s = ''.join(brr)[:n]
# 二进制转十进制
raw = int(s, 2)
mask = (1 << n) - 1
# 求右移的最少变成全1的次数
right_move_num = 10**9
for i in range(n):
    if (raw | (raw >> i)) == mask:
        right_move_num = i
        break
# 求左移的最少变成全1的次数
left_move_num = 10**9
for i in range(n):
    if ((raw | (raw << i)) & mask) == mask:
        
        left_move_num = i
        break
# 如果左右移都达不到要求
min_move_num = min(left_move_num, right_move_num)
if min_move_num == 10**9:
    print(0)
    exit()
res = []
# 如果右移是最少次数
if right_move_num == min_move_num:
    res.append("+" + str(right_move_num))
    # 获得二进制里的0的位置
    zero_pos = [n - i - 1 for i in range(n) if s[i] == '0']
    res_mask = 0
    # 通过位运算得到将0变成1的mask
    for i in range(len(zero_pos)):
        res_mask |= 1 << (zero_pos[i] + right_move_num)
    res.append(str(bin(res_mask)[2:].zfill(n)))
if left_move_num == min_move_num:
    res.append("-" + str(left_move_num))
    # 获得二进制里的0的位置
    zero_pos = [n - i - 1 for i in range(n) if s[i] == '0']
    res_mask = 0
    # 通过位运算得到将0变成1的mask
    for i in range(len(zero_pos)):
        res_mask |= 1 << (zero_pos[i] - left_move_num)
    res.append(bin(res_mask)[2:].zfill(n))
print(len(res) // 2)
print('\n'.join(res))

C++

bitset实现

#include <bits/stdc++.h>
using namespace std;

// 定义两个bitset，a用于存储原始的二进制串，b用于表示目标的全1串
bitset<1024> a, b;
int n; // n表示二进制串的长度
string s;

// 打印bitset中从低位到高位的前n位
void print(bitset<1024> x) {
    for(int i = 0 ; i < n ; i ++) {
        cout << x[i]; // 按顺序输出每一位
    }
    cout << endl;
}

int main() {
    cin >> n; // 输入n，表示二进制串的长度
    int idx = 0; // 用于记录当前处理到的bit位置

    // 逐个读取十六进制表示的输入
    while(cin >> s) {
        int now = 0; // 用于存储转换后的整数值
        for(int i = 2 ; i < s.size() ; i ++) { // 跳过前缀"0x"
            if(s[i] >= '0' && s[i] <= '9') { // 如果是数字字符
                now = now * 16 + s[i] - '0'; // 转换为相应的整数值
            } else { // 如果是字母字符（A-F）
                now = now * 16 + s[i] - 'A' + 10; // 转换为相应的十进制值
            }
        }

        // 将转换后的整数转为二进制并存储到bitset中
        stack<int> st;
        for(int i = 0 ; i < 16 ; i ++) { // 逐位提取二进制位
            st.push(now & 1); // 取最低位
            now >>= 1; // 右移1位
        }
        
        // 将栈中的二进制位逐位存储到bitset a 中
        for(int i = 0 ; i < 16 && idx < n ; i ++, idx++) {
            a[idx] = st.top(); // 从栈顶取出二进制位
            st.pop();
        }
    }

    // 构造目标全1的二进制串
    for(int i = 0 ; i < n ; i ++) {
        b[i] = 1; // b的每一位都设置为1
    }

    // 用于记录左移和右移的最小移动次数
    int ans = 0; // 记录总方案数
    int ans1 = -1, ans2 = -1; // 分别记录左移和右移的最小位移数

    // 枚举右移情况
    for(int i = 0 ; i < n ; i ++) {
        if((a << i & b | a).count() == n) { // 右移i位后，检查是否可以全1
            ans1 = i; // 记录右移的最小位移数
            ans++;
            break; // 只需要找到最少的位移次数，找到即可跳出
        }
    }

    // 枚举左移情况
    for(int i = 0 ; i < n ; i ++) {
        if((a >> i & b | a).count() == n) { // 左移i位后，检查是否可以全1
            ans2 = i; // 记录左移的最小位移数
            ans++;
            break; // 只需要找到最少的位移次数，找到即可跳出
        }
    }

    // 如果没有任何平移方案，或a本身已是全1串，直接输出0
    if(ans == 0 || a.count() == n) {
        cout << 0 << endl;
        return 0;
    }

    // 输出可以使其全1的平移方案数
    cout << (ans1 != -1) + (ans2 != -1) << endl;

    // 输出右移方案
    if(ans1 != -1) {
        cout << "+" << ans1 << endl;
        print((a ^ b) >> ans1); // 输出移动后的覆盖情况
    }

    // 输出左移方案
    if(ans2 != -1) {
        cout << "-" << ans2 << endl;
        print((a ^ b) << ans2); // 输出移动后的覆盖情况
    }
}