跳棋「LCA+二分答案」

跳棋「LCA+二分答案」
タイトルの説明
ジャンプは1本の数軸で行われる.駒は整点にしか並べられない.ポイントごとに1つ以上の駒を並べてはいけません.
私たちはジャンプ将棋で簡単なゲームをします.碁盤には3つの駒があり、それぞれ(a,b,c)の3つの位置にあります.私たちは最小限のジャンプで彼らの位置を(x,y,z)に移動します.(駒は区別がない)
ジャンプのルールは簡単で、任意に1つの駒を選んで、1つの中軸の駒に対してジャンプします.ジャンプ後の2つの駒の距離は変わらない.一度に(1)個の駒をスキップすることしか許されません.
プログラムを書いて、まず任務を完成できるかどうかを判断します.できれば、最低必要なジャンプ回数を出力します.
入力フォーマット
最初の行には、現在の駒の位置(a)(b)(c)を表す3つの整数が含まれます.(互いに異なる)
2行目には、ターゲット位置(x)(y)(z)を表す3つの整数が含まれます.(互いに異なる)
出力フォーマット
解がない場合は、行(NO)を出力します.
到着可能であれば、第1行出力(YES)、第2行出力の最小ステップ数.
入出力サンプル
入力#1

1 2 3
0 3 5

出力#1

YES
2

説明/ヒント
(20)%入力整数の絶対値が(10)を超えない
(40)%入力整数の絶対値が(10000)を超えない
(100)%絶対値が(10^{9})を超えない
構想分析
本こんにゃくは物を详しく言うのが好きだから、ちょっと长いです.
この問題は神レベルのモデリングです!-姚さん
考えが立たない
神格のモデリング、暗示は見えません
清華合宿、本こんにゃくが似合わないことを暗示
この問題は本当に思いがけず(LCA)が断固として1つの特判1つのNOをだまして点数をだまし取ることができるとは思わなかった.

この問題は3つの駒しかなく、駒の移動は比較的単一であり、数え切れない状況を構成することができるが、これを突破点とする

である.

は、3つの駒の初期位置が(x,y,z)であると仮定し、駒の移動状況はほぼ2つである.

両端から中間へジャンプ

中間両端にジャンプ

は、第(2)種の場合、駒の鼓動には制限がなく、どのくらい跳べばどのくらい跳べるか、第1種の場合

が鍵であることを発見した.

第(1)種の場合は、(x)から(y)までの距離を(d_{1})、(y)から(z)までの距離を(d_{2})とし、この場合は3つの小さな状況(注意はいずれも中間)を区別することができる.

(d_{1})>(d_{2}):この場合は(z)のみが(x),(y)の中間にジャンプでき、(y)と(z)が左に平行移動する(d_{2})個の単位長(ここでの(xyz)は3個の駒の相対順序であり、番号ではない)

(d_{1}:上記の場合と同様、(x)ホッピングは、(x)と(y)の右へ移動(d_{1})個の単位長

に等しい

(d_{1}==d_{2}):漕ぎ~重~点~.容易に発見して、この時両側の駒はすでに中間に跳ぶことができなくて、私達はそれを究極の状態になって、再び突破点

を見つけます

この究極の状態を出発点とし,駒の花形ジャンプによって多くの状態を飛び出すことができ,これをサブ状態と呼ぶ.明らかな1つの性質は、この究極の状態の任意の2つのサブ状態が、まず究極の状態に変換することによって、互いに互いの状態

に達することができることである.

ここから、何を連想していますか??木に似ているのではないでしょうか.究極の状態はルートノードであり,サブ状態はこのツリー上の任意のノードである.では,2つの駒の状態が互いに転化できるかどうかについては,ノード,すなわち究極の状態が同じかどうかを判断するだけでよいが,各ノードは3点の座標の構造体である.

の最小ステップ数はここまでも明らかであるべきで、互いに転化できるかどうかを判断する思想と似ているが、究極の状態に飛び込む必要はないが、同じ中間状態で転化する必要があり、しかもステップ数が最小である必要がある.それは最近の公共祖先(LCA)ではないか.

最後の問題が残っています.データの範囲がこんなに広いので、木を建ててはいけませんか.どうやって収束するの?遷移過程を考慮すると,(1,2,1 e 9)のようなデータに対しては,実際にホッピングの回数を一度に処理できるが,この場合,ホッピング毎の距離は同じであるため,連続ホッピング(k=(d_{2}−1)/d_を求めることができる.{1})次後(d_{1}>=d_{2})(記憶-1、そうでなければ重なる可能性がある)

それでは公共の祖先はこの数軸の上で2分列挙することができて、この問題は基本的に

を解決します
詳細はコードを参照
Code

#include
#include
#include
#include
using namespace std;
inline int read(){
	int x = 0,f = 1;
	char ch = getchar();
	while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x = (x<<1)+(x<<3)+(ch^48);ch = getchar();}
	return x*f;
}
const int inf = 0x3f3f3f3f;
struct Node{
	int x,y,z;
	void Init(){
		x = read(),y = read(),z = read();
		if(x>y)swap(x,y); //      
		if(x>z)swap(x,z);
		if(y>z)swap(y,z);
	}
}a,b,ra,rb;
bool check(Node u,Node v){ //          
	return u.x==v.x&&u.y==v.y&&u.z==v.z;
}
int step,k;
Node getroot(Node t,int s){ //       ，s    ，step      
	for(step=0;s;step+=k){
		int d1 = t.y-t.x,d2 = t.z-t.y;
		if(d1==d2)return t;
		if(d1>1; //        ，   
		if(check(getroot(a,mid),getroot(b,mid)))r = mid;
		else l = mid+1;
	}
	printf("YES
%d
",(l<<1)+step1-step2);//  ×2   a   
}