当前位置：首页 > article >正文

机试题——移动01字符串

article 2025/2/13 22:52:01

题目描述

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

输入描述

第一行：一个整数 ( n )，表示 01 字符串的长度，( 10 < n <1024 )。
第二行：一个或多个双字节十六进制数，表示 ( n ) 个 bit 的序列。如果 ( n ) 超过 16，则用多个双字节十六进制数表示，它们之间用空格分割。有效 bit 从第一个十六进制的最高位开始计算，序列尾部如果有无效 bit 则用 1 填充。

输出描述

输出第一行为可以变化为全 1 字符串的方案个数，同一个方向只需要给出移位最少的方案。如果无法变为全 1 字符串，则输出 0。
输出从第二行开始，每两行为一组：
- 第一行为平移方向和平移的次数，用 +X 表示向右移，-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

解题思路

将输入的十六进制数转换为二进制字符串。每个十六进制字符对应4位二进制，通过映射关系将每个十六进制字符转换为对应的二进制字符串。然后根据输入的长度 ( n )，从转换后的二进制字符串中截取前 ( n ) 位，作为目标字符串。

接下来，分析目标字符串中 1 和 0 的位置，分别存储到两个集合 index1 和 index0 中。这些位置信息将用于后续的移动覆盖检查。

为了找到合法的移动方案，分别检查左移和右移的情况：

左移覆盖：从左到右逐位检查，对于每个可能的左移位数 ( i )，检查是否所有 0 的位置 ( t ) 都可以通过左移 ( i ) 位后被 1 覆盖（即检查 ( t + i ) 是否在 index1 中）。如果找到一个合法的左移位数 ( i )，记录该位数并停止进一步检查。
右移覆盖：从左到右逐位检查，对于每个可能的右移位数 ( i )，检查是否所有 0 的位置 ( t ) 都可以通过右移 ( i ) 位后被 1 覆盖（即检查 ( t - i ) 是否在 index1 中）。如果找到一个合法的右移位数 ( i )，记录该位数并停止进一步检查。

输出找到的合法方案数量（左移和右移各算一个方案，即使它们的移动次数相同）。对于每个找到的方案，输出移动方向和移动次数（+X 表示右移，-X 表示左移），并输出一个长度为 ( n ) 的 01 字符串，表示移动后哪些位置的 1 覆盖了原字符串中的 0。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include <sstream>
#include <bitset>
#include <stack>
using namespace std;
string get(string num) {
    string res = "";
    for (int i = 2; i < num.size(); i++) {
        if (num[i] == '0') res += "0000";
        else if (num[i] == '1') res += "0001";
        else if (num[i] == '2') res += "0010";
        else if (num[i] == '3') res += "0011";
        else if (num[i] == '4') res += "0100";
        else if (num[i] == '5') res += "0101";
        else if (num[i] == '6') res += "0110";
        else if (num[i] == '7') res += "0111";
        else if (num[i] == '8') res += "1000";
        else if (num[i] == '9') res += "1001";
        else if (num[i] == 'A') res += "1010";
        else if (num[i] == 'B') res += "1011";
        else if (num[i] == 'C') res += "1100";
        else if (num[i] == 'D') res += "1101";
        else if (num[i] == 'E') res += "1110";
        else if (num[i] == 'F') res += "1111";
    }
    return res;
}
void print(bitset<1024> t,int n) {
    for (int i = 0; i < n; i++) {
        cout << t[i];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string input;
    getline(cin, input); //吃一个回车符号
    getline(cin, input);
    istringstream is(input);
    string data;
    string temp;
    while (is >> temp) {
        data += get(temp);
    }
    // 切割
    data = data.substr(0, n);
    //cout << data << endl;
    set<int> index1;//1的位置
    set<int> index0;//0的位置
    for (int i = 0; i < n; i++) {
        if (data[i]=='1') index1.insert(i);
        else index0.insert(i);
    }
    // 左移 是右边的1覆盖
    int resl = -1;
    for (int i = 0; i < n; i++) {
        bool flag =true;
        for (auto& t : index0) {
            if (!index1.count(t + i)) {
                //没找到
                flag = false;
            }
        }
        if (flag) {
            resl = i;
            break;
        }
    }
    // 右移 是左边的1覆盖
    int resr= -1;
    for (int i = 0; i < n; i++) {
        bool flag = true;
        for (auto& t : index0) {
            if (!index1.count(t - i)) {
                //没找到
                flag = false;
            }
        }
        if (flag) {
            resr = i;
            break;
        }
    }
    if (resl == -1 && resr == -1) {
        cout << 0;
        return 0;
    }
    cout << (resl!=-1) +(resr!=-1)<<"\n";
    if (resr != -1) {
        cout << "+" << resr << '\n';
        for (int i = 0; i < n; i++) {
            if (index0.count(i + resr)) {
                cout << "1";
            }
            else cout << "0";
        }
        cout << "\n";
    }
    if (resl != -1) {
        cout << "-" << resl << '\n';
        for (int i = 0; i < n; i++) {
            if (index0.count(i - resl)) {
                cout << "1";
            }
            else cout << "0";
        }
    }
}