DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

数据传输

返回题目

题解

使用长度为7的汉明码,位置从左到右从1开始编号。将原串的四个比特依次放在第 3,5,6,73,5,6,73,5,6,7 位。

将这四个位置中比特为1的位置编号全部异或,得到 xxx。写成 x=(b2b1b0)2x=(b_2b_1b_0)_2x=(b2​b1​b0​)2​,再将 b0,b1,b2b_0,b_1,b_2b0​,b1​,b2​ 分别放到第 1,2,41,2,41,2,4 位。完整字符串中所有值为1的位置编号的异或和即为 x⊕x=0x\oplus x=0x⊕x=0。

设传输时第 kkk 位被翻转。对收到的字符串中所有值为1的位置编号求异或,相当于增加或去掉一次 kkk,所以结果恰好为 kkk。再次翻转该位,再读取第 3,5,6,73,5,6,73,5,6,7 位即可。由于恰好翻转一位,这种策略下收到的异或结果总在1到7之间。

传输长度始终为7,满足限制。校验位1,2,4出错和数据位3,5,6,7出错都能用同一方法恢复。

朴素恢复方法是枚举16种原串并编码,寻找与受损字符串恰好相差一位的码字。任意两个不同码字的距离至少为3:距离为1会导致它们的校验异或值不同;距离为2则要求两个不同位置编号的异或为0,矛盾。因此候选码字唯一。由于输入规模固定,朴素解法也能通过全部条件。

主解法时间和额外空间均为 O(1)O(1)O(1)。朴素解法至多进行 16⋅7=11216\cdot7=11216⋅7=112 次比特比较,也为 O(1)O(1)O(1)。位置异或值至多为7,原串的数值至多为15,8位掩码至多为255,所有整数运算都在有符号64位范围内。

Solution written by GPT6