题目1 格子游戏

题面描述：Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3 ）。接着，他们两个轮流在相邻的点之间画上红边和蓝边：

1.png

直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序，帮助他们计算他们是否结束了游戏？

原题链接：AcWing 1250. 格子游戏

解题思路：

  1. 问题转换，当要连接的两个点的本身就是一个是连接的状态那么就会得到一个环，我们用集合的形式维护已经连接的点根节点就当作链接状态的起始点，于是这样的判环问题就转化成了集合合并与查找的问题了

完整代码：

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
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 40010;
int n, m;
int p[N];

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int get(int x, int y){
    return (x-1)*n+(y-1);
}

int main(){
    cin>>n>>m;
    for(int i = 0; i < n*n; i++)p[i] = i;
    
    int ans = 0;
    for(int i = 1; i <= m; i++){
        int x, y;
        char d;
        cin>>x>>y>>d;
        int a = get(x, y);
        int b;
        if(d == 'D') b = get(x+1, y);
        else b = get(x ,y+1);
        
        int pa = find(a), pb = find(b);
        if(pa == pb){
            ans = i;
            break;
        }
        p[pa] = pb;
    }
    if(ans) cout<<ans;
    else puts("draw");
    
    return 0;
}

题目2 搭配购买

题面描述：Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有 n 朵云，云朵被编号为 1,2,…,n ，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。但是Joe的钱有限，所以他希望买的价值越多越好。

原题链接：AcWing 1252. 搭配购买

备用链接：洛谷 P1455 搭配购买

解题思路：

  1. 这里看到了钱数有限还要每朵云都有相应价值就可以联想到背包问题了，把价格看作体积就是一个01背包问题的变形啦
  2. 我们需要做的就是将这些捆绑销售的云朵看作是一个集合，集合的属性只要在根节点上面维护就可以了

完整代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 10010;
int n, m, vol;
int v[N], w[N];
int p[N];
int f[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin>>n>>m>>vol;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= n; i++) cin>>v[i]>>w[i];
    
    while(m--){
        int a, b;
        cin>>a>>b;
        int pa = find(a), pb = find(b);
        
        if(pa != pb){
            v[pb] += v[pa];
            w[pb] += w[pa];
            p[pa]  = pb;
        }
    }
    
    //01背包问题
    for(int i = 1; i <= n; i++){
        if(p[i] != i) continue;
        for(int j = vol; j >= v[i]; j--){
            f[j] = max(f[j], f[j-v[i]]+w[i]);
        }
    }
    
    cout<<f[vol]<<endl;
    
    return 0;
}

题目3 程序自动分析

题目描述：在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。

例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

原题链接：AcWing 237. 程序自动分析

备用链接：洛谷 P1955 NOI2015 程序自动分析

解题思路：

  1. 这个题实际上和格子游戏的题很相似的在于两者都是在于查找查找闭环的情况
  2. 我们将相等与不相等的条件分立来看，所有相等的条件之间都不会产生冲突，所有不相等的条件之间也不会产生冲突，只有当处理到已经判断相等的条件而又判断为不相等或者已经判断不相等而后又判断相等 才会出现错误
  3. 这里我们选择第一种判断的方案，因为经过 “格子游戏” 的启发后我们可以发现处理这种彼此之间无向关系并且有连接传递性质的问题时我们使用集合的概念时是比较适用的，我们可以将彼此相等的一群元素看作是处于同一个集合，先行处理完所有相等的元素并连接为集合（这样就可以避免判断差错数据未处理完之前还无法看出某两个元素之间是相等的）
  4. 然后根据不相等的条件我们对查找两个被判定为相等的元素是否在之后又被判断为不相等了，即之后处理被判断为不相等原始是否同在一个集合之中，如果在同一个集合之中则判断为冲突
  5. 由于本题中的元素数据范围比较大而数据量想对的小，所以我们还需要采用离散化的方法，这里的离散化使用也是非常经典的：使用哈希表存储变量的到离散化数据的转化关系，当一个转化关系确定后就存储在哈希表中，当查找到确定的转化关系后就使用关系即可否则添加关系

完整代码：

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
#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<algorithm>
using namespace std;

const int N = 2000010;

int n, m;
int p[N];
unordered_map<int, int> S;

struct{
    int x, y, e;
} query[N];

int get(int x){
    if(S.count(x) == 0) S[x] = ++n;
    return S[x];
}

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        n = 0;
        S.clear();
        
        scanf("%d", &m);
        for(int i = 0; i < m; i++){
            int x, y, e;
            scanf("%d%d%d", &x, &y, &e);
            query[i] = {get(x), get(y), e};
        }
        
        for(int i = 1; i <= n; i++) p[i] = i;
        
        //合并所有相等条件
        for(int i = 0; i < m; i++){
           if(!query[i].e) continue;
           int pa = find(query[i].x), pb = find(query[i].y);
           p[pa] = pb;
        }
        
        //检查所有不等条件
        bool has_conflict = false;
        for(int i = 0; i < m; i++){
            if(query[i].e) continue;
            int pa = find(query[i].x), pb = find(query[i].y);
            if(pa == pb) {
                has_conflict = true;
                break;
            }
        }
        
        if(has_conflict) puts("NO");
        else puts("YES");
    }
    
    return 0;
}

题目4 银河英雄传说

题目描述：有一个划分为N列的星际战场，各列依次编号为1,2,…,N。

有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。

有T条指令，每条指令格式为以下两种之一：

1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。

2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

现在需要你编写一个程序，处理一系列的指令。

原题链接：AcWing 238. 银河英雄传说

备用链接：洛谷 P1196 NOI2002 银河英雄传说

解题思路：

  1. 我们很容易地发现题目具有良好的传递关系（虽然是有向的），我们可以用节点之间的创建集合关系来维护节点间的联通性
  2. 由于节点还需要添加一个边权可以很明显地发现这里的边权是每个节点的属性而不单是根节点的属性故我们不能只维护根节点的属性，这就是本题的核心如果去处节点之间距离的属性而只关注节点之间合并到一个战舰队列中然后判断两个战舰是否在同一个战队中这其实就是普通的集合合并与查找，而带上边权之后其实就不是那么显然了
  3. 使用并查集的方式处理问题，我们节点之间的关系很多是通过根节点去传递的，这里如果为每一个战舰配置一个距离量显然是不合理的，所有我们利用了前缀和的思想维护每一个节点到根节点的距离即可
  4. 考虑集合合并的情况：当一个舰队连接到另一个舰队的尾部时，这个舰队中的每一个节点距离根节点的距离都要加上另一个舰队的总舰队的战舰数量，这里又需要维护一个舰队的舰队体积的值，而这个量只需要在根节点维护即可

完整代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

const int N = 30010;

int m;
int p[N], s[N], d[N];

int find(int x){
    if(p[x] != x){
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int main(){
    scanf("%d", &m);
    
    for(int i = 1; i < N; i++){
        p[i] = i;
        s[i] = 1;
        //d[i] = 0;
    }
    
    while(m--){
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        int pa = find(a), pb = find(b);
        
        if(op[0] == 'M'){
            d[pa] = s[pb];
            s[pb] += s[pa];
            p[pa] = pb;
        }
        else{
            if(pa != pb) puts("-1");
            else printf("%d\n", max(abs(d[a]-d[b])-1, 0));
        }
    }
    return 0;
}

这里的关键就是find()函数了，当进行集合合并的时候只修改了被合并的集合的根节点到现在集合中的根节点的距离，我们并没有修改其他舰队的距离这是必须注意的，当我们进行路径压缩时先时找到了最初的根节点，然后修改了的到根节点的距离然后才插入到新的根节点的，所有当没有进行路径压缩前节点找到的永远时前一个状态的根节点然后才更新了到目前的根节点的（这里非常绕还请多加留意）

题目5

题目描述：小A和小B在玩一个游戏。

首先，小A写了一个由0和1组成的序列S，长度为N。然后，小B向小A提出了M个问题。在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。机智的小B发现小A有可能在撒谎。

例如，小A曾经回答过 S[1~3] 中有奇数个1， S[4~6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。

请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。即求出一个最小的k，使得01序列S满足第1~k个回答，但不满足第1~k+1个回答。

原题链接：AcWing 239. 奇偶游戏

备用链接：POJ 1733 Parity game

解题思路：

方法1：带边权的并查集

  1. 这里我们也用到了前缀和的思想，对于一个在区间[l,r]内为奇数的序列可以看作在[0,l-1]和[0,r]两个区间内的奇偶性不同，而区间[l,r]内为偶数的序列就可以看作是在[0,l-1]和[0,r]两个区间内的奇偶性相同
  2. 根据并查集的特点我们来看一下已经确定两两之间的奇偶关系的两组数据如何得到他们的传递关系
    1. 很显然如果这两组数据是形如区间[x1, x2]和[x3, x4]这样的话是完全无法得到通过已知确定他们之间的奇偶传递关系的，故我们下面考虑这样的两个区间[x1, x2]和[x2+1, x3]之间由确定关系推导出其传递关系
    2. 如果[x1, x2]与[x2+1, x3]都是偶，即[0, x1-1]与[0, x2]的奇偶性相同，[0, x2]与[0, x3]的奇偶性也相同，这样显然就可以推出[0, x1-1]与[0, x3]的奇偶性相同
    3. 如果[x1, x2]为偶[x2+1, x3]为奇，那就意味着[0, x1-1]与[0, x2]奇偶性相同，而[0, x2]与[0, x3]奇偶性不同，即[0, x1-1]与[0, x3]奇偶性也不相同，同样的[x1, x2]为奇[x2-1, x3]为偶也是相似的
    4. 如果[x1, x2]与[x2-1, x3]同为奇，即[0, x1-1]与[0, x2]奇偶性不同[0, x2]与[0, x3]奇偶性也不同，可以推出[0, x1]与[0, x3]奇偶性相同
  3. 这里的奇偶性就是我们要维护的边权，当需要路径压缩的时候就通过上面的结论进行路径压缩啦，将[0, x2]与[0, x3]的边权相异或即可得到[0, x3]与[0, x1]的奇偶关系啦
  4. 由于这里的数据范围N非常大而数据量M相对较小我们同样是需要离散化的，由上面的分析其实可以得到这样是结论：x1 x2 x3之间的相对大小关系是不重要的只要确定了这三者之间的奇偶性关系就可以进行路径压缩啦，所以我们可以采用和上面的程序自动分析相同的离散化方案
  5. 当出现两个数本来在同一个集合内即奇偶性确定但是后面输入的奇偶性与确定的奇偶性相矛盾则说明答案错误游戏结束

完整代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<unordered_map>
using namespace std;

const int N = 20010;

int n,m;
int p[N], d[N];
unordered_map<int, int> S;

int get(int x){
    if(S.count(x) == 0) S[x] = ++n;
    return S[x];
}

int find(int x){
    if(p[x] != x){
        int root = find(p[x]);
        d[x] ^= d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int main(){
    cin>>n>>m;
    //这里的n实际上是没有用的
    //所以直接就当作离散化的基数来使用了
    n = 0;
    
    for(int i = 0; i < N; i++) p[i] = i;
    
    int ans = m;
    for(int i = 1; i <= m; i++){
        int a, b;
        string type;
        cin>>a>>b>>type;
        a = get(a-1), b = get(b);
        
        int t = 0;
        if(type == "odd") t = 1;
        
        int pa = find(a), pb = find(b);
        if(pa == pb){
            if((d[a]^d[b]) != t){
                ans = i-1;
                break;
            }
        }
        else{
            p[pa] = pb;
            d[pa] = d[a]^d[b]^t;
        }
    }
    
    cout<<ans;
    return 0;
}

方法2：扩展域并查集

  1. 由上面的分析可以知道，我们可以通过[l, r]的奇偶性判断[0, l-1]与[0, r]的奇偶性是否相同，但是我们不能知道[0, l-1]与[0, r]这两个区间各自确切的奇偶性，因此我们考虑两种情况[0, l-1]为奇数和[0, l-1]为偶数，即将一个节点拆分为两种状态（经常也称这两个节点为l-1（也就是代表着区间[0, l-1]的节点）的“奇数域”和“偶数域”）
  2. 当确定了[l, r]为奇，也就是[0, l-1]与[0, r]的奇偶性相反，我们可以推出如果[0, l-1]为奇则[0, r]一定要为偶，而如果[0, l-1]为偶则[0, r]一定要为奇，这样我们可以将节点l-1的奇数域与r的偶数域等价合并将节点l-1的偶数域与r的奇数域也等价合并，即当[0, l-1]为奇数则能推出[0, r]为偶数
  3. 如果确定了[l, r]为偶也和上面的分析类似即可
  4. 我们考虑一下这种情况：当我们确定了[l, r]为奇但是在[0, l-1]的奇数域中发现和[0, r]的奇数域已经合并在一起了就说明发生矛盾了，当[l, r]为偶的时候类似

完整代码：

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<iostream>
#include<cstdio>
#include<cstring>
#include<unordered_map>
using namespace std;

const int N = 40010, Base = N/2;

int n,m;
int p[N], d[N];
unordered_map<int, int> S;

int get(int x){
    if(S.count(x) == 0) S[x] = ++n;
    return S[x];
}

int find(int x){
    if(p[x] != x){
        p[x] = find(p[x]);
    }
    return p[x];
}

int main(){
    cin>>n>>m;
    n = 0;
    
    for(int i = 0; i < N; i++) p[i] = i;
    
    int ans = m;
    for(int i = 1; i <= m; i++){
        int a, b;
        string type;
        cin>>a>>b>>type;
        a = get(a-1), b = get(b);
        
        if(type == "even"){
            if(find(a+Base) == find(b)){
                ans = i-1;
                break;
            }
            p[find(a)] = find(b);
            p[find(a+Base)] = find(b+Base);
        }  
        else{
            if(find(a) == find(b)){
                ans = i-1;
                break;
            }
            p[find(a+Base)] = find(b);
            p[find(a)] = find(b+Base);
        }
    }
    
    cout<<ans;
    return 0;
}