首页 algorithm 杂杂的算法知识

# 模版

# 合并集合

836. 合并集合 - AcWing 题库

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N];
int n, m;
int find(int x)//寻找根节点
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void Merge(int a, int b)
{
    int pa = find(a), pb = find(b);
    if(pa != pb) p[pa] = pb;
}
string Query(int a, int b)
{
    if(find(a) == find(b)) return "Yes";
    else return "No";
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;//初始化自己的根节点是自己
    while(m--)
    {
        char x; int a, b;
        cin >> x >> a >> b;
        if(x == 'M')  Merge(a, b);
        else cout << Query(a, b) << '\n';
    }
    return 0;
}

# 应用

# 食物链

240. 食物链 - AcWing 题库

与根节点一共有三种关系，用 0 表示和根节点是同类；1 表示根节点吃该结点；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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int p[N], d[N];
int n, k, res;
int find(int x)
{
    if(x != p[x]) 
    {
        int t = find(p[x]);
        d[x] += d[p[x]];//将所有结点直接连接根节点
        p[x] = t;
    }
    return p[x];
}
bool D1(int x, int y)//合并
{
    int px = find(x), py = find(y);
    if(px != py)
    {
        p[px] = py;
        d[px] = d[y] - d[x];//到根节点距离都是0，表示是同类
        //d[x]+ d[px]表示x到根节点的距离；d[y]表示y到根节点的距离
        //x的旧根节点即父节点，所以x到新根节点的距离等于x到旧根节点的距离+旧根节点到新根节点的距离
        return true;
    }
    else
    {
        if((d[y] - d[x] + 3) % 3) return false;//如果x，y到根节点的距离不同，证明不是同类
        else return true;
    }
}
bool D2(int x, int y)//x吃y -> 相当于y吃根节点，根节点吃x，x吃y -> x到根节点距离是1，y到根节点距离是2
{
    int px = find(x), py = find(y);
    if(px != py)
    {
        p[px] = py;
        //d[px] + d[x] = d[y] - 1
        d[px] = (d[y] - d[x] - 1 + 3) % 3;
        return true;
    }
    else
    {
        if((d[x] - d[y] + 1 + 3) % 3) return false;
        else return true;
    }
}
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) p[i] = i;//初始化让自己的父节点是自己
    while(k--)
    {
        int c, x, y;
        cin >> c >> x >> y;
        if(x > n || y > n) 
        {
            res++;
            continue;
        }   
        if(c == 1) 
            if(!D1(x, y)) res++;
        if(c == 2) //注意！！！不要写else！！！
            if(!D2(x, y)) res++;
    }
    cout << res;
    return 0;
}

# 格子游戏

1250. 格子游戏 - AcWing 题库

  1. 将二维变成一维(x,y)=x∗n+y(x,y)=x*n+y
  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
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 200 + 10;
int p[N];
int n, m;
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n * n; i++) p[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int a, b; char c;
        cin >> a >> b >> c;
        int x = (a - 1) * n + b, y;
        if(c == 'D') y = a * n + b;
        else y = (a - 1) * n + b + 1;
        int px = find(x), py = find(y);
        if(px == py)
        {
            cout << i;
            return 0;
        }
        else
            p[px] = py;
    }
    cout << "draw";
    return 0;
}

# 程序自动分析

237. 程序自动分析 - AcWing 题库

  1. 因为数据量很大，但实际上没有那么多的数据，所以需要离散化
  2. 将相等的放在同一个联通块中，再遍历不相等的，如果发现不相等的两个节点在同一个联通块就输出 “NO”
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int p[N];
int t, n, idx;
typedef pair<int, int> PII;
vector<PII> e, ue;
unordered_map<int, int> H;
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int Hash(int x)
{
    if(!H.count(x)) H[x] = ++idx;
    return H[x];
}
int main()
{
    cin >> t;
    while(t--)
    {
        bool flag = true;
        H.clear(), e.clear(), ue.clear();
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            a = Hash(a), b = Hash(b);
            if(c == 1)//相等
                e.push_back({a, b});
            else //不相等
                ue.push_back({a, b});
        }
        for(int i = 1; i <= idx; i++) p[i] = i;
        for(auto [x, y] : e)
            p[find(x)] = find(y);
        for(auto[x, y] : ue)
            if(find(x) == find(y))
                {
                    flag = false;
                    break;
                }
        cout << (flag ? "YES" : "NO") << '\n';
    }
    return 0;
}

# 奇偶游戏

239. 奇偶游戏 - AcWing 题库

  1. 用 sum [n] 存储前 n 个数的和，那么S[l∼r]S[l\sim r] 有奇数个 1⇔\Leftrightarrow sum[l−1]sum[l-1] 和sum[r]sum[r] 奇偶性不同；S[l∼r]S[l\sim r] 有偶数个 1⇔\Leftrightarrow sum[l−1]sum[l-1] 和sum[r]sum[r] 奇偶性相同
  2. 因为依次递推不止两种情况，所以用距离表示奇偶关系，d[x]=0d[x]=0 表示和根节点奇偶性相同，d[x]=1d[x]=1 表示和根节点奇偶性不同
  3. 使用异或 ^ 更新d[x]d[x]
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int p[N], d[N];
unordered_map<int, int> H;
int n, m, idx;
int Hash(int x)
{
    if(!H.count(x)) H[x] = ++idx;
    return H[x];
}
int find(int x)
{
    if(x != p[x]) 
    {
        int root = find(p[x]);
        d[x] ^= d[p[x]];
        p[x] = root;
    }
    return p[x];
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < N; i++) p[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        string c;
        cin >> a >> b >> c;
        a = Hash(a - 1), b = Hash(b);
        int t = 0;
        if(c[0] == 'o') t = 1;
        int pa = find(a), pb = find(b);
        if(pa == pb)
        {
            if(d[a] ^ d[b] != t) 
            {
                cout << i - 1;
                return 0;
            }
        }
        else
        {
            p[pa] = pb;
            //d[b] ^ d[a] ^ d[pa] ^ t = 0
            d[pa] = d[b] ^ d[a] ^ t;
        }
    }
    cout << m;
    
    return 0;
}