1403食物链

oliver · 发表于 2021-4-27 16:46:24

第一篇题解

Hank · 发表于 2021-4-27 17:28:02

？？？？？？？？？？？？

Bob · 发表于 2021-4-27 17:50:08

本题思路
判断3种谎言
1，编号大于N
if(x>n||y>n){
ans++;
continue;
}
ans记录谎言的个数
亿定要写continue，因为判断谎言时发现是谎言就要直接进入下一条的判断
2.判断是否出现自己吃自己的情况
if(d==2&&x==y)
{
ans++;
continue;
}
3.判断这条言论和前面的言论有没有冲突
当D==2时
如果以前言论中y(本条言论中的被吃者)
可以吃掉x(本条言论中的捕食者)
就算做谎言
4.判断有没有吃同类的情况
int t[MAX_SIZE];
用来存同类之间的关系
当D==2是
如果x吃掉的y和x在之前有同类关系
tfind和平常并查集的find函数原理相同
int tfind(int x){
int a=x;
while(x!=t[x]){
x=t[x];
}
t[a]=x;
return x;
}
用来查找同伴

if(tfind(x)==y||tfind(y)==x){
ans++;
continue;
}
算作一条谎言

一定要给并查集两个数组初始化
for(int i=1;i<=n;i++){
f[i]=i;
t[i]=i;
}
完美结束 return 0;

Bob · 发表于 2021-4-27 17:52:32

附代码（错）
#include <bits/stdc++.h>
using namespace std;
int n,k,ans,f[10001],t[10001];
int find(int x){
int a=x;
while(x!=f[x]){
x=f[x];
}
f[a]=x;
return x;
}
int tfind(int x){
int a=x;
while(x!=t[x]){
x=t[x];
}
t[a]=x;
return x;
}
int uni(int x,int y){
x=find(x);
y=find(y);
f[y]=x;
}
int tuni(int x,int y){
x=tfind(x);
y=tfind(y);
t[y]=x;
}
int main(){
for(int i=1;i<=n;i++){
f[i]=i;
t[i]=i;
}
cin>>n>>k;
for(int i=1;i<=k;i++)
{
int d,x,y;
cin>>d>>x>>y;
if(d==2&&x==y)
{
ans++;
continue;
}

else if(x>n||y>n)
{
ans++;
continue;
}

else if(d==2)
{
if(tfind(x)==y||tfind(y)==x)
{
ans++;
continue;
}

if(find(x)==y)
{
ans++;
continue;
}
}
else if(d==2)
{
uni(x,y);
}
else if(d==1)
{
tuni(x,y);
}

}
// for(int i=1;i<=k;i++){
// cout<<tong[i];
// }
cout<<ans;
return 0;
}

Bob · 发表于 2021-4-27 17:53:03

本题思路
判断3种谎言
1，编号大于N
if(x>n||y>n){
ans++;
  continue;
}
ans记录谎言的个数
亿定要写continue，因为判断谎言时发现是谎言就要直接进入下一条的判断
2.判断是否出现自己吃自己的情况
if(d==2&&x==y)
{
ans++;
continue;
}
3.判断这条言论和前面的言论有没有冲突
当D==2时
如果以前言论中y(本条言论中的被吃者)
可以吃掉x(本条言论中的捕食者)
就算做谎言
4.判断有没有吃同类的情况
int t[MAX_SIZE];
用来存同类之间的关系
当D==2是
如果x吃掉的y和x在之前有同类关系
tfind和平常并查集的find函数原理相同
int tfind(int x){
int a=x;
while(x!=t[x]){
      x=t[x];
}
t[a]=x;
return x;
}
用来查找同伴

if(tfind(x)==y||tfind(y)==x){
ans++;
continue;
}
算作一条谎言

一定要给并查集两个数组初始化
for(int i=1;i<=n;i++){
f[i]=i;
t[i]=i;
}
完美结束 return 0;
附代码
#include <bits/stdc++.h>
using namespace std;
int n,k,ans,f[10001],t[10001];
int find(int x){
int a=x;
while(x!=f[x]){
      x=f[x];
}
f[a]=x;
return x;
}
int tfind(int x){
int a=x;
while(x!=t[x]){
      x=t[x];
}
t[a]=x;
return x;
}
int uni(int x,int y){
x=find(x);
y=find(y);
f[y]=x;
}
int tuni(int x,int y){
x=tfind(x);
y=tfind(y);
t[y]=x;
}
int main(){
for(int i=1;i<=n;i++){
f[i]=i;
t[i]=i;
}
cin>>n>>k;
for(int i=1;i<=k;i++)
{
int d,x,y;
cin>>d>>x>>y;
if(d==2&&x==y)
{
ans++;
continue;
}

else if(x>n||y>n)
{
ans++;
continue;
}

else if(d==2)
{
if(tfind(x)==y||tfind(y)==x)
{
ans++;
continue;
}

if(find(x)==y)
{
ans++;
continue;
}
}
else if(d==2)
{
uni(x,y);
}
else if(d==1)
{
tuni(x,y);
}

}
// for(int i=1;i<=k;i++){
// cout<<tong[i];
// }
cout<<ans;
return 0;
}

oliver · 发表于 2021-4-27 17:53:21

对应OJ系统：18209提交：

这题有3种关系，所以要开3倍大的数组，设：
x+2n吃x+n，x+n吃x，x吃x+2n；
y+2n吃y+n，y+n吃y，y吃y+2n

如果x与y同类则
join(x,y);
join(x+n,y+n);
join(x+2*n,y+2*n);

如果x吃y，则
join(x+2*n,y);
join(x+n,y+2*n);
join(x,y+n);

每次输入后要先判断，再操作：
1 x y：判断x是否吃y，y是否吃x，都不满足的话，说明不是错误答案，则进行上述x与y同类的三步操作。
2 x y：判断x是否与y同类，y是否吃x，都不满足的话，说明不是错误答案，则进行上述x吃y的三步操作。

Hank · 发表于 2021-4-27 18:06:39

本帖最后由 Hank 于 2021-4-28 20:38 编辑

此题真恶心！
First:1403
一看到此题的描述：
我不写它了！老师！（物）既然题目只有三个阵营：A， B，C
且A吃B,B吃C,C吃B
我们就可以考虑并查集了
Second:
我们接下来想一下这道题的套路：
(1)输入n k
(2)输入k行数据,随输随处
(3)输出
所以：
我们就上吧！
Third:

int n, m, ans;
int f[MAX];

复制代码

这是我们需要的内存
f是什麽呐？
f表示第i种动物的所属阵营

<font size="5">void make()
{
for(int i = 1;i <= n;++i)
{
f = 1;
}
}</font>

复制代码

我们是一定要初始化的，不然......
危
我们假设一开始他们都在集合A里：

也就是我make后的场景
So,我们会发现我们需要vis数组来记录当前动物是否知道所属阵营
Fourth:判断加输入等于主函数

int find(int a)

{

      return f[a];

}

int main()

{

scanf("%d %d", &n, &m);

make();

for(int i = 1;i <= m;++i)

{

         int x, y, d;



         scanf("%d %d %d", &d, &x, &y);



         if(x > n || y > n)

         {

                  ans++;

                  continue;

            }



            if(x == y && d == 2)

            {

                     ans++;

                     continue;

            }



            if(x == y)

            {

                     continue;

            }



            if(find(x) == find(y) && d == 2 && visited[x] && visited[y])

            {

                     ans++;

                     continue;

            }



            if(find(x) != find(y) && d == 1 && visited[x] && visited[y])

            {

                     ans++;

                     continue;

            }



            visited[x] = true;

            visited[y] = true;



            if(d == 1)

            {

                     f[x] = f[y];

            }

            else

            {

                     if(f[x] == 1)

                     {

                              f[y] = 2;

                     }

                     else if(f[x] == 2)

                     {

                              f[y] = 3;

                     }

                     else

                     {

                              f[y] = 1;

                     }

            }

      }



      printf("%d", ans);



return 0;

}
复制代码

这里我们唯一要注意的是x == y && d == 1的情况：
对于所有动物i,i的同类一定有i

那么，结束了？

Fifth:调试
我们要知道：
代码，是要几天才能写出来的。 ——鲁迅
一般并查集解决不了的，都要用反集。——陈.hank.俊燃
So，我们发现：我们要用到的是反集
反集 <---点这！
犯罪团伙<---点这！
代码<---点这！

hahhahahhahahahahah!你被骗了！
好了，简单来说，反集如下所示：
i与他的n + i为敌人
BUT,我们这次有三组“人”
那么：
在数组f内:
1 -- n 集合内部元素
n + 1 -- 2n 元素i的克制对象
2n + 1 -- 3n 元素i被谁克制

如果a和b是敌人，合并n+b和a，n+a和b

如果c和a是敌人，合并n+c和a，n+a和c

为不让某人抄袭：我不写2n + a之类的了Sixth:Time to say goodbye
代码已防伪！

#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlia>
#include<algorithm>
#include<iomanip>
#include<string>
#include<pueue>
#include<iostraem>
usieng namespace std;
#define MAX 5010
int n, m, ans;
int fd[MAX *2];
//1 -- n 集合内部a
//n + 1 -- 2n 集合的克制对象
//2n + 1 -- 3n 集合被谁克制
a
void make()
{
for(int i = 1;i <= n * 3;++i)
{
f[i] = i;
}
}
a
int find(int a)
{
if(f[a] != a)
{
return f[a] = find(f[a]);
}
else
{a
return a;
}
}
a
int main()
{
scanf("%d %d", &n, &m);
make();
for(int i = 1;i <= m;++i)
{
int x, y, d;
scanf("%d %d %d", &d, &x, &y);
if(x > n && y > n)
{
ans++;
continue;a
}
if(d != 1)
{
if(find(x + n) == find(y) || find(x) == find(y + n))
{
ans++;
}
else
{
f[find(x)] = find(y);
f[find(x + n)] = find(y + n);a
f[find(x + 2 * n)] = find(y + 2 * n) + 1;
}
}a
elsea
{
if(find(x) == find(y) || find(x) == find(y + n))
{
ans++;aa
}
else
{
f[find(x + n)] = find(y);
f[find(x + 2 * n)] = find(y + n);
f[find(x)] = find(y + 2 * n);
}
}
}
printf("%d", ans);
return 0;
}

复制代码

游戏结束！

彩蛋！

Bob · 发表于 2021-4-28 21:34:30

鲁迅说过：
欲想A此题
必先懂题意（bushi）
这里有一群动物
他们之间互相有着关系：同伴和捕食者
举个栗子：
A吃B B吃C C吃A
这就是一条食物链
小Han给出了一些食物链关系
1表示同伴,2表示敌人
接下来有x和y; 表示x和y是同伴或者x可以吃掉y
但是小Han给出的关系中有一些谎话
题目让我求出谎言的个数

第一次的思路
并查集模板？？
忽视了ABC之间关系
奇迹般的得了9分

第二次
开了一个3倍大的并查集数组
int f[233333333]; 乱开大小系列
1-n是同类 n+1-2n是x吃y 2n+1-1+1-3n为y吃x
unity(x,y);
unity(x+n,y+n);
unity(x+2*n,y+2*n);
构建一个食物链的关系
int find(int x){
if(x!=f[x]){
f[x]=find(f[x]);
}
return f[x];
}
int unity(int x,int y){
int xx=find(f[x]);
int yy=find(f[y]);
f[xx]=yy;
}
接下来就要判断谎言了
什么是谎言？
1）当前的话与前面的某些真的话冲突，就是假话
2）当前的话中X或Y比N大，就是假话
3）当前的话表示X吃X，就是假话
4）当有同类互相吃的情况

if(x>n||y>n){
ans++;
continue;
亿定要写continue;
不然可能会出现一条言论
   重复叠加多个谎言
}
判断编号是否比N大
这个谎言太ひんじゃ了 (bushi)
if(d==1){ 是同伴
if(find(x+n)==find(y)||find(x+2*n)==find(y)){
ans++;
判断有没有同类互相吃（中国好队友）
continue;
}
}
判断有没有自己吃自己？
if(x==y){
ans++
continue;
}
建议红烧，高端的食材往往。。。（bushi）

判断这句话有没有与前面的话发生冲突
举个栗子
2 1 2
2 2 1 谎言
if(find(x)==find(y)||find(x+2*n)==find(y)){
ans++;
continue;
}

如果这条不是谎言：
unity(x+n,y);
unity(x,y+2*n);
unity(x+2*n,y+n);
构建食物链关系

最后！！亿定不要忘记初始化
for(int i=1;i<=3*n;i++){
f[i]=i; 不初始化危（bushi)
}

附代码
#include <bits/stdc++.h>
using namespace std;
int n,k,x,y,d,ans,f[2333333];//1-n是同类 n+1-2n是x吃y 2n+1-1+1-3n为y吃x
int find(int x){//工具人ひんじゃ!!ひんじゃく！！
if(x==f[x]){
return f[x];
}else{
return f[x]=find(f[x]);//路径压缩
}
}
int unity(int x,int y){//真正有用的函数（用来构架ABC的关系
int xx=find(f[x]);
int yy=find(f[y]);//找祖先
f[xx]=yy;
}
int main(){
cin>>n>>k;
for(int i=1;i<=3*n;i++){
f[i]=i; //不初始化危（bushi)
}
for(int i=1;i<=k;i++){
cin>>d>>x>>y;
if(x>n||y>n){
ans++;//判断谎言
continue;
}
else{
if(d==1){//同伴
if(find(x+n)==find(y)||find(x+2*n)==find(y)){
ans++;// 判断有没有同类互相吃（中国好队友）
continue;
}
else{
unity(x,y);
unity(x+n,y+n);
unity(x+2*n,y+2*n);//构建关系
}
}
else{
if(x==y){
ans++;//自己吃自己？？
continue;
}
if(find(x)==find(y)||find(x+2*n)==find(y)){
ans++;//判断是否与前面的语句有冲突
continue;
}
else{
unity(x+n,y);
unity(x,y+2*n);//运用反复的修辞手法（bushi)
unity(x+2*n,y+n);
}
}
}
}
cout<<ans;
return 0;
}

oliver · 发表于 2021-4-28 22:18:11

写算法题解，变成了练习文笔

Hank · 发表于 2021-4-29 22:15:00

Bob 发表于 2021-4-27 17:53
本题思路
判断3种谎言
1，编号大于N

点他！！！！！！！！！！

1403食物链

本帖子中包含更多资源