[COCI 2022/2023 #5] Diskurs

Luogu

IDLGP9178

Time2000ms

Memory512MB

DifficultyP4

动态规划 DP2022位运算COCI（克罗地亚）

给你 $n$ 个非负整数 $a_1, a_2, \cdots a _n$，任何一个都小于 $2^m$。对于其中的每一个数，你都要找出它与数组中其他元素之间的最大哈明距离。两个非负整数的哈明距离被定义为在这些数字的二进制表示中，它们之间有多少个不同的位置（如果有必要，加上前导零）。形式上，对于每个 $i$ 求： $$\max\limits_{1\leq j\leq n} \operatorname{hamming}(a_i,a_j)$$ ## Input 第一行包含两个整数 $n$ 和 $m(1\leq n\leq 2^ m,1\leq m\leq 20)$。第二行包含 $n$ 个数字 $a_i(0 \leq a_i < 2^ m)$。 ## Output 一行 $n$ 个数，第 $i$ 个数表示 $a_i$ 与数组中其他元素之间的最大哈明距离。 [samples] ## Note | Subatask | $\text{pts}$ | 限制 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 是样例 | | $1$ | $20$ | $m\leq 10$ | | $2$ | $25$ | $m\leq 16$ | | $3$ | $25$ | 无 |

Samples

Input #1

4 4
9 12 9 11

Output #1

2 3 2 3

Input #2

4 4
5 7 3 9

Output #2

2 3 2 3

Input #3

4 4
3 4 6 10

Output #3

3 3 2 3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2022/2023 #5] Diskurs",
    "description": {
      "content": "给你 $n$ 个非负整数 $a_1, a_2, \\cdots a _n$，任何一个都小于 $2^m$。 对于其中的每一个数，你都要找出它与数组中其他元素之间的最大哈明距离。 两个非负整数的哈明距离被定义为在这些数字的二进制表示中，它们之间有多少个不同的位置（如果有必要，加上前导零）。 形式上，对于每个 $i$ 求： $$\\max\\limits_{1\\leq j\\leq n} \\operat",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9178"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给你 $n$ 个非负整数 $a_1, a_2, \\cdots a\n_n$，任何一个都小于 $2^m$。\n\n对于其中的每一个数，你都要找出它与数组中其他元素之间的最大哈明距离。\n\n两个非负整数的哈明距离被定义为在这些数字的二进制表示中，它们之间有多少个不同的位置（如果有必要，加上前导零）。\n\n形式上，对于每个 $i$ 求：\n\n$$\\max\\limits_{1\\leq j\\leq n} \\operat...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments