算法挑战赛题解（11.2）

简单版本：

题目大意：

给定n个区间，判断这些区间能划分出几种不同的区域

题目分析：

实际上是在讨论每个点被哪几个区包含，在样例中，数据是这样的，我们来分析一下这两个样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Sample Input 1 

1
1 6

Sample Output 1

2

Sample Input 2

4
0 12
4 13
6 13
12 13

Sample Output 2

6

样例分析：

1
2
3
4
5
6
7
8
样例1: 0 1 1 1 1 1 1 0 0 … …  所以是两种区间
样例2: 1   2  3   4   5   6   7  8    9   10  11  12  13 … …
       1   1  1   1   1   1   1  1   1    1   1   1
                  2   2   2   2  2   2    2   2   2   2
                          3   3  3   3    3   3   3   3
                                                  4   4
       |< ------ >|< ---- >|< ----------------- >|<->|<->|<--

所以是6种区间
这样,我们就弄明白了题目在讲什么,接下来就可以思考怎么实现了

题目思路：

实际上有些人会以为我们需要统计的是这个点有几个区间经过，但是这是错误的，在样例二就能发现这一点。
（这也是我第一次的想法，测试样例二时发现的T_T）

我们需要思考怎么表示这一个点有哪些区间经过，而且每一个区间是互不相同的。这里我们考虑类似状态压缩的思想。

什么是状态压缩呢？简而言之就是用一个数来代替这个状态。
比如说，我们用1表示未进行，2表示正在进行，3表示完成，
那么一个含有4个任务的任务表可以是这样的：

            1321

（1，4任务未进行，2任务完成，3正在进行）

我们使用了一个4位数表示了这一状态，这样就实现了状态压缩，我们没有用数组存储状态，而是一个数，这样我们在判断两个状态是否相同时就可以直接判断数字是否相同了，节约了时间和判断的复杂度。

那么怎么把这个思想用在这一题呢？我们考虑给每个区间一个标号k，每个区间内的点加上2^k，这样就保证了每一个状态不会重复。
但是这么写居然WA了！这是因为数据范围n是[0,300]也就是会有2^300，远大于long long的最大范围(2^64-1)这显然是不行的。

实际上这个算法已经十分接近答案了,但我们还需要改进这个算法。
接着我们想到一个类似的方法，哈希表(hash)。

其实哈希表和刚才的思路差不多，不过加入了一些更高级的算法来防止数据溢出。

那么什么是hash呢？

实际上也是创建一种对应关系，使得在查询时能快速访问这种情况对应的值。就像上面的例子一样，我们通过我们规定的方式把任务状态和整数一一对应。

怎么创建hash表呢？

首先，找到一个质数作为进制数P，通常取131或者13331，模数mod通常取1e9+7或1e9+9，对应关系就是对应的P进制数%mod
例如这个点上经过了134这三个集合，那么我们就把134转化为131进制，即1 131^2+3 131+4，在实际操作时，就是每一个集合的下标k作为对应的位数，则每一个点的表示可以是这样的：

公式

这样我们就计算出了每一个点的唯一标识，含有相同标识的才能算是同一个点。（这里选择质数是为了防止哈希碰撞，即不同状态的得到了相同的标记；选择mod是防止溢出）

最后只要统计一下标识的个数就行了（可以用set实现）
代码实现：对于简单版本，暴力完全够用了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll P=131,mod=1e9+7;
int main(){
    ll n,z=1,a[1010]; cin>>n;
    for(int i=0;i<=1000;i++) a[i]=0;
    while(n--){
        ll l,r; cin>>l>>r;
        for(int i=l;i<=r;i++){
            a[i]=(a[i]+z)%mod;
        }
        z=(z*P)%mod;
    }
    set<ll> q;
    for(int i=0;i<=1000;i++){
        q.insert(a[i]);
    }
    cout<<q.size()<<endl;
}

所以这样我们就解决了简单版本。

复杂版本：

那么对于数据量大的复杂版本呢？

这里我们依然采用hash，但是由于数据量大，为了防止冲突，我们给每一个区间都分配一个随机hash值，在计算时只考虑起点和终点，在进入起点时加入标记，离开时移除标记。这时我们就想到了具有可逆性质的异或，我们只要给对应的起终点打上相同标记就行了，最后还是用set统计产生的不同标记数

参考代码：

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ULL unsigned long long
#define endl '\n'
int main(){
    ll n; cin>>n;
    vector<pair<ll,int>> box;
    for (int i=0;i<n;i++){
        ll l,r; cin>>l>>r;
        box.push_back({l,i});
        box.push_back({r+1,i});
    }
    sort(box.begin(),box.end());
    vector<unsigned long long> h(n);
    mt19937_64 rng(time(0));
    for(int i=0;i<n;i++){
        h[i]=rng();
    }
    set<ULL> s; s.insert(0);
    ULL cur=0;ll last=-2e9;
    for(auto& i:box){
        ll pos=i.first,idx=i.second;
        if(pos>last&&last!=-2e9) s.insert(cur);
        cur^=h[idx];
        last=pos;
    }
    s.insert(cur);
    cout<<s.size()<<endl;
}

```yaml
感谢观看！关注ZestfulYK喵，谢谢喵！