yxy

用户名：dotcpp0787179

访问量：569

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	979
经　　验	3404
参赛次数	3
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

dp--数字三角形模型系列//闫氏dp法
浏览：31

dp--最长上升子序列模型//闫氏dp法
浏览：35

dp--数字三角形模型//闫氏dp法[最低通行费]
浏览：28

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

[食物链] 并查集 - NOI2001 提高组

　　作者: yxy　　　　发表时间：2024-10-07 18:32:11 浏览：24　|　评论：0　

原题链接：食物链[NOI2001]

# 并查集 路劲压缩
###### 根据题目将所有的动物分为 被捕食 天敌 竞争对手 三种类型 分别存放于 并查集的 三个位置 分别求各自所属的“连通块”

思路 ： 如果
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。
###### 之后给的任一一个满足以上三种情况 就行成悖论 也就是假话

##### 其实此题和正常的并查集一样 只是将动物分为三种不同的群体 就可以很轻松的判断出 当前的关系了

###### Code：
````cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long  // 个人习惯 有备无患

using namespace std;
const int N = 300005;
int n , m;
int p[N] , ans;

int find(int x)   //路劲压缩 并
{
    if (x != p[x]) p[x] = find(p[x]);

return p[x];
}

inline void solve()
{
ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0); //关闭输入输出流
cin >> n >> m;

for (int i = 1 ; i <= n * 3 ; i ++ )  p[i] = i; // 0 - n , n + 1 - 2n , 2n + 1 - 3n 分别存储 三种不同的关系群

while ( m -- )
{
    int a , b , c;
    cin >> a >> b >> c;
    if (b > n || c > n)
    {
        ans ++;
        continue;
    }

if (a == 1)
    {
        if (find(n + b) == find(c) || find(2 * n + b) == find(c))
        {
            ans ++;
            continue;
        }
        else p[find(b)] = find(c) , p[find(b + n)] = find(c + n) , p[find(n + n + b)] = find(c + n + n); 
    }
    if (a == 2)
    {
        if (b == c)
        {
            ans ++;
            continue;
        }
        if (find(b) == find(c) || find(n + n + b) == find(c))
        {
            ans ++;
            continue;
        }
        
        p[find(b)] = find(n + n + c) , p[find(b + n)] = find(c) , p[find(b + n + n)] = find(c + n);
    }

}

cout << ans << endl;

}

signed main()
{
    solve();
    return 0;
}
````

0.0分

1 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

格式错误一万年，，有没有过了的来看看（终于过了）

三进制小数（C++代码）（第11位大于1.5才能进位）

[食物链] 并查集 - NOI2001 提高组

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言训练-数字母（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

程序员的表白（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

演讲大赛评分（C语言代码）

yxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

格式错误一万年，，有没有过了的来看看（终于过了）

三进制小数 （C++代码）（第11位大于1.5才能进位）

[食物链] 并查集 - NOI2001 提高组

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言训练-数字母 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

程序员的表白 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

演讲大赛评分 （C语言代码）

三进制小数（C++代码）（第11位大于1.5才能进位）

　　评论区

C语言训练-数字母（C语言代码）

程序员的表白（C语言代码）

演讲大赛评分（C语言代码）