【每日一题8】AcWing 422. 校门外的树

发表于 更新于 分类于 Valine：
本文字数： 155 阅读时长 ≈ 1 分钟

Day8 AcWing 422. 校门外的树

思路

  1. 区间合并
  2. (暴力) bool数组遍历

拓展

  1. 区间合并算法

  2. bool数组初始化方法

    • 全部初始化为false 

      1
      bool a[N]={0};

    • 全部初始化为true

      1
      2
      bool a[N];
      memset(a,1,sizeof(a));//#include<cstring> or #include<bits/stdc++.h>

    注：bool hashTable[256] = {1};不报错，这样只会把第一个bool值初始化为true，其他都是false

代码

bool数组
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
#include<iostream>
using namespace std;

const int N=10010;
bool a[N];
int l,m;
int lp,rp;
void init(int l)
{
    for(int i=0;i<=l;i++)
    a[i]=true;
}
int main()
{
    cin>>l>>m;
    init(l);
    int res=0;
    while(cin>>lp>>rp)
    {
        for(int i=lp;i<=rp;i++)
        {
            a[i]=false;
        }
    }
    for(int i=0;i<=l;i++)
    {
        if(a[i]==true)
        res++;
    }
    cout<<res;
    return 0;
}
bool标准
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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
bool st[N];

int main()
{
    scanf("%d%d", &m, &n);
    while (n -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        for (int i = l; i <= r; i ++ ) st[i] = true;
    }

    int res = 0;
    for (int i = 0; i <= m; i ++ )
        if (!st[i])
            res ++ ;

    printf("%d\n", res);

    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
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
PII seg[N];

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

    for (int i = 0; i < n; i ++ ) cin >> seg[i].first >> seg[i].second;

    sort(seg, seg + n);

    int res = m + 1;
    int st = seg[0].first, ed = seg[0].second;
    for (int i = 1; i < n; i ++ )
        if (seg[i].first <= ed) ed = max(seg[i].second, ed);
        else
        {
            res -= ed - st + 1;
            st = seg[i].first, ed = seg[i].second;
        }

    res -= ed - st + 1;

    cout << res << endl;

    return 0;
}