【题解】配伍分程 —— 二分答案 + 按位与贪心

代码来源：midau/25/1/1.cpp
算法标签：二分答案、位运算（按位与）、贪心、对拍
难度：普及+/提高

一、题意

有 $N$ 种制剂，按服用顺序编号 $1,2,\dots,N$，第 $i$ 种有个正整数特征码 $A_i$。

一次完整分程是选定疗程数 $k$（$1 \le k \le L$）和一组分割边界

$$
0 = b_0 < b_1 < \cdots < b_k = N,
$$

第 $j$ 个疗程包含编号 $b_{j-1}+1$ 到 $b_j$ 的连续一段制剂。也就是说，把整个序列切成不超过 $L$ 段连续非空子段，恰好覆盖所有制剂。

一个疗程的共同特征码 = 这一段内所有 $A_i$ 的按位与（AND）。

一次分程的稳定值 = 这 $k$ 个共同特征码中的最小值。

求：在所有合法分程中，稳定值的最大值。

输入格式

第一行两个整数 $N, L$。

第二行 $N$ 个整数 $A_1 \dots A_N$。

输出格式

一个整数，最大稳定值。

样例

输入

5 5
1 2 3 4 5

输出

1

样例解释：$L=5$，上限宽松，可以把 5 种制剂各成一个疗程，共同特征码依次是 $1,2,3,4,5$，最小值 $1$。

为什么不能更大？含制剂 1 的疗程一定是「若干个 $A_i$ 与 $A_1=1$ 的按位与」，结果只能是 $0$ 或 $1$，所以稳定值恒 $\le 1$。取到 $1$ 即最优。

下图对比了两种分程：切法 A 让 5 种制剂各成一疗程，稳定值 $=1$；切法 B 把制剂 1、2 合并（$1,&,2=0$），稳定值掉到 $0$。可见分段方式直接决定稳定值——这正是我们要最优化的东西。

数据范围与子任务

• $1 \le N \le 10^5$，$1 \le L \le N$，$1 \le A_i \le 10^9$。

其中特殊性质 A 保证 $L=1$（只能整体一段），B 保证 $L=N$（每种制剂都能单独成段）。

数据范围直接告诉我们：$O(N \log A)$ 才稳。看到“最大化最小值”+ 连续分段 + $N=10^5$，几乎可以确定是二分答案。

二、朴素思路：枚举所有分程

相邻两种制剂之间有 $N-1$ 个“缝隙”，每个缝隙要么切开、要么不切。用一个二进制掩码 mask 表示：

• mask 第 $i$ 位为 1 → 在第 $i$ 个缝隙处切开。

于是总共 $2^{N-1}$ 种分程。对每种：

1. 数段数 $k=1+\operatorname{popcount}(mask)$，若 $k>L$ 直接跳过；
2. 从左到右维护每段的按位与，记录所有段权值的最小值 $mn$；
3. ans = max(ans, mn)。

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

// 暴力：枚举所有划分（用 01 序列表示每个缝隙断/不断），一定正确
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    int n, L;
    cin >> n >> L;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    ll ans = 0;
    // 有 n-1 个缝隙，二进制位表示是否在此处切开
    for (int mask = 0; mask < (1 << (n - 1)); mask++)
    {
        int k = 1 + __builtin_popcount(mask);   // 段数
        if (k > L) continue;
        ll mn = LLONG_MAX, cur = a[0];
        for (int i = 0; i < n - 1; i++)
        {
            if (mask >> i & 1) {                // 切开：结算当前段
                mn = min(mn, cur);
                cur = a[i + 1];
            } else {                            // 不切：并入当前段
                cur &= a[i + 1];
            }
        }
        mn = min(mn, cur);                      // 结算最后一段
        ans = max(ans, mn);
    }
    cout << ans << "\n";
    return 0;
}

复杂度 $O(2^{N} \cdot N)$，只能过 $N \le 20$（测试点 1～3 的 15 分）。它的价值在于作为对拍的“标准答案”。

注意 ans 初值取 $0$（而非 $-\infty$）：按位与非负，且 $k=1$ 总合法，所以答案一定 $\ge 0$。这也暗示答案可能为 0。

三、正解：二分答案

3.1 关键观察——单调性

问题等价于：求最大的 $m$，使得存在一种分程，让每个疗程的共同特征码都 $\ge m$。

把「存在分程使每段按位与都 $\ge m$」记作命题 $P(m)$。它有单调性：

若 $P(m)$ 为真，则对任意 $m’ \le m$，$P(m’)$ 也为真。

原因很朴素：让 $P(m)$ 成立的那组分程方案，原封不动拿来用，每段都 $\ge m \ge m’$，自然满足 $\ge m’$。

所以可行域是前缀 $[0, m^]$，$m^$ 就是答案 → 二分 $m$。

下图把这条单调性画了出来：$m$ 轴上一段是“可行”，一段是“不可行”，交界处 $m^*$ 就是答案。二分就是在不断把区间往交界处收缩。

3.2 二分区间

• 下界 $lo = 0$。答案可能为 0，绝不能取 1！（本题最大坑，见第七节）

• 上界 $hi = \min_i A_i$。因为一段的按位与一定 $\le$ 段内每个数：

  按位与只会“抹掉”二进制里的 1，不会凭空造 1，所以 $x ,&, y \le x$。若某段含全局最小值 $A_{\min}$，则该段按位与 $\le A_{\min}$，从而稳定值 $w \le A_{\min}$。

  故 $m \le A_{\min}$，取 $hi = A_{\min}$。

3.3 二分模板（求最大值）

while (l < r) {
    ll mid = (l + r + 1) / 2;     // 上取整，防死循环
    if (check(mid)) l = mid;      // 可行 -> 往大找
    else            r = mid - 1;  // 不可行 -> 往小找
}
// 最终 l == r 即答案

为什么 mid 要 (l + r + 1) / 2（上取整）？ 因为这是“保留左端点”的二分：可行时 l = mid。若用 mid = (l+r)/2，当 l=3, r=4 时 mid=3，l 被赋回 3，区间不缩小 → 死循环。上取整后 mid=4，区间必缩。求最大值的标准写法，务必记牢。

四、判定函数 check(m) —— 贪心

骨架搭好，核心是：给定 $m$，如何判断能否切成 $\le L$ 段且每段按位与都 $\ge m$？

等价于求「每段都 $\ge m$ 时的最少段数 $\text{cnt}{\min}$」，若 $\text{cnt}{\min} \le L$ 则可行。

4.1 贪心策略

从左到右扫描，维护“当前这段”的按位与：

能并就并：只要把下一个数并入当前段后，段按位与仍 $\ge m$，就并进来，让当前段尽量长；一旦并入后会跌破 $m$，就必须在此处切开，另起一段。

下图以 $A=[1,2,3,4,5]$、$m=2$ 为例，完整演示了 check 的扫描过程（每行是一次 i 的推进）。绿色格表示这一步发生了合并，值被替换为合并后的按位与：

4.2 为什么贪心正确？

关键性质：按位与关于“往集合里加元素”单调不增。

往一段里多加一个数，只会让这段的按位与不变或变小，绝不会变大。

于是“一段最多能延伸到哪儿”只由它自己的前缀按位与决定，与后面怎么切无关。而越早切开，只会让剩余元素更多、段数不减少（交换论证：任取一个最优分程，若它比贪心更早切开，把它的切点后移成贪心的位置，对应段按位与只会更大或相等、段数只会更少或相等，故贪心不劣）。因此“尽量往后并”得到的就是最少段数。

4.3 一个巧妙的数组实现

代码并没有真的“切开”，而是用合并来数段数：

• 初始把每个数各自当作一段，段数 cnt = N；
• 从左到右扫相邻格，若 a[i] & a[i+1] >= m，说明这两段能合并，于是 cnt--，并把合并结果写回 a[i+1]：

if ((a1[i] & a1[i + 1]) >= m) {
    cnt--;
    a1[i + 1] = a1[i] & a1[i + 1];
}

• 最终 cnt 就是尽可能合并后的段数 = 最少段数。

必须把结果写回 a[i+1]！ 因为 a[i+1] 代表“从某起点一路 AND 到这里”的累积值，下次比较 a[i+1] & a[i+2] 用的必须是这个累积值，而非原始值。这是手写最易漏的一步。

五、完整参考代码（1.cpp）

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;
ll n, len, a[maxn];
ll mina = LONG_LONG_MAX;               // 全局最小值，作为二分上界

// 判定：能否把序列切成 <= len 段，使每段按位与都 >= m
bool check(ll m)
{
    ll a1[maxn] = {0};
    for (ll i = 1; i <= n; i++)        // 拷贝一份，避免污染原数组
        a1[i] = a[i];

    ll cnt = n;                        // 初始：每个数各成一段
    for (ll i = 1; i < n; i++)
    {
        // 若当前段与下一段合并后仍 >= m，就合并（贪心：能并就并）
        if ((a1[i] & a1[i + 1]) >= m)
        {
            cnt--;
            a1[i + 1] = a1[i] & a1[i + 1];   // 累积按位与写回下一格
        }
    }

    if (cnt > len || m > mina) return 0;     // 段数超限 or 超过上界 => 不可行
    else return 1;
}

ll bs_find(ll l, ll r)                 // 二分最大的可行 m
{
    while (l < r)
    {
        ll mid = (l + r + 1) / 2;      // 上取整，防死循环
        if (check(mid)) l = mid;       // 可行 -> 往大找
        else            r = mid - 1;   // 不可行 -> 往小找
    }
    return l;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> len;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i];
        mina = min(a[i], mina);        // 维护全局最小值
    }
    cout << bs_find(0, mina + 1);      // 下界从 0 开始（答案可能为 0！）
    return 0;
}

复杂度

• 一次 check：$O(N)$；
• 二分次数：$\lceil \log_2(A_{\min}+1) \rceil \le 30$；
• 总复杂度 $O(N \log A_{\min})$，$N \le 10^5$、$A_i \le 10^9$ 完全够用。

六、多解法对比

为什么贪心优于 DP？ 因为“段内按位与”具有前缀单调性：固定左端点，段越长按位与越小、越短越大。于是“给定 $m$ 是否可行”这个判定问题能线性贪心解决，无需 DP 记录所有“切几段”的状态。先用二分把「最优化」变成「判定」，再用单调性把「判定」变成「贪心」，是本题精髓，也是这类题的通法。

七、易错点 / 踩坑合集

1. 二分下界必须取 0。 答案可能为 0。本仓库早期草稿 1b.cpp 写成 bs_find(1, mina+1)，答案为 0 时会错误输出 1；最终 1.cpp 改成 bs_find(0, mina+1) 才正确。

2. 合并后必须把结果写回 a[i+1]。 漏了它，后续比较用的是原始值，贪心失效。

3. check 里要拷贝数组。 判定会修改累积值，直接改原数组会让多次二分互相污染。代码里 ll a1[maxn] = {0}; 每次重新拷贝。

4. 二分上取整 (l+r+1)/2。 求最大值时不写 +1，l=r-1 时会死循环。

5. m > mina 的短路。 在 check 里直接判不可行，既让右端点安全地取 mina+1，又是一层剪枝。

6. 边界 N=1。 只有一段，check 直接通过（cnt=1 \le L），输出 bs_find(0, A_1+1)；上界 mina+1 虽有冗余，但被第 5 条的短路挡掉，不会出错。

7. 数据范围与类型。 用 long long；mina 初值用 LONG_LONG_MAX，防止输入全是超大数时上界被压错。

8. L=1（性质 A）时。 只能一段，答案就是全体 $A_i$ 的按位与，二分也能自然得出，无需特判。

八、对拍验证

为确认 1.cpp 是本题的正确最终版，我用暴力程序做了三重验证：

1. 官方样例：5 5 / 1 2 3 4 5 → 输出 1，与题面一致；
2. 穷举小数据：$N \le 6$、小值域的所有取值组合，正解与暴力逐一比对，全部一致；
3. 随机对拍：$N \le 12$，混合“小值 / 中等值 / 接近 $10^9$ 的大值”三种分布，共 200000 组，答案 100% 吻合。

结论：1.cpp 为最终正确版本。同目录的 1b.cpp 是已知有 bug 的草稿（易错点 1），2.cpp 在本目录中为空文件，3.cpp 是暴力对照，gen.cpp / search.cpp 是对拍脚手架。

提醒：本仓库目录约定里“2.cpp 是最新最完美的版本”并非绝对——本目录的 2.cpp 就是空文件。每道题都要实际读代码判断，不能盲信文件名。

九、小结

一句话总结：“最大化最小值”→ 二分答案；“每段按位与 $\ge m$ 是否可行”→ 利用 AND 的单调性贪心合并。 吃透这两步，这套“二分 + 位运算贪心”就能迁移到一大类题目。