题目解释

题目要求我们将一个用十六进制数表示的二进制序列（长度为 $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); // 输出移动后的覆盖情况
    }
}

题目内容

小明突然收到一封信，里面有一个一个十六进制数，信里提到，这个十六进制数表示一个长度为 $n$ 的 $01$ 字符串。

信中写道，你能否通过左右移动一个和该$01$字符串相同的字符串，来用$1$覆盖掉原字符串中的$0$（$0$ 并不会覆盖 $1$），使得原字符串变成一个长度为 $n$ 的全 $1$ 字符串。如果可以请将方案写出，如果同时存在多个方案，请写下移动次数最少的方案。

小明一直在思考这个问题该如何解决，你能帮助小明解决这个问题吗？

输入描述

输入第一行为 $01$ 字符串的长度 $n$ 。（ $10\le n\le 1024$ ）

输入第二行为 $n$ 个bit的序列，用双字节十六进制数表示，如果 $n$ 超过 $16$ ，则用多个双字节十六进制表示，它们之间用空格分割。

有效bit从第一个十六进制的最高位开始计算，序列尾部如果有无效bit则用 $1$ 填充。

输出描述

输出第一行为可以变化为全 $1$ 字符串的方案个数，同一个方向只需要给出移位最少的方案。如果无法变为全 $1$ 字符串，则输出 $0$ 。

输出从第二行开始，每两行为一组。

第一行为平移方向和平移的次数，用 +X 表示向右为 + ，向左为 - ;

第二行为一个长度为 $n$ 的 $01$ 字符串，表示移动后字符串中哪些位置的 $1$ 将覆盖原始位置的 $0$ ；

如果存在多个方案，先输出向右移动的方案

样例

样例一

输入

13
0xEEEE

输出

2
+1
0010001000100
-1
0000100010001

样例解释

输入的十六进制数为:0xEEEE , 二进制为1110111011101110 , 截取$n=13$ 得到1110111011101

肉眼观察可以发现有两种方案，分别是右移 $1$ 个位置和左移 $1$ 个位置。对应的 $01$ 连续字符序列表示移动后字符串中哪些位置的 $1$ 将覆盖原始位置的 $0$ 。

样例二

输入

20
0xEEEF 0x3FFF

输出

2
+2
01000100010000110000
-2
00000100010001000011

样例解释

输入的十六进制数 0xEEEF 0x3FFF，截取前$n=20$位，转换为二进制序列为 11101110111011110011 ；

肉眼观察可以发现有两种方案，左移 $2$ 个位置 和 右移两个位置 。 对应的 $01$ 连续字符序列表示移动后字符串中哪些位置的 $1$ 将覆盖原始位置的 $0$ 。