综合算法题

发表于 更新于 分类于 本文字数： 2.1k 阅读时长 ≈ 8 分钟

收录一些平时做的比较综合的题目. 考察的知识点不止一点, 各种优化方式简直使出毕生所学.

大概是蓝桥杯国赛, ACM银, 提高组以上难度, 是比赛你不会轻易去碰的题目, 讲解起来也是额外麻烦. 虽然说比赛能保证签到题全对就已经很了不起了, 但这种题目就像高考数学的压轴题, 还是要有所接触才能有所突破嘛.

裁剪序列

题目

导航: AcWing 299. 裁剪序列

题目描述

给定一个长度为 \(N\) 的序列 \(A\)，要求把该序列分成若干段，在满足“每段中所有数的和”不超过 \(M\) 的前提下，让“每段中所有数的最大值”之和最小。

试计算这个最小值.

输入格式

第一行包含两个整数 \(N\) 和 \(M\).

第二行包含 \(N\) 个整数，表示完整的序列 \(A\).

输出格式

输出一个整数，表示结果。

如果结果不存在，则输出-1。

数据范围

\[0 \leqslant N \leqslant 10^5\]

\[0 \leqslant M \leqslant 10^{11}\]

序列 \(A\) 中的数非负, 且不超过 \(10^6\).

输入样例:

1
2
8 17
2 2 2 8 1 8 2 1

输出样例:

1
12

样例解释:

样例解释

按照如此分组, 第一组中的最大值为2, 第二组中的最大值为8, 第三组的最大值为2, 总和 2+8+2=12, 为最小值.

题解

TAG: DP 双指针 贪心 单调队列 堆 STL Multiset

朴素DP

本题可以考虑区间DP的处理方式:

  • 状态表示:
    • 集合: f[i] 表示前 i 个数中所有的划分区间中的最大值之和.
    • 状态: min
  • 状态计算:
    • 划分区间: 1~j 和 j+1~i
      • 1~j 不管
      • 第二段的和要不超过 M
    • 前一段区间很好表示: f[j]
    • 后一段区间: 是 j+1~i 这一段区间上的最大值
    • f[i] = min(f[j] + max A[k]), k in [j+1, i]
    • f[n] 就是答案.
模拟样例

例如 i = 6, 可能的分组有 2 2 2 8 1 8, 2 2 2 8 1 8, 2 2 2 8 1 8...而 f[i] 是这些方案中的最小值, 也即 2 2 2 8 1 8 分组下的 10.

枚举 i, 再枚举 j, 还要枚举 j+1~i 这段上的 k, 这种方法的时间复杂度是 O(n^3). 必定会TLE. 所以得考虑优化. 如果想不出优化方式过几个数据就作罢.

注: 在进一步优化之前请务必理解DP计算的正确性.

优化

j 可以从小到大枚举, 开一个变量就可以存最大的 a[k], 这样复杂度能压到 O(n^2). 但还是会 TLE.

定理 1 如果 j 能够成为 f[i] 的唯一最优解, 那么 j 必须满足以下条件之一:

  • A[j] = max(A[j], A[j+1], ..., A[i])
  • A[j] + ... + A[i] > M 且 A[j+1] + ... + A[i] <= M

证明 考虑反证法. 假设 \(j\) 上述两个条件都不满足. 对于决策 j-1:

  • A[j] + ... + A[i] <= M, 考虑两种情况:
    1. A[j-1] + ... + A[i] > M, 此时 j-1 满足上述条件之一.
    2. A[j-1] + ... + A[i] <= M:
    • f[i] 单调递增.
    • 同时 A[j] 不是 A[j...i] 中的最大值.
      • 那么 f[j-1] + max A[j...i] <= f[j] + max A[j+1...i]
  • j-1 是一个优于 j 或和 j 一样优的方案.

由假设可知不成立. 因此 j 必须满足上面条件之一. \(\Box\)

那么我们的问题就转换为: 对于一个 i, 找到一个满足上述条件的 j, 且 j 距离 i 最远. i 和 j 是随同变化的, 用双指针就可以压到一维.

不过使用双指针之前还要验证单调性, 也就是移动 i, j 也会相应向后移动(无回溯). 不过这不是什么大的问题, 我们给出一个简单的证明:

定理 2 j 在 i 变大的过程中同步增大.

证明 考虑反证法: 如果 i 移动到 i' 而 j 不往后移动, 因为 j 是满足 A[j+1] + ... + A[i] <= M 最小的一个点, 必然有 A[j+1] + ... + A[i'] > M 不满足条件, 因此 j 必须往后移动, 即 j' > j. \(\Box\)

有了这一点, 我们又得到一个性质: [j, i] 这段区间实际上是一个滑动区间, 尽管长度不定, 但最主要的是, i 和 j 都是单调的. 并且, 我们实现的核心, 是在这个区间内寻找区间最值——本质上这就是一个单调队列! 也即, 我们可以用一个单调队列来维护滑动窗口中出现的最大值, 并使得这段区间的总和小于 m.

同时我们需要维护一个方案的集合, 使得集合能够动态求最小值, 添加一个数, 删除一个数(头节点和尾节点). 你可能会想到使用堆存储, 但堆不太方便同时存储头节点和尾节点, 最好用一个平衡树来维护, C++STL里可以用 multiset.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 100010;

int n;
LL m;
int w[N], q[N];
LL f[N];
multiset<LL> S;

// 不用 S.remove 是因为他会把所有的 x 全删掉
// 我们只要删去重复的一个即可
void remove(LL x)
{
    auto it = S.find(x);
    S.erase(it);
}

int main()
{
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
        if (w[i] > m)
        {
            puts("-1");
            return 0;
        }
    }

    int hh = 0, tt = -1;
    LL sum = 0;
    // i 是滑动窗口的右端点 j 是左端点
    // 单调队列维护的是 a_max 的下标
    for (int i = 1, j = 1; i <= n; i++)
    {
        sum += w[i];
        while (sum > m)
        {
            // 减去滑动窗口的左端点
            sum -= w[j++];
            if (hh <= tt && q[hh] < j)
            {
                if (hh < tt)
                    remove(f[q[hh]] + w[q[hh] + 1]);
                hh++;
            }
        }

        while (hh <= tt && w[q[tt]] <= w[i])
        {
            if (hh < tt)
                remove(f[q[tt] - 1] + w[q[tt]]);
            tt--;
        }

        q[++tt] = i;
        if (hh < tt)
            S.insert(f[q[tt] - 1] + w[q[tt]]);
        f[i] = f[j - 1] + w[q[hh]];
        if (S.size())
            f[i] = min(f[i], *S.begin());
    }

    printf("%lld\n", f[n]);

    return 0;
}

送信

导航: B 送信

题目描述

某人写了 \(n\) 封信和 \(n\) 个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。

输入描述

一行一个 \(n\). \(n \leqslant 10^9\).

输出描述

输出方案数对 \(10^9+7\) 取模.

样例 1

输入

1
2

输出

1
1

样例 2

输入

1
114514

输出

1
977005016

题解

TAG: 组合数学 DP优化 分段打表

朴素做法

经典的错排问题.

小学生都能看懂的错排问题解析

打表程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
typedef unsigned long long ULL;
using namespace std;

const int MOD = 1e9 + 7;
int n;

ULL D[3] = {0, 1, 1};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 3; i <= n; i++)
    {
        D[2] = (i - 1) * (D[1] + D[0]);
        D[0] = D[1];
        D[2] %= MOD;
        D[1] = D[2];
    }
    cout << D[2] << endl;
    return 0;
}

直接交 TLE. \(O(n)\) 的复杂度, 但是常数还是挺大的, 1s 跑不完 1e9 的数据. 显然我们要用打表优化.

分块打表

关键是 n 离谱的大, 朴素打表不适用, 只能用分段打表, 大体思路是: 把数据范围分成多份, 预处理每一块的信息, 不满一块就暴力计算.

我们把 1e9 的数据分成 10 份 1e8 的块. 如果你有力气, 可以分块成 1000 份 1e6 的块, 然后打表. 预处理之后, 要计算例如 3e8 + 3, 那么直接从表里找到 3e8 + 1 和 3e8 + 2(你也可以写 10 个 elif), 然后按公式计算即可.

这题还有个坑: 考场上有一个样例 n = 0, 这不欺负人嘛.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
typedef unsigned long long ULL;
using namespace std;

const int P = 1e8, MOD = 1e9 + 7;
int n;

ULL dp[3];
const ULL scr[] = {
    0,
    1,
// 1e8 + 1, 1e8 + 2
    696682031,
    5686635,

    314470659,
    988682402,

    41451389,
    695854867,

    451755479,
    238595622,

    827750738,
    758373908,

    269882629,
    806258227,

    398578002,
    244123805,

    365715120,
    683425583,

    639014656,
    652237004,

    586902194,
    65489052,
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    int x = n / P;
    if (n % P == 0)
        x --;
    dp[0] = scr[2 * x];
    dp[1] = scr[2 * x + 1];
    for (int i = x * P + 3; i <= n; i++)
    {
        dp[2] = (i - 1) * (dp[0] + dp[1]);
        dp[0] = dp[1];
        dp[2] %= MOD;
        dp[1] = dp[2];
    }
    if (n % P == 1)
        dp[2] = scr[2 * x];
    else if (n % P == 2)
        dp[2] = scr[2 * x + 1];

    cout << dp[2] << endl;
    return 0;
}