建站资源共享,建公司网站一般多少钱,网站如何防盗链,wordpress修改注册[NOI2001] 食物链
题目描述
动物王国中有三类动物 A , B , C A,B,C A,B,C#xff0c;这三类动物的食物链构成了有趣的环形。 A A A 吃 B B B#xff0c; B B B 吃 C C C#xff0c; C C C 吃 A A A。
现有 N N N 个动物#xff0c;以 1 ∼ N 1 \sim N 1∼N 编号。…[NOI2001] 食物链
题目描述
动物王国中有三类动物 A , B , C A,B,C A,B,C这三类动物的食物链构成了有趣的环形。 A A A 吃 B B B B B B 吃 C C C C C C 吃 A A A。
现有 N N N 个动物以 1 ∼ N 1 \sim N 1∼N 编号。每个动物都是 A , B , C A,B,C A,B,C 中的一种但是我们并不知道它到底是哪一种。
有人用两种说法对这 N N N 个动物所构成的食物链关系进行描述
第一种说法是 1 X Y表示 X X X 和 Y Y Y 是同类。第二种说法是2 X Y表示 X X X 吃 Y Y Y。
此人对 N N N 个动物用上述两种说法一句接一句地说出 K K K 句话这 K K K 句话有的是真的有的是假的。当一句话满足下列三条之一时这句话就是假话否则就是真话。
当前的话与前面的某些真的话冲突就是假话当前的话中 X X X 或 Y Y Y 比 N N N 大就是假话当前的话表示 X X X 吃 X X X就是假话。
你的任务是根据给定的 N N N 和 K K K 句话输出假话的总数。
输入格式
第一行两个整数 N , K N,K N,K表示有 N N N 个动物 K K K 句话。
第二行开始每行一句话按照题目要求见样例
输出格式
一行一个整数表示假话的总数。
样例 #1
样例输入 #1
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5样例输出 #1
3提示
对于全部数据 1 ≤ N ≤ 5 × 1 0 4 1\le N\le 5 \times 10^4 1≤N≤5×104 1 ≤ K ≤ 1 0 5 1\le K \le 10^5 1≤K≤105。
这是一道没本事的中等题看过的人都知道用指针做。不过在实操的过程中有几个小点需要注意 先看代码
#includeiostream
#includealgorithm
using namespace std;
const int N50010;
int n,k,res;
int p[N],d[N];
int find(int x)
{if(p[x]!x){int tfind(p[x]);d[x]d[p[x]];p[x]t;}return p[x];
}
int main()
{cinnk;for(int i1;in;i){p[i]i;}while(k--){int m,x,y;cinmxy;if(xn||yn){res;}else{int pxfind(x),pyfind(y);if(m1){if(pxpy(d[x]-d[y])%3)res;else if(px!py){p[px]py;d[px]d[y]-d[x];}}else{if(pxpy(d[x]-d[y]-1)%3)res;else if(px!py){p[px]py;d[px]d[y]-d[x]1;}}}}coutres;return 0;
}小点1
d[px]d[y]-d[x] 和 d[px]d[y]-d[x]1 是怎么来的 根据指针指向m1时d[x]?d[y]?d[y]-d[x]m2时d[x]?-1d[y]?d[y]-d[x]1。
小点2
find 函数
int find(int x)
{if(p[x]!x){int tfind(p[x]);d[x]d[p[x]];p[x]t;}return p[x];
}这样是对的大家都能看出来但有没有人觉得 t 有些多余 想改成这样
int find(int x)
{if(p[x]!x){d[x]d[p[x]];p[x]find(x);}return p[x];
}但这样是过不了的 下面的代码却能过
int find(int x)
{if(p[x]!x){int tfind(p[x]);d[x]d[p[x]];p[x]find(p[x]);}return p[x];
}发现问题所在了吗 一般情况下t 确实无用但这是递归p[x] 要不要变要的但在什么时候变 一定要在先 find(p[x]) 再更新 d[x]为什么 因为这是递归递归什么特点 从最后一种情况慢慢往前推因为你没有办法保证 d[p[x]] 一开始一定存在所以需要不断地更新 d[x]。
