题解：P11883 [RMI 2024] 信号 / Signals

MaxFwl · 2025-03-16 13:58:20 · 题解

先考虑如何判断是否存在合法解。

由于所有限制都是关于两个数的相对关系的，所以我们可以假定 b_1 = 0，则是否存在合法解转化为是否存在一种方案满足前 n - 1 条限制且 \text{popcount}(b_n) = a_n。

定义 dp_{i, j} 表示是否存在一种方案使得满足前 i - 1 条限制且 \text{popcount}(b_i) = j，考虑顺推，假设从第 i 个数推到第 i + 1 个数，枚举使 b_i 中几个 1 变为 0，则可以表示出其能转移到的下一个状态，复杂度 O(nk^2)。

dp[1][0] = 1;
for (int i = 1; i < n; i++){
    for (int j = 0; j <= k; j++)
        if (dp[i][j])
            for (int x = max(0, a[i] - k + j); x <= min(j, a[i]); x++)
                dp[i + 1][j - x + a[i] - x] = 1;
}

考虑优化，我们发现每次转移到的位置都是编号奇偶性相同的一段连续段，于是我们可以对编号为奇数和编号为偶数的位置分别建立差分数组，每次转移可以看成区间覆盖，这样可以做到 O(nk)。

dp[1][0] = 1;
for (int i = 1; i < n; i++){
    for (int j = 0; j <= k; j++)
        if (dp[i][j]){
            int l = abs(a[i] - j), r = min(a[i] + j, k * 2 - a[i] - j);
            if (l <= r){
                dp[i + 1][l]++;
                if (r + 2 <= k)     dp[i + 1][r + 2]--;
            }
        }
    for (int j = 2; j <= k; j += 2) dp[i + 1][j] += dp[i + 1][j - 2];
    for (int j = 3; j <= k; j += 2) dp[i + 1][j] += dp[i + 1][j - 2];
}

考虑如何找出合法解，我们把 dp 的过程倒过来，回溯找出一种合法的方案，由于根据上一个 dp 状态可以推出分别改了几个 0，几个 1，所以可以很简单地找出合法解，复杂度 O(nk)。

总复杂度 O(nk)，略微有点卡空间，实现的时候要注意一下。

code。