[语言月赛 202401] 二进制与一

Luogu
IDLGB3919
Time1000ms
Memory512MB
DifficultyP2
2024O2优化位运算循环结构语言月赛
给定一个正整数 $n$,以及操作次数 $q$。对于每次操作,给出一个正整数 $k$,要求:让 $n$ 加上一个非负整数 $x$,使得 $n$ 在二进制下的第 $k$ 位(从右往左数)是 $1$,并在符合要求的情况下,令 $x$ 最小。 请注意,每次操作都会让 $n$ 变为 $n + x$,会影响后续操作。 小山需要求出,所有的 $x$ 之和是多少。 ## Input 输入共 $q + 1$ 行。 第一行两个整数 $n$ 和 $q$。 接下来 $q$ 行,每行一个正整数 $k$,表示要让 $n$ 在二进制下从右往左数的第 $k$ 位是 $1$。 ## Output 一行一个整数,表示所有的 $x$ 之和。 [samples] ## Note ### 样例 1 说明 $5$ 在二进制下是 $101$。 - 对于第一次操作,需要让 $101$ 的第二位变为 $1$,则需让 $101$ 加上 $1$,变为 $110$; - 对于第二次操作,需要让 $110$ 的第三位是 $1$,由于 $110$ 的第三位本身就是一,所以无需改变; - 第三次操作同理,需要让 $110$ 加上 $2$。 最终输出结果是 $1+0+2=3$。 ### 数据规模与约定 对于 $100\%$ 的数据,$1\le n < 2^{32},1\le q\le 10^5,1 \le k\le 32$。 | 测试点编号 | $n$ | $q$ | $k$ | | :-: | :-: | :-: | :-: | | $1$ | $\leq 4$ | $\leq 10$ | $\leq 2$ | | $2, 3$ | $\leq 4$ | $\leq 10$ | $\leq 32$ | | $4, 5$ | $\leq 1024$ | $\leq 1000$ | $\leq 10$ | | $6, 7$ | $< 2 ^ {32}$ | $\leq 10$ | $\leq 32$ | | $8 \sim 10$ | $< 2 ^ {32}$ | $\leq 10 ^ 5$ | $\leq 32$ |
Samples
Input #1
5 3
2
3
4
Output #1
3
API Response (JSON)
{
  "problem": {
    "name": "[语言月赛 202401] 二进制与一",
    "description": {
      "content": "给定一个正整数 $n$,以及操作次数 $q$。对于每次操作,给出一个正整数 $k$,要求:让 $n$ 加上一个非负整数 $x$,使得 $n$ 在二进制下的第 $k$ 位(从右往左数)是 $1$,并在符合要求的情况下,令 $x$ 最小。 请注意,每次操作都会让 $n$ 变为 $n + x$,会影响后续操作。 小山需要求出,所有的 $x$ 之和是多少。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3919"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个正整数 $n$,以及操作次数 $q$。对于每次操作,给出一个正整数 $k$,要求:让 $n$ 加上一个非负整数 $x$,使得 $n$ 在二进制下的第 $k$ 位(从右往左数)是 $1$,并在符合要求的情况下,令 $x$ 最小。\n\n请注意,每次操作都会让 $n$ 变为 $n + x$,会影响后续操作。\n\n小山需要求出,所有的 $x$ 之和是多少。\n\n## Input\n\n输入共 $q + 1$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments