食物連鎖
2996 ワード
テキストリンク:https://blog.csdn.net/yjr3426619/article/details/82315133
動物王国には3種類の動物A,B,Cがあり,この3種類の動物の食物連鎖は興味深い環状を構成している.
AはBを食べ、BはCを食べ、CはAを食べる.
既存のN個の動物は、1−Nで番号付けされている.
どの動物もA,B,Cの一種ですが、どれなのか分かりません.
このN個の動物が構成する食物連鎖関係を2つの説で説明する人がいる.
1つ目の言い方は「1 X Y」で、XとYが同類であることを表す.
2つ目の言い方は「2 X Y」で、XがYを食べることを表します.
この人はN個の動物に対して、上記の2つの言い方を使って、次から次へとK文の言葉を言って、このK文の言葉はあるのは本当で、あるのは偽物です.
一言が次の3つの1つを満たすと、この言葉はうそで、そうでなければ本当のことです.
1)現在の話は前のいくつかの本当の話と衝突し、うそである.2)現在の話ではXやYがNより大きく、うそである.3)現在の言葉はXがXを食べることを意味し,うそである.
あなたの任務は、与えられたN文とK文に基づいて、偽話の総数を出力することです.
入力フォーマット
最初の行は2つの整数NとKで、1つのスペースで区切られています.
以下のK行は、行ごとに3つの正の整数D,X,Yであり、2つの数の間に1つのスペースで区切られており、Dは言い方の種類を表す.
D=1であれば、XとYは同類であることを示す.
D=2なら、XがYを食べることを表す.
出力フォーマット
うその数を表す整数は1つしかありません.
データ範囲
1≤N≤500001≤N≤50000, 0≤K≤1000000≤K≤100000
サンプルを入力:
出力サンプル:
この問題では相対関係が食物連鎖上の関係であるため,重みを持って集中した重み値を調べるには,2つの動物の食物連鎖上の相対関係を記録すべきであり,A−>Bは0で同類を表し,1はAがBを食べ,2はAがBに食べられることを示す.この値は前の2つの問題の区間合、点数差とは異なり、直接加算することはできません.3つの問題を考慮します.
1.パス圧縮時のValueの更新方法
もし今A->Bが1ならば、B->Cは1で、どのようにA->Cを求めますか?明らかにAはBを食べて、BはCを食べて、それでは題意CはAを食べるべきで、それではA->Cは2であるべきです;
もし今A->Bが2ならば、B->Cは2で、どのようにA->Cを求めますか?明らかにBはAを食べて、CはBを食べて、それでは題意AからCを食べるべきで、それではA->Cは1であるべきです;
もし今A->Bが0であるならば、B->Cは1で、どのようにA->Cを求めますか?明らかにA、Bは同類で、BはCを食べて、それでは題意AからCを食べるべきで、それではA->Cは1であるべきです;
法則を探すと,A−>C=(A−>B+B−>C)%3であるため,関係値の更新には再モード3の累積が必要であることが容易に分かった.
2.区間連結時のバリューの更新方法
1から明らかなように,本題のValue更新は複数の型取り操作にほかならないので,区間統合の更新操作を検証するのは難しくない.
relationWithParent[fx] = (-relationWithParent[x] + relation + relationWithParent[y]) % 3
3.矛盾しているかどうかをどう判断するか
点数、区間和とは異なり、直接減算して計算結果を得ることができます.ここで、Aとルートノードの関係が既知であれば、Bとルートノードの関係を解決するには、A、Bの関係をどのように求めますか.関係値の計算は型3を要するため、A->B=(A->C-B->C+3)%3、プラス3は負数の影響を避けるためである.A->Bとタイトルから与えられたRelation値判定などを比較すればよい.
なお,本題で与えられたrelation値はいずれも1または2であり,実際に処理する場合,この値は1を減らすべきである.
動物王国には3種類の動物A,B,Cがあり,この3種類の動物の食物連鎖は興味深い環状を構成している.
AはBを食べ、BはCを食べ、CはAを食べる.
既存のN個の動物は、1−Nで番号付けされている.
どの動物もA,B,Cの一種ですが、どれなのか分かりません.
このN個の動物が構成する食物連鎖関係を2つの説で説明する人がいる.
1つ目の言い方は「1 X Y」で、XとYが同類であることを表す.
2つ目の言い方は「2 X Y」で、XがYを食べることを表します.
この人はN個の動物に対して、上記の2つの言い方を使って、次から次へとK文の言葉を言って、このK文の言葉はあるのは本当で、あるのは偽物です.
一言が次の3つの1つを満たすと、この言葉はうそで、そうでなければ本当のことです.
1)現在の話は前のいくつかの本当の話と衝突し、うそである.2)現在の話ではXやYがNより大きく、うそである.3)現在の言葉はXがXを食べることを意味し,うそである.
あなたの任務は、与えられたN文とK文に基づいて、偽話の総数を出力することです.
入力フォーマット
最初の行は2つの整数NとKで、1つのスペースで区切られています.
以下のK行は、行ごとに3つの正の整数D,X,Yであり、2つの数の間に1つのスペースで区切られており、Dは言い方の種類を表す.
D=1であれば、XとYは同類であることを示す.
D=2なら、XがYを食べることを表す.
出力フォーマット
うその数を表す整数は1つしかありません.
データ範囲
1≤N≤500001≤N≤50000, 0≤K≤1000000≤K≤100000
サンプルを入力:
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
出力サンプル:
3この問題では相対関係が食物連鎖上の関係であるため,重みを持って集中した重み値を調べるには,2つの動物の食物連鎖上の相対関係を記録すべきであり,A−>Bは0で同類を表し,1はAがBを食べ,2はAがBに食べられることを示す.この値は前の2つの問題の区間合、点数差とは異なり、直接加算することはできません.3つの問題を考慮します.
1.パス圧縮時のValueの更新方法
もし今A->Bが1ならば、B->Cは1で、どのようにA->Cを求めますか?明らかにAはBを食べて、BはCを食べて、それでは題意CはAを食べるべきで、それではA->Cは2であるべきです;
もし今A->Bが2ならば、B->Cは2で、どのようにA->Cを求めますか?明らかにBはAを食べて、CはBを食べて、それでは題意AからCを食べるべきで、それではA->Cは1であるべきです;
もし今A->Bが0であるならば、B->Cは1で、どのようにA->Cを求めますか?明らかにA、Bは同類で、BはCを食べて、それでは題意AからCを食べるべきで、それではA->Cは1であるべきです;
法則を探すと,A−>C=(A−>B+B−>C)%3であるため,関係値の更新には再モード3の累積が必要であることが容易に分かった.
2.区間連結時のバリューの更新方法
1から明らかなように,本題のValue更新は複数の型取り操作にほかならないので,区間統合の更新操作を検証するのは難しくない.
relationWithParent[fx] = (-relationWithParent[x] + relation + relationWithParent[y]) % 3
3.矛盾しているかどうかをどう判断するか
点数、区間和とは異なり、直接減算して計算結果を得ることができます.ここで、Aとルートノードの関係が既知であれば、Bとルートノードの関係を解決するには、A、Bの関係をどのように求めますか.関係値の計算は型3を要するため、A->B=(A->C-B->C+3)%3、プラス3は負数の影響を避けるためである.A->Bとタイトルから与えられたRelation値判定などを比較すればよい.
なお,本題で与えられたrelation値はいずれも1または2であり,実際に処理する場合,この値は1を減らすべきである.
#include
using namespace std;
const int N = 50000 + 10;
int p[N],dis[N];
//0
//1 A B
//2 B A
int find(int x)
{
if(x != p[x])
{
int px = p[x];
p[x] = find(p[x]);
dis[x] = (dis[x] + dis[px]) % 3;
}
return p[x];
}
int main()
{
int n,k;
cin>>n>>k;
int ans = 0;
for(int i=1; i<=n; i++) p[i] = i;
while(k--)
{
int a,b,w;
cin>>w>>a>>b;
if(a >n || b > n || (a == b && w == 2))
{
ans++;
continue;
}
w--;
int pa = find(a);
int pb = find(b);
if(pa == pb)
{
if((dis[a] - dis[b] + 3) % 3 != w) ans++;
}
else
{
p[pa] = pb;
dis[pa] = (-dis[a] + dis[b] + w + 3) % 3;
}
}
cout<