1 solutions
-
0
题目解释
题目要求我们将一个用十六进制数表示的二进制序列(长度为 的 字符串)通过左右平移一个相同的字符串,用其中的 覆盖掉原字符串中的 ,从而使原字符串变成全 。输入包含一个整数 (表示二进制字符串的长度)和多个十六进制数(用空格分隔,表示这个 字符串的内容)。要求输出能使字符串变为全 的所有平移方案,方案应优先输出右移,且每个方向只需输出移动次数最少的方案。如果无法完成覆盖,输出 。
思路:
先将十六进制转成二进制,然后要么往左移动若干位,要么往右移动若干位。枚举这两种情况即可。注意二进制可能很大,无法直接使用内置int或者long类型。C++需要使用bitset,python直接使用内置的大整数。Java需要手写bitset.
题解
这道题的核心思想是将一个用十六进制表示的字符串转换为二进制,然后通过左右移动这个二进制串,尝试用其中的
1
来覆盖原二进制串中的0
,最终希望使其变为全1
的序列。具体操作步骤如下:- 输入处理:我们首先将输入的十六进制数转换为二进制数表示的字符串,并将其存储在一个大小为
1024
的bitset
中(C++ 中用bitset
存储)。 - 构造目标序列:目标是一个全
1
的二进制字符串,所以我们用另一个bitset
,将它的所有位置都设为1
。 - 左右移位操作:
- 向左移动:将字符串向左移动若干位,检查移动后的字符串是否能够覆盖所有的
0
。 - 向右移动:同样地,检查右移若干位后的情况。
- 向左移动:将字符串向左移动若干位,检查移动后的字符串是否能够覆盖所有的
- 结果计算:枚举左右移动的所有可能位置,找出能够使原字符串变为全
1
且移动次数最少的方案。如果存在多个方案,优先输出右移方案。如果不能通过平移使字符串全为1
,则输出0
。 - 输出:最后输出移动的方向、移动的次数,以及覆盖原二进制串时的具体情况。
代码详解
- 输入转换:输入十六进制字符串,先将其转换为对应的整数,然后再将其转为二进制位并存储到
bitset
中。 - 移位操作:分别枚举右移和左移的情况,通过移位后与目标全
1
串进行位运算,检查能否通过移位变为全1
。 - 结果输出:根据找到的最优右移或左移方案,输出移动次数及最终能覆盖的位置。
具体见代码注释
代码
python
利用大整数性质解决
C++
bitset实现
- 输入处理:我们首先将输入的十六进制数转换为二进制数表示的字符串,并将其存储在一个大小为
- 1
Information
- ID
- 18
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- # Submissions
- 57
- Accepted
- 9
- Uploaded By