UOJ Logo Universal Online Judge

UOJ

#530. 【美团杯2020】汉明距离

附件下载 统计

蒜斜一旦有作业做不出的时候,就会刷一刷北大算协的公众号。 他最喜欢的一篇推文是 震惊 | 50%程序猿都不会的算法题!。每做出里面的一道题,他就感觉自己的智商提高了一些,作业里的困难也立马迎刃而解。

这一回算协的朋友送给了蒜斜一道非常很有趣的题目。所谓“独IQ++ 不如众IQ++”,蒜斜也把这道题送给了你~

题目描述

对于两个长度为 $m$ 的01串 $\alpha,\beta$,定义它们的汉明距离 $d(\alpha,\beta) = \sum_{i=1}^m |\alpha_i-\beta_i|$。例如,当 $\alpha=001,\beta=100$ 时,$d(\alpha,\beta) = |0-1|+|0-0|+|1-0| = 2$。

现在给出一个神秘01串 $\pi=110010010000111\cdots$,它的长度是 $n=2^{19}$。我把完整的串放在了下发文件$\texttt{pi.txt}$里。

你需要写一个程序,程序输入一个长度为 $n$ 的01串 $\sigma$ 后,需要输出 $d(\pi,\sigma)$ 的估计值:设你输出的整数为 $D$,则 $D$ 需要满足不等式 $D\le 2d(\pi,\sigma)\le 4D$。

特别地,你的程序代码长度不能超过2048B(超出长度限制的代码无法提交)。

输入格式

输入一个长度为 $2^{19}$ 的01串 $\sigma$。

输出格式

输出一个非负整数,表示你给出的 $d(\pi,\sigma)$ 的估计值。

样例一

见下发文件下载。在这个样例中,汉明距离的准确值是 $3$。因此所有被视为正确的输出为 $2,3,4,5,6$。

限制与约定

Small Task: 对于所有 $11000< i \le 2^{19}$ 都满足 $\sigma_i = \pi_i$。包含 $20$ 个数据,只有同时通过这些数据才能得到这一部分的 $35$ 分。

Large Task: 无特殊限制,同样包含 $20$ 个数据。只有同时通过 Small 和 Large 的共计 $40$ 个数据,才能获得这一部分的 $65$ 分。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

下发文件下载