LCA+二分

看了題面，再看標簽：二分也就算了，但。。。LCA？？
沒錯，就是LCA！
來慢慢分析一波。。。。。

由于一次只允許跳過1顆棋子并且兩個棋子不能同時在一個點，我們以(1,2,3)為例((x,y,z)表示3個棋子分別在x,y和z位置)模擬一下.

注意紅體字部分。
不難發現，當中間數向兩邊跳時，會產生兩種未出現過的子狀態，而左右兩邊數只能取一個距離離中間數小的向中間跳，這樣產生的子狀態是上一層狀態。

看到這里，我們假設把當前狀態連條邊到子狀態，那么就有了

WOC！這不就是一棵樹嗎？
對嗎？完全正確！！

那么最小變化次數不就是求樹上兩點之間的路徑嗎？
這不禁又讓我們想起。。。LCA！
沒錯，\(dis_{(x,y)}=deep_x+deep_y-2×deep_{LCA(x,y)}\)

這樣我們就有大致的算法框架了。
先求出兩個狀態的根節點，判斷是否相同，若不相同，則直接輸出"NO"。
而根節點，其3個數必定構成等差數列，那么我們就存一個公差d和第一個數x，就可以確定了。

但注意一點:
若x,y,z為0,1,10^9，那么我們查找根節點時顯然會TLE。
如何優化？
對于上面那組樣例，我們可以想成這樣

由于這么多次都是z點和x,y之間的距離都不變，也就是說x,y沿著坐標軸平移了一段距離，那么我們就可以快速地算出增加的深度和x,y的最終位置，時間就會大大降低。

至于最后計算路徑長度，同樣我們可以二分LCA的深度，找到LCA。(類似于倍增算法，若這兩個點向上跳躍深度為x時，相等了，就往小的距離去找)

代碼:

#include<bits/stdc++.h> #define int long long using namespace std; int st[4],ed[4],dst,ded,lst,led,rtst,rted,ans,last; void Get(int x,int y,int z,int &deep,int &l,int rt) {deep=0;int d1=y-x,d2=z-y;while(d1!=d2) {d1=y-x,d2=z-y;if(d1<d2) {int a1=d2/d1,a2=d2%d1;if(a2==0) {a1--;deep+=a1;x+=a1*d1,y+=a1*d1;l=d1;rt=x;return;} else {deep+=a1;x+=a1*d1,y+=a1*d1;l=d1;}} else {int a1=d1/d2,a2=d1%d2;if(a2==0) {a1--;deep+=a1;z-=a1*d2,y-=a1*d2;l=d2;rt=x;return;} else {deep+=a1;z-=a1*d2,y-=a1*d2;l=d2;}}}l=d1,rt=x;return; } void Up(int &x,int &y,int &z,int dep){while(dep){int d1=y-x,d2=z-y;if(d1<d2){int a1=d2/d1,a2=d2%d1;if(dep<=a1){x+=dep*d1,y+=dep*d1;return;}x+=a1*d1,y+=a1*d1;dep-=a1;}else {int a1=d1/d2,a2=d1%d2;if(dep<=a1){y-=dep*d2,z-=dep*d2;return;}z-=a1*d2,y-=a1*d2;dep-=a1;}} } signed main() {scanf("%lld %lld %lld %lld %lld %lld",&st[1],&st[2],&st[3],&ed[1],&ed[2],&ed[3]);sort(st+1,st+4),sort(ed+1,ed+4);Get(st[1],st[2],st[3],dst,lst,rtst);Get(ed[1],ed[2],ed[3],ded,led,rted);//cout<<dst<<" "<<ded;if(rtst!=rted||lst!=led){puts("NO");return 0;}puts("YES");if(dst>ded){ans+=dst-ded;dst=ded;Up(st[1],st[2],st[3],ans);}else {ans+=ded-dst;ded=dst;Up(ed[1],ed[2],ed[3],ans);}int l=0,r=dst;while(l<=r){int mid=(l+r)>>1;int a1=st[1],a2=st[2],a3=st[3];int b1=ed[1],b2=ed[2],b3=ed[3];Up(a1,a2,a3,mid);Up(b1,b2,b3,mid);if(a1==b1&&a2==b2&&a3==b3){last=2*mid;r=mid-1;???}else l=mid+1;}ans+=last;cout<<ans;return 0; }

轉載于:https://www.cnblogs.com/SillyTieT/p/11185813.html

總結

以上是生活随笔為你收集整理的【BZOJ】P2144 跳跳棋的全部內容，希望文章能夠幫你解決所遇到的問題。

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