当前位置：首页 > news >正文

题解：AtCoder AT_awc0082_b Maximizing the Partition Score of a Lamp Sequence

news 2026/6/14 10:58:24

【题目来源】

AtCoder：B - Maximizing the Partition Score of a Lamp Sequence

【题目描述】

Takahashi has a device with \(N\) lamps arranged in a row. Each lamp is either on (\(1\)) or off (\(0\)).

Denoting the lamps from left to right as \(b_1, b_2, \ldots, b_N\), the state of the device is represented by the integer

\(X = \sum_{i=1}^{N} b_i \cdot 2^{i-1}\)

That is, the \(i\)-th lamp from the left, \(b_i\), corresponds to the \(i\)-th bit from the bottom in the binary representation of \(X\) (the leftmost lamp is the least significant bit).

The following operation is repeatedly performed on Takahashi's device. The operation is performed at most \(K\) times, but may stop midway.

One operation: Check the leftmost lamp of the current sequence.

- If it is on (\(1\)), do nothing and terminate all operations.

- If it is off (\(0\)), remove that lamp from the sequence and append one on (\(1\)) lamp to the right end (the length of the sequence remains \(N\)). If the number of operations has not yet reached \(K\), perform the operation again.

In other words, "as long as the leftmost lamp is off, remove it and append an on lamp to the right end" is performed up to \(K\) times. The process terminates when the leftmost lamp is confirmed to be on, or when \(K\) operations have been performed.

After this process, Aoki brings \(M\) lamp sequences. Each lamp sequence also has length \(N\), and the state of the \(j\)-th lamp sequence is represented by the integer \(Y_j\), using the same bit correspondence as Takahashi's device.

Takahashi chooses a single common split position \(p\) (\(1 \le p \le N - 1\)) for all \(M + 1\) lamp sequences — his own processed lamp sequence and Aoki's \(M\) lamp sequences. Each lamp sequence is divided into the left \(p\) lamps and the right \(N - p\) lamps.

For each lamp sequence, letting the lamps of the left part from left to right be \(c_1, c_2, \ldots, c_p\), its integer value is defined as

\(\sum_{i=1}^{p} c_i \cdot 2^{i-1}\)

Let \(A\) be the sum of the integer values of the left parts of all \(M+1\) lamp sequences.

Similarly, for each lamp sequence, letting the lamps of the right part from left to right be \(d_1, d_2, \ldots, d_{N-p}\), its integer value is defined as

\(\sum_{i=1}^{N-p} d_i \cdot 2^{i-1}\)

(Note that the powers of \(2\) restart from \(2^0\) within the right part.) Let \(B\) be the sum of the integer values of the right parts of all \(M+1\) lamp sequences.

Takahashi chooses the split position \(p\) to maximize \(A + B\). Find the maximum value of \(A + B\).

高桥有一个装置，其中 \(N\) 盏灯排成一行。每盏灯要么亮着（\(1\)），要么熄灭（\(0\)）。

从左到右将灯记为 \(b_1, b_2, \ldots, b_N\)，装置的状态由整数表示

\(X = \sum_{i=1}^{N} b_i \cdot 2^{i-1}\)

也就是说，从左数第 \(i\) 盏灯 \(b_i\) 对应于 \(X\) 二进制表示中从低位开始的第 \(i\) 位（最左边的灯是最低有效位）。

在高桥的装置上重复执行以下操作。操作最多执行 \(K\) 次，但可能中途停止。

一次操作：检查当前序列中最左边的灯。

- 如果它亮着（\(1\)），什么也不做，并终止所有操作。

- 如果它熄灭（\(0\)），从序列中移除该灯，并在右端追加一盏亮着（\(1\)）的灯（序列长度保持为 \(N\)）。如果操作次数尚未达到 \(K\)，则再次执行操作。

换句话说，“只要最左边的灯是熄灭的，就移除它并在右端追加一盏亮着的灯”这一步骤最多执行 \(K\) 次。当确认最左边的灯亮着，或者已执行了 \(K\) 次操作时，过程终止。

在此过程之后，青木带来了 \(M\) 个灯序列。每个灯序列的长度也是 \(N\)，第 \(j\) 个灯序列的状态由整数 \(Y_j\) 表示，使用与高桥装置相同的位对应关系。

高桥为所有 \(M + 1\) 个灯序列——他自己处理后的灯序列和青木的 \(M\) 个灯序列——选择一个公共的分割位置 \(p\)（\(1 \le p \le N - 1\)）。每个灯序列被分成左边的 \(p\) 盏灯和右边的 \(N - p\) 盏灯。

对于每个灯序列，设左边部分从左到右的灯为 \(c_1, c_2, \ldots, c_p\)，其整数值定义为

\(\sum_{i=1}^{p} c_i \cdot 2^{i-1}\)

令 \(A\) 为所有 \(M+1\) 个灯序列左边部分的整数值之和。

类似地，对于每个灯序列，设右边部分从左到右的灯为 \(d_1, d_2, \ldots, d_{N-p}\)，其整数值定义为

\(\sum_{i=1}^{N-p} d_i \cdot 2^{i-1}\)

（注意，在右边部分中，\(2\) 的幂从 \(2^0\) 重新开始。）令 \(B\) 为所有 \(M+1\) 个灯序列右边部分的整数值之和。

高桥选择分割位置 \(p\) 以最大化 \(A + B\)。求 \(A + B\) 的最大值。

【输入】

\(N\) \(K\) \(M\) \(X\)
\(Y_1\) \(Y_2\) \(\ldots\) \(Y_M\)

The first line contains the length of the lamp sequence \(N\), the maximum number of operations \(K\), the number of additional lamp sequences \(M\), and the initial state of Takahashi's device \(X\), separated by spaces.

When \(M \geq 1\), the second line contains \(M\) integers \(Y_1, Y_2, \ldots, Y_M\) representing the states of the additional lamp sequences, separated by spaces.

When \(M = 0\), the second line does not exist.

【输出】

Output the maximum value of \(A + B\) in one line.

【输入样例】

5 2 2 4
3 16

【输出样例】

【核心思想】

问题分析：给定一个 \(N\) 位的二进制数 \(X\)，可以对其最多进行 \(K\) 次循环左移操作（每次将最低位移除并在最高位补 \(1\)，前提是当前最低位为 \(0\)）。然后给定 \(M\) 个 \(N\) 位二进制数 \(Y_j\)，需要选择一个分割位置 \(p\)（\(1 \le p \le N-1\)），将每个数分成低 \(p\) 位和高 \(N-p\) 位，使得所有 \(M+1\) 个数的分割后两部分之和最大。这是一个位运算 + 枚举问题，关键在于理解循环左移操作和位分割的计算方式。
算法选择：
- 循环左移：通过位运算模拟循环左移操作，直到最低位为 \(1\) 或达到 \(K\) 次操作
- 位分割枚举：枚举所有可能的分割位置 \(p\)，计算每个位置的分割得分
- 掩码技巧：使用 (1 << p) - 1 构造低 \(p\) 位全为 \(1\) 的掩码
关键步骤：
- 循环左移处理 \(X\)（最多 \(K\) 次）：
  - 若 \(X\) 的最低位为 \(1\)（x & 1），停止操作
  - 否则：x = (x >> 1) | (1LL << (n - 1))，实现循环左移（移除最低位 \(0\)，在最高位补 \(1\)）
- 加入数组：将处理后的 \(X\) 加入 \(Y\) 数组末尾（y[m + 1] = x）
- 枚举分割位置（\(p = 1\) 到 \(N-1\)）：
  - 构造掩码 t = (1LL << p) - 1，低 \(p\) 位为 \(1\)
  - 对于每个数 \(y[i]\)：
    - 低 \(p\) 位值：y[i] & t
    - 高 \(N-p\) 位值：y[i] >> p（右移 \(p\) 位后，高位的权重重新从 \(2^0\) 开始）
  - 累加所有数的两部分之和：sum += (y[i] & t) + (y[i] >> p)
  - 更新最大答案：ans = max(ans, sum)
- 输出 ans
时间/空间复杂度：
- 时间复杂度：\(O(K + N \cdot M)\)，循环左移 \(O(K)\)，枚举 \(N-1\) 个分割位置，每个位置遍历 \(M+1\) 个数
- 空间复杂度：\(O(M)\)，存储 \(Y\) 数组
位运算的核心思想：
- 循环左移：x = (x >> 1) | (1LL << (n - 1)) 实现了将最低位移除并在最高位补 \(1\)
- 掩码构造：(1 << p) - 1 产生低 \(p\) 位全为 \(1\) 的数，用于提取低 \(p\) 位
- 位分割：y & t 提取低 \(p\) 位，y >> p 提取高 \(N-p\) 位（并自动调整权重）
- 枚举优化：由于 \(N \le 50\)，枚举所有分割位置是可行的
- 适用于二进制位操作、位分割、循环移位类问题

【算法标签】

位运算

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 50, M = 200005;
int n, k, m, x, ans;  // n: 位数，k: 操作数，m: 数组长度，x: 初始值，ans: 最大结果
int b[N];  // 未使用
int y[M];  // 存储数组
signed main()
{cin >> n >> k >> m >> x;  // 输入参数for (int i = 1; i <= m; i++)  // 输入数组cin >> y[i];for (int i = 1; i <= min(k, n); i++)  // 对x进行循环左移操作{if (x & 1LL)  // 如果最低位为1break;  // 停止循环elsex = (x >> 1) | (1LL << (n - 1));  // 循环左移一位}y[m + 1] = x;  // 将处理后的x加入数组for (int p = 1; p < n; p++)  // 遍历每个分割位置{int t = (1LL << p) - 1;  // 掩码，低p位为1int sum = 0;  // 当前分割位置的总和for (int i = 1; i <= m + 1; i++)  // 遍历所有数sum += (y[i] & t) + (y[i] >> p);  // 分割并求和ans = max(ans, sum);  // 更新最大结果}cout << ans << endl;  // 输出结果return 0;
}

【运行结果】