一些思路
2025-05-23 16:36:50 # code

记录一些想出思路之后感觉很有意思的题目

当前只想起来这几题，而且作为算法小白所学算法实在少，题目难度不高，但是觉得思路很巧妙或者思路对某一算法的理解有很大加深。

Codeforces-edu177-Disappearing Permutation

一道并查集启蒙题。

感觉在写这题之前并查集就是一个模板放在那里，不遇到板一点的题难以触动那根神经，但是在想到这题的思路之后感觉并查集作为一个工具真是……好用啊。当时看懂题目花了好一阵子，想写dfs但是在一些处理上感觉很头大，但是一旦想起并查集，就忽然发现代码实现很简单……

其实就是看哪几个数字混一起了，把混一起的数字放一组，每次到哪个数字就把那个数字所在的组理顺。

很简单的一个实现。

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 <iostream>
#include <map>
using namespace std;
int fa[100001];
int cnt[100001];
int find(int i)
{
    if (fa[i] == i)
        return fa[i];
    return fa[i] = find(fa[i]);
}
void uni(int i, int j)
{
    int ifa = find(i);
    int jfa = find(j);
    fa[ifa] = jfa;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            // 读入的数字和它的序列混一起
            uni(x, i); 
        }
        for (int i = 1; i <= n; i++)
            cnt[find(i)]++;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            ans += cnt[find(x)];
            cnt[find(x)] = 0;
            cout << ans << " ";
        }
        cout << "\n";
    }
    return 0;
}

忽然想起来其实真正的启蒙题应该是这场cf前几天的abc看错的题，有一道换座位的题目，但是因为看错题看成校赛出的那种换座位了……打完才发现看错题目了，结果当时看错题的思路放上校赛拿了个一血……第一次如此深刻体会塞翁失马焉知非福……感觉并查集真的是很值得一学的算法，思路很简单实现很容易用起来也很方便，性价比很高。

[P1525 NOIP 2010 提高组] 关押罪犯 - 洛谷

并查集的另外一种思想之放在对立面。

放在对立面的思想应当在思考团伙（朋友的朋友是朋友，敌人的敌人是朋友）的时候有意识，有了该思想之后这题就可以秒了。

在实现团伙的时候，应当会想把一个人放在另一个人的敌人团伙里也就是对立面，一个人的对立面节点应该如何创建？每个人的编号为1-n，那我们很容易想到把每个人的对立面设为i+n，就可以有效避免编号重复且一一对应了。

回到这题，对立面的思想就很有用了~我们可以先将每对组合按照怨气值作一个降序排序，从怨气值最大的开始，把两个人放在对方对立面，如果两个人已经在一个集合内，则输出当前怒气值。题目是不是一下子就变得很容易了……

实现也非常简单

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
#include <iostream>
#include <queue>
using namespace std;
int fa[40002];
int find(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
void uni(int x, int y)
{
    int f1 = find(x);
    int f2 = find(y);
    if (f1 != f2)
        fa[f1] = f2;
}
struct aa
{
    int x, y, w;
    bool operator<(const aa &a) const
    {
        return w < a.w;
    }
};
priority_queue<aa> q;
int main()
{
    int n, m;
    cin >> n >> m;
    //记得对立面也要初始化
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    int x, y, w;
    while (m--)
    {
        cin >> x >> y >> w;
        q.push({x, y, w});
    }
    while (!q.empty())
    {
        aa a = q.top();
        if (find(a.x) != find(a.y))
        {
            //放在对方对立面~
            uni(a.x + n, a.y);
            uni(a.y + n, a.x);
        }
        else
        {
            cout << a.w;
            return 0;
        }
        q.pop();
    }
    cout << 0;
}

Codeforces-1024-Quartet Swapping

一道逆序对实际应用。以前写逆序对是看着算法书的例题写的，当时写得很迷迷糊糊……甚至之后忘记自己写过逆序对也不记得逆序对的意义了，直到看到这题，在想如何实现在一数组里如何寻找大于当前数字且序列比当前数字小的数字个数，每次遍历tle是必然……打完忽然发现……这不就是逆序对个数！？

这题的思路是奇位置偶位置各存一数组，分别sort，如果两者原数组逆序对之差为奇数，则调换倒数第一个和倒数第三个再输出。至于为什么……当时猜的。

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
70
71
72
73
74
75
76
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int cnt[2];
int c[100005];
vector<int> v[2];
//归并排序计算逆序对
void f(int a, int b, int g)
{
    long long mid;
    mid = (a + b) / 2;
    if (b - a == 0)
        return;
    f(a, mid, g);
    f(mid + 1, b, g);
    int i = a;
    int j = mid + 1;
    int l = a;
    while (i <= mid && j <= b)
    {
        if (v[g][i] <= v[g][j])
            c[l++] = v[g][i++];
        else
        {
            c[l++] = v[g][j++];
            cnt[g] += mid - i + 1;
        }
    }
    while (i <= mid)
        c[l++] = v[g][i++];
    while (j <= b)
        c[l++] = v[g][j++];
    for (int i = a; i <= b; i++)
        v[g][i] = c[i];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        v[0].clear();
        v[1].clear();
        int n;
        int x;
        cin >> n;
        cnt[0] = cnt[1] = 0;
        for (int i = 1; i <= n; ++i)
        {
            cin >> x;
            v[i % 2].push_back(x);
        }
        f(0, v[1].size() - 1, 1);
        f(0, v[0].size() - 1, 0);
        if ((cnt[0] - cnt[1]) % 2 != 0)
        {
            int p = v[n % 2].size() - 1;
            if (p >= 1)
            	//若逆序对差为奇，调换。
                swap(v[n % 2][p], v[n % 2][p - 1]);
        }
        for (int i = 0; i < max(v[0].size(), v[1].size()); ++i)
        {
            if (i < v[1].size())
                cout << v[1][i] << " ";
            if (i < v[0].size())
                cout << v[0][i] << " ";
        }
        cout << "\n";
    }
    return 0;
}

其实当时不明白为什么该思路ac。后来去补了有关逆序对的题目感觉明白了，一个数组想通过交换相邻数字达到有序状态，交换次数就是其逆序对个数。这道题目也是奇位置偶位置的数组分别通过交换相邻数字达到有序状态，若两数组逆序对之差为奇数就无法完全置换，为达到最优解选择不交换最后一对。

ICPC(Wuhan),2024-Countless Me

一道很巧妙的进制转化，看似是把数字加来减去，实际上跟单个数字大小一点关系也没有，看清这一本质之后这题就很简单了，直接变成一道进制转化题，将sum在十进制转二进制的基础上做一点小处理就好了，难以形容……应该说是十进制转n*二进制，得以将值压缩到最小状态，重点是处理好小细节。感觉训练赛有很多二进制相关的题目，都非常巧妙……让人忽然感受到二进制的魅力。

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 <iostream>
using namespace std;
long long n, x, sum = 0, ans = 0;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        sum += x;
    }
    for (int i = 30; i >= 0; i--)
    {
        //看起来是不是非常熟悉……
        if (sum > ((1 << i) - 1) * n)
        {
            long long g = sum / (1 << i);
            g = min(n, g);//这一步操作防止减多
            sum -= g * (1 << i);
            ans += (1 << i);
        }
    }
    if (sum != 0)
        ans++;//如果有剩下记得补一个1
    cout << ans;
    return 0;
}

1407:循环赛日程表

一道找规律（虽然本意应该不是找规律。

找规律第一步是分析样例！n=8时

1
2
3
4
5
6
7
8
2 3 4 5 6 7 8
1 4 3 6 5 8 7
4 1 2 7 8 5 6
3 2 1 8 7 6 5
6 7 8 1 2 3 4
5 8 7 2 1 4 3
8 5 6 3 4 1 2
7 6 5 4 3 2 1

看啊看啊看，然后发现，数字都是一对一对交换的？！然后应该思考哪些数字可以成为一对，这里注意数据，给出的n是2的次方，所以我们应该往2的次方相关去思考。而且我们不难发现，如果上面的数字是自己i的话，自己i不跟自己i打，那就跟上一个人i-1打

然后把每一行跟上一行交换的数字列举出来：

1
2
3
4
5
6
7
2: 34,56,78,1
3: 14,67,58,2
4: 12,56,78,3
5: 18,27,36,4
6: 12,34,78,5
7: 14,23,58,6
8: 12,34,56,7

列出来之后……是不是就感觉这些数字很有关联啊！可以看作第二行缺12凑对第三行缺23凑对，以此类推，然后就可以进一步发现每组凑对的数在一个二的次方两端都是对称的，比如第三行就是14，23，58，67，第五行是18，27，36，45，至此规律找得差不多了，可以开始代码实现了。如何找这个二的次方呢，设该行为i，那么这个次方数应当是i-1能够%=0的最大的2的次方数再乘以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
#include <iostream>
using namespace std;
int a[33][33];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
        a[1][i] = i + 1;
    for (int i = 2; i <= n; i++)
    {
        int k = 2;
        int g = i - 1;
        while (g % 2 == 0)
        {
            k *= 2;
            g /= 2;
        }
        for (int j = 1; j < n; j++)
        {
            if (a[i - 1][j] == i)
                a[i][j] = i - 1;
            else
            {
                int b = a[i - 1][j] - 1;
                int d = b % k;
                b /= k;
                a[i][j] = (b + 1) * k - d;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j++)
            cout << a[i][j] << " ";
        cout << "\n";
    }
}

总结——找规律之观察样例法。但是经常cf的题目样例可能会误导你找规律，这时候找规律其实就是看透题目本质。能不能看透……看运气。大胆猜测小心求证。

Prev
2025-05-23 16:36:50 # code
Next