1.蓝桥侦探

原题链接:https://www.lanqiao.cn/problems/1136/learning/

题解:

// 拓展域并查集
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e6 + 10;
int p[N];
int res;  // 记录问题答案 

int find(int x)  // 返回x所在的集合 + 路径压缩
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];    
} 

void join(int x,int y)  // 集合合并 
{
    p[find(x)] = find(y); 
}

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

    // 构造一个2n区域的集合 
    for(int i = 1; i <= 2 * n; i ++) p[i] = i;

    while(m--)
    {
        int x,y;
        cin >> x >> y; 
        if(find(x) == find(y) ||find(x+n) == find(y+n))
        {
            res = x;
            break;  
        }       
        join(x,y+n);
        join(y,x+n);
    } 

    cout << res << endl;

  return 0; 
} 

知识点与注意事项:

// 并查集模板
int find(int x)  // 返回x的所在集合 + 路径压缩 
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

2.小明的衣服(贪心)

原题链接:https://www.lanqiao.cn/problems/1228/learning/

题解:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long LL;
LL res;

int main()
{
    LL n;
    cin >> n;
    // 用优先队列实现哈夫曼树的建树过程 
    priority_queue<LL,vector<LL>,greater<LL>> q;

    for(int i = 1; i <= n; i ++) 
    {
        int x;
        cin >> x;
        q.push(x);
    }

    while(q.size() > 1)
    {
        LL a = q.top();q.pop();
        LL b = q.top();q.pop();
        LL c = a + b;
        res += c;
        q.push(c); 
    }

    cout << res << endl;

 return 0;
} 

知识点与注意事项:

// 优先队列默认为大根堆
priority_queue <int,vector<int>,greater<int>> heap;  // 重载为小根堆

// 注意数据范围!!!!!!