【每日一题】code-festival-2016-qualc C - Two Alpinists | 分类讨论 |简单

题目内容

原题链接

给定两个长度为 $n$ 的数组 $b$ 和 $c$ ，下标从 $0$ 开始
$b_i=\max (a_0,a_1,\cdots ,a_i)$
$c_i=\max (a_{n-1},a_{n-2},\cdots ,a_i)$

问可以构造出多少个不同的 $a$ ，$a_i$ 是正整数。

答案对 $10^9+7$ 取模。

数据范围

• $1\le n\le 10^5$
• $1\le b_i\le 10^9,b_i\le b_{i+1}$
• $1\le c_i\le 10^9,c_i\ge c_{i+1}$

题解

考虑 $b_i>b_{i-1}$ ，则 $a_i=b_i$ ，此时 $c_i\ge b_i$
考虑 $c_i>c_{i+1}$，则 $a_i=c_i$ ，此时 $b_i\ge c_i$

这里我们还需要特判 $b_0\le c_0$ ，$b_{n-1}\ge c_{n-1}$

如果 $b_i=b_{i-1}$ 且 $c_i=c_{i+1}$ ，则 $a_i\in [1,\min (b_i,c_i)]$，$a_i$ 共这么多种选择。

时间复杂度：$O(n)$

代码

#include 
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    vector<int> b(n), c(n);
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) cin >> c[i];

    if (b.front() > c.front() || b.back() < c.back()) {
        cout << "0\n";
        return 0;
    }

    bool ok = true;
    int ans = 1;
    for (int i = 1; i + 1 < n; ++i) {
        if (b[i] > b[i - 1]) {
            if (c[i] < b[i]) {
                ok = false;
                break;
            }
        } else if (c[i] > c[i + 1]) {
            if (c[i] > b[i]) {
                ok = false;
                break;
            }
        } else {
            ans = 1ll * ans * min(b[i], c[i]) % MOD;
        }
    }

    if (ok) cout << ans << "\n";
    else cout << 0 << "\n";

    return 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