#1475. Can You Hear My Voice?

Can You Hear My Voice?

题目背景

这是一道通信题。

通信题的定义为,你需要完成两个不同的程序(或者同一个程序内的两个函数),其中程序A能获得输入,并且向程序B传递指定格式的有限信息。而程序B需要根据程序A传递过来的信息计算并输出答案。 这种题型目前比较新,并且不常见于日常训练,因此只作为兴趣拓展配置一道范例题目在此处。

题目描述

给定两个长度相等(不超过 10610^6)且至多有一个位置的字符不同的 01 串 S,TS,T(下标从 11 开始)。Alice 只知道 SS,Bob 只知道 TT

Bob 想要确定 S,TS,T 字符不同的那个位置。为了达成这一目的,Alice 决定偷偷帮助他。

具体来说,Alice 可以向 Bob 传递一个整数 XX,满足 X[0,220)X \in [0, 2^{20})

特别地,如果 S=TS=T,Bob 应返回 0。

实现细节

您需要在一个程序内实现两个函数

int Alice(std::string S);
  • 在单组测试点中,该函数只会被调用一次。
  • SS:长度不超过 10610^6std::string 数组,表示题目中的 SS
  • 该函数返回一个满足 X[0,220)X \in [0, 2^{20}) 的整数 XX,表示 Alice 给 Bob 传递的数。
int Bob(std::string T, int X);
  • 在单组测试点中,该函数只会被调用一次。
  • TT:长度不超过 10610^6std::string 数组,表示题目中的 TT
  • XX:满足 X[0,220)X \in [0, 2^{20}) 的整数 XX,表示 Alice 给 Bob 传递的数。
  • NNTT 的长度,该函数返回一个满足 P[0,N]P \in [0, N] 的整数 PP,表示 S,TS,T 字符不同的位置。如果 S=TS=T,返回 0。评分程序会根据返回内容与正确答案对比进行打分。

您不需要,也不应该实现主函数。

在最终评测时,对于单组测试点,上述两个函数会在不同的进程中运行。也就是说,你不能通过全局变量等方式试图在函数间传递信息。

样例

0101011
0100011
4