序列合并

Luogu

IDLGP10512

Time1000ms

Memory512MB

DifficultyP4

贪心洛谷原创O2优化位运算洛谷月赛

给定一个长度为 $n$ 的非负整数序列 $\{a_n\}$，你可以进行 $k$ 次操作，每次操作你选择两个相邻的数，把它们合并成它们的按位或。形式化地，一次操作中，你选择一个下标 $i$（$1 \le i < n$），然后把原序列变成 $\{a_1,a_2,\cdots,a_i \operatorname{or} a_{i+1},a_{i+2},\cdots,a_n\}$。求 $k$ 次操作后所有数按位与的最大值。 ## Input 第一行包含两个正整数 $n,k$。第二行包含 $n$ 个非负整数，其中第 $i$ 个非负整数为 $a_i$。 ## Output 输出一行，包含一个正整数，代表答案。 [samples] ## Note **【样例解释】** 一种合法的方案： - 第一次操作，选择第一个数和第二个数合并，序列变为 $\{3,2,3,1\}$。 - 第二次操作，选择第三个数和第四个数合并，序列变为 $\{3,2,3\}$。最终所有数的按位与为 $2$。可以证明不存在更优的方案。 **【数据范围】** - 对于 $25\%$ 的数据，$n \le 20$。 - 对于另外 $25\%$ 的数据，$k=n-2$。对于所有数据，保证 $1 \le k<n \le 2 \times 10^5$，$0 \le a_i < 2^{30}$。

Samples

Input #1

5 2
2 1 2 3 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "序列合并",
    "description": {
      "content": "给定一个长度为 $n$ 的非负整数序列 $\\{a_n\\}$，你可以进行 $k$ 次操作，每次操作你选择两个相邻的数，把它们合并成它们的按位或。 形式化地，一次操作中，你选择一个下标 $i$（$1 \\le i < n$），然后把原序列变成 $\\{a_1,a_2,\\cdots,a_i \\operatorname{or} a_{i+1},a_{i+2},\\cdots,a_n\\}$。 求 $k$ 次操",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10512"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的非负整数序列 $\\{a_n\\}$，你可以进行 $k$ 次操作，每次操作你选择两个相邻的数，把它们合并成它们的按位或。\n\n形式化地，一次操作中，你选择一个下标 $i$（$1 \\le i < n$），然后把原序列变成 $\\{a_1,a_2,\\cdots,a_i \\operatorname{or} a_{i+1},a_{i+2},\\cdots,a_n\\}$。\n\n求 $k$ 次操...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments