[雅礼 2018WC模拟赛] 送你一个集合

题目大意

通信题。

要求实现函数F1(a, b)和F2(h, x), F1返回一个不超过12的正整数, 要求F2(F1(a, b), a)返回0, F2(F1(a, b), b)返回1。

a, b ≤ 920。

解题报告

第一次通信题, 神奇狗逼…

弱化的想法就是F1返回二进制下a和b第一位不相同的位数和a是0是1, 由于a和b二进制下能有10位, 这种表示方法需要10*2=20大小的数字。

观察12和920之间有什么关系…貌似没什么关系, 但是12和924有关系:[latex]C^6_{12} = 924 \ge 920[/latex]。

QAQ

那么可以把[latex][1, 920][/latex]内的数字全部映射到集合[latex]\{x | x \in [1, 2^{12}), bitcnt(x) = 6\}[/latex]内, 其中bitcnt(x)代表x二进制表示下1的位数, 设a, b映射之后的数字为x, y, 那么x和y的二进制低六位必然会有一位不同, 保存不同位置和x在这一位上是0是1即可。

代码

不存在的…