【CSP】2021-09-2 非零段划分 索引+递推/差分+前缀和

2021-09-2 非零段划分 索引+递推/差分+前缀和

一开始写的时候没有发现直接从a数组求q的规律，怎么也想不到怎么用差分前缀和，然后就是只使用了常规的思路建立索引，然后递推的求解，虽然也是过了，但是感觉不是最优解，于是上网搜了一下发现原来可以用这样用差分，以后能用差分就尽量用差分，毕竟差分是正解

索引+递推思路

这个方法是暴力的优化，如果是暴力的话，就是要遍历每一个p然后判断非零段的个数是多少，时间复杂度是$O(n^2)$ 这样肯定会超时，然后我们在此只之上，用一个map来存储每个值对应的下标，这样我们就不用每次遍历一次$O(n)$而是复杂度$O(logn)$ 总的复杂度就是$O(nlogn)$ ，然后就可以拿到100分了。

差分+前缀和思路

然后前面我们是遍历p，其实我们其实可以换个思路遍历a，求得p，这样我们可以实现复杂度是$O(n)$了。

我们需要找到数组a和数组p的关系。首先p数组的含义我们很容易想到，就是p[i]就是p=i时非零段的个数，然后我们判断a[i]和a[i-1]来确定p

如果a[i-1]

那么就是p[a[i]]到p[a[i-1]+1]这个区间内都增加一个非零段，所以这里用到了差分，p[a[i]+1]–,p[a[i-1]+1]++，实现O(1)的复杂度的区间操作。最后在求个前缀和算出所有p对应的非零段的个数，再求出最大值。总的时间复杂度就是O(n)

遇到的问题

1. 递归初始状态的问题

用索引+递归的方法的话，我们得先计算初始的非零段有多少个，然后通过判断周围a[i-1]和a[i+1]的值，是否对非零段增加，并且注意要判断0和n-1的特殊情况。

然后就可以拿到100分

2. 注意题目细节

如果使用前缀+差分的思路的话，得要注意啊题目说的，要是小于p的全部为0，而不是小于等于p的全部为零

对应的差分代码就要从

p[a[i]]--;
p[a[i-1]]++;
1
2

变成

p[a[i]+1]--;
p[a[i-1]+1]++;
1
2

然后这样就可以拿到100分了。

索引+递推完整代码

#include 
using namespace std;
int n;
int a[500001];
map> mp1; // value 对应的位置有哪些
int main()
{
    cin >> n;
    bool zero = true;
    int max_range = 0;
    int temp_num = 0;
    // 输入并且计算非零段的数目的初值
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] != 0)
            mp1[a[i]].push_back(i);
        if (a[i] == 0)
            zero = true;
        if (a[i] != 0)
        {
            if (zero == true)
                temp_num++;
            zero = false;
        }
    }
    max_range = temp_num;
    for (auto item : mp1)
    {
        for (auto x : item.second)
        {
            if (x > 0 && x < n - 1)
            {
                if (a[x - 1] != 0 && a[x + 1] != 0)
                {
                    temp_num++;
                }
                else if (a[x - 1] == 0 && a[x + 1] == 0)
                {
                    temp_num--;
                }
            }
            if (x == 0 && a[x + 1] == 0)
            {
                temp_num--;
            }
            if (x == n - 1 && a[x - 1] == 0)
            {
                temp_num--;
            }
            a[x] = 0;
        }
        max_range = max(max_range, temp_num);
    }
    cout << max_range << endl;
    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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

差分+前缀和完整代码

#include 
using namespace std;
int n, a[500001], p[10001];
// 定义p[i]是不超过i的非零段的个数
// 那么p[i]-p[i-1]的含义是在i-1为0的基础上增加i为0后非零段的个数的增加
int main()
{
    cin >> n;
    int max_a = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i]; // 输入数据
        max_a = max(max_a, a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > a[i - 1])//如果前一个大于后一个
        {
            p[a[i - 1] + 1]++;
            p[a[i] + 1]--;
        }
    }
    int max_p = 0;
    for (int i = 1; i <= max_a + 1; i++)
    {
        p[i] += p[i - 1];
        max_p = max(max_p, p[i]);
    }
    cout << max_p;
    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