題目描述

跳跳棋是在一條數軸上進行的。棋子只能擺在整點上。每個點不能擺超過一個棋子。我們用跳跳棋來做一個簡單的 游戲：棋盤上有3顆棋子，分別在a，b，c這三個位置。我們要通過最少的跳動把他們的位置移動成x，y，z。（棋 子是沒有區別的）跳動的規則很簡單，任意選一顆棋子，對一顆中軸棋子跳動。跳動后兩顆棋子距離不變。一次只 允許跳過1顆棋子。

寫一個程序，首先判斷是否可以完成任務。如果可以，輸出最少需要的跳動次數。

輸入

第一行包含三個整數，表示當前棋子的位置a b c。（互不相同） 第二行包含三個整數，表示目標位置x y z。（互不相同）

輸出

如果無解，輸出一行NO。如果可以到達，第一行輸出YES，第二行輸出最少步數。

樣例輸入

1 2 3
0 3 5

樣例輸出

YES
2
【范圍】
100% 絕對值不超過10^9
思維神題。 考慮對于當前狀態的a,b,c有哪些可移動方案，設d1=b-a,d2=c-b，如果d1!=d2，那么b可以向兩邊跳，d1,d2其中小的那個可以向中間跳；如果d1=d2那么只能由b向兩邊跳。 可移動方案最多只有三種，那么可以將每個狀態看成一個點，往左右跳看作這個點的左右子節點，往中間跳看作是這個點的父節點，如果不能往中間跳，那這個點就是根節點。 那么所有狀態就變成了一個二叉樹森林，判斷能否完成就變成了判斷兩個狀態是否在同一棵樹中，而最小步數自然就是兩點間的距離了。 但如果將所有狀態都枚舉出來顯然不行，例如下面這個樣例： 1 2 1e9 1e9-1 1e9-2 1e9 要跳1e9級別這么多次，顯然不能暴力跳。 那么再回到求答案的那一步，兩點間的距離不就是lca分別和兩點深度差的和嗎！ 而深度就是每個點跳到根節點的步數。 那么兩點往上跳在原題中就是兩邊的點往中間跳。 因為跳的點和被跳的點之間的相對距離不變，那么就相當于將兩個點都平移了兩點間距離這么多。 假設d1>d2，那么c最多向左平移(d1-1)/d2次(因為不能跳到同一個點)。 對于d1和d2，我們可以像求gcd一樣輾轉相除來求得在二叉樹上給出的這兩點的深度，然后將深度深的點往上跳使兩點深度相同。 接下來只要找到深度相同的這兩個點的lca就好了，可以像求倍增lca一樣往上跳驗證，也可以用二分答案來往上跳驗證。 我這里用了二分的寫法。注意原題三個數不一定按順序給出。 #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<vector> #include<bitset> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll a,b,c; ll x,y,z; ll dep1,dep2; ll root1,root2; ll l1,l2; ll len; void cmp(ll &a,ll &b,ll &c) {if(a>b){swap(a,b);}if(a>c){swap(a,c);}if(b>c){swap(b,c);} } ll find_root(ll a,ll b,ll c,ll &dep,ll &anc) {ll d1=b-a;ll d2=c-b;while(d1!=d2){if(d1<d2){ll s=d2/d1;ll t=d2%d1;if(t==0){dep+=(s-1);anc=d1;return a+(s-1)*d1;}else{dep+=s;a+=s*d1;d2=t;}}else{ll s=d1/d2;ll t=d1%d2;if(t==0){dep+=(s-1);anc=d2;return a;}else{dep+=s;d1=t;}}}dep=0;anc=d1;return a; } void get_fa(ll &a,ll &b,ll &c,ll dep) {ll d1=b-a;ll d2=c-b;while(dep>0){if(d1<d2){ll s=d2/d1;ll t=d2%d1;if(s>=dep){a+=dep*d1;b+=dep*d1;if(b==c){b=a;a-=d1;}return ;}else{dep-=s;a+=s*d1;b+=s*d1;d2=t;}}else{ll s=d1/d2;ll t=d1%d2;if(s>=dep){c-=dep*d2;b-=dep*d2;if(a==b){b=c;c+=d2;}return ;}else{dep-=s;b-=s*d2;c-=s*d2;d1=t;}}} } int main() {scanf("%lld%lld%lld",&a,&b,&c);scanf("%lld%lld%lld",&x,&y,&z);cmp(a,b,c);cmp(x,y,z);l1=find_root(a,b,c,dep1,root1);l2=find_root(x,y,z,dep2,root2);if(l1!=l2||root1!=root2){printf("NO");return 0;}if(dep1<dep2){len+=dep2-dep1;get_fa(x,y,z,len);}else{len+=dep1-dep2;get_fa(a,b,c,len);}ll l=0;ll r=min(dep1,dep2);ll ans=0;while(l<=r){ll mid=(l+r)/2;ll a1=a,b1=b,c1=c;ll x1=x,y1=y,z1=z;get_fa(a1,b1,c1,mid);get_fa(x1,y1,z1,mid);if(a1==x1&&b1==y1&&c1==z1){ans=mid;r=mid-1;}else{l=mid+1;}}printf("YES\n");printf("%lld",len+ans*2); }

轉載于:https://www.cnblogs.com/Khada-Jhin/p/9776977.html

總結

以上是生活随笔為你收集整理的BZOJ2144跳跳棋——LCA+二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。