P4141 解题报告 暨 缺一分治学习报告

AuCodingFrogHoward · 2026-03-09 14:01:01 · 题解

鸣谢

本文的部分内容可能来自他的口头讲解，让我们感谢他的贡献。

算法

概览

缺一分治适合解决明确要求剔除一个元素，支持快速插入一个元素，通常不支持快速合并，通常不支持快捷删除的问题。缺一分治函数 f(l ,r) 代表进行到某一进程时，在选数集合中不含且仅不含 [l ,r] 之间的元素，会发生什么。

流程

其流程是如此的：

甲、如果 l = r，则剔除 l 的局面已经形成，则统计答案，并立刻结束这个函数。

乙、算出区间的中点为 z，并复制当前的状态。

丙、加入区间左半边，即 [l ,z] 间的元素，在此状态下求解 f(z + 1 ,r)。

丁、依靠复制本，回滚到丙操作之前。

戊、加入区间右半边，即 [z + 1 ,r] 间的元素，在此状态下求解 f(l ,z)。

己、立刻结束这个函数。

时空复杂度分析

总析

我们发现这个函数每一次递归都会将 r - l + 1 缩小至原来的一半，所以会递归 \log n 层。

加入元素

由于递归不改变同一层中的总长，因为同一层中的总长恒为 n。因为在同一层中，每一个元素都会被加入一次，当加入操作复杂度为 O(k) 时，加入元素的时间复杂度为 O(n \log n k)。

回滚数组

设统计数组（有时是记录答案，有时动态规划）的大小为 a，类比线段树，执行 f 的次数为 O(n)，每执行一次就会进行一次时间复杂度为 O(a) 的回滚，则回滚操作的总复杂度为 O(na)。

空间分析

每一层只会有一个函数同时等待运行，故并行函数只有 O(\log n) 个。辅助数组空间大小为 O(a)，则总体为 O(a\log n)。

整理

缺一分治部分，时间复杂度为 O(nk \log n + na)，空间复杂度为 O(a\log n)。

此题应用

使用缺一分治，尝试抽离模型。

我们发现此问题是枚举缺少任一个元素，在缺一意义下做膜拜 10 的普通背包方案计数，然后据此输出。于是可以套模板。

码

#include<bits/stdc++.h>
#define int long long
#define y1 qht_yjx
#define hash ZhaoAk
#define maxn 2005
#define endl "\n"
#define nullptr 0
#define I ios::sync_with_stdio (nullptr);
#define AK cin.tie (nullptr);
#define CSP cout.tie (nullptr);

using namespace std;

int n ,m ,a[maxn] ,dp[maxn] ,ans[maxn][maxn];

void qadd (int x)//添加
{
    for (int i = m ;i >= a[x] ;i --)
        dp[i] += dp[i - a[x]] ,dp[i] %= 10;
}

void MaXiaomeng (int l ,int r)//值得仰慕的名字
{
    if (l == r)//甲
    {
        for (int i = 1 ;i <= m ;i ++)
            ans[l][i] = dp[i] % 10;
        return ;
    }
    int zc[maxn];
    for (int i = 1 ;i <= m ;i ++)
        zc[i] = dp[i];
    int z = (l + r) >> 1;//乙
    for (int i = l ;i <= z ;i ++)
        qadd (i);
    MaXiaomeng (z + 1 ,r);//丙
    for (int i = 1 ;i <= m ;i ++)
        dp[i] = zc[i];//丁
    for (int i = z + 1 ;i <= r ;i ++)
        qadd (i);
    MaXiaomeng (l ,z);//戊
}//己

signed main()
{
    I AK CSP
    cin >> n >> m;
    for (int i = 1 ;i <= n ;i ++)
        cin >> a[i];
    dp[0] = 1;
    MaXiaomeng (1 ,n);
    for (int i = 1 ;i <= n ;i ++)
    {
        for (int j = 1 ;j <= m ;j ++)
            cout << ans[i][j];
        cout << endl;
    }
    return !!!!! ("ShZhao" && "SHzhao");
}
//Code by Lyyq.
//wage.

本题复杂度

取 a = k = m，时间复杂度为 O(nm\log n)，空间复杂度为 O(nm)。

另例应用（浅析）

某题

我们可以观察到一个性质：始终存在一个最优解，至多有一个数组取了但没取完。考虑使用反证法证明。

证明：

设取了但没取完 a_k 和 a_t 两个数组，它们的大小分别为 n 和 m，我分别取了 i 和 j 个，但未取完，答案却超过了性质里所提策略。

当 i + j \ge n 时：

则有：

说明：

说明：

对偶的，也矛盾。

当 i + j < n 时：