Throw 【NOIP2016提高A组模拟8.15】

题目（bzoj2144）

样例输入： 1 2 3 0 3 5

样例输出： YES 2

数据范围：

---

剖解题目

初始三个数，每一次操作可以改变两个数，问最少几次能够达到目标三个数。

---

思路

这题很不一般，做时一直是一脸懵逼，除了暴力什么都想不出来。(。・・)ノ

---

解法

20%：暴力，时间复杂度： O(n3) （注：这里的n指max|A[i]|）。 40%：捣鼓一段后，发现这三个数可以转换成其他三种状态，设这这个三元组（x,y,z）(x < y < z),设l=y-x,r=z-y，它可以转化成(x+l,y+l,z),(x,y-r,z-r)。这是指中间的数向两边跳的两种情况。当（l< r）时，可变成（x-l,y-l,z），当（l>r）时，可变成（x,y+r,z+r）。这是两边往中间跳的情况，当（l=r）时，不可变成任何状态。 我们发现，对于任意一个状态，它至多可以变化成三个状态，只有一个有两种状态，那么这就构成了一棵二叉树，我们目的就是求出两个状态是否能够找到一个lca，以及两个及节点与lca的距离的和，暴力查找即可。时间复杂度： O(n2) 100%：我们知道，求lca正常方法就是倍增，但是倍增这里的数组因为太大不可以预处理出来，我们需要想别的方法。 我们想到，暴力之所以慢，是因为这个原因：如这个状态（1，2，1000000），这种状态下，暴力会跑很久。很明显这种情况下可以一部跳过嘛，就是令 k=（r−1）/l ，然后 x+=l∗k,y+=l∗k ，从右边跳向左边的也是同理，这样我们就实现了一步转化，那么就优化成了log级别。 然后我们在求lca时，我们二分lca的深度，在跑一遍lca，就可以了。时间复杂度： O(log2n) 。

---

代码

#include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=1e9; struct cy{ int x,y,z; void getin(){ scanf("%d%d%d",&x,&y,&z); if (x>y) swap(x,y); if (x>z) swap(x,z); if (y>z) swap(y,z); } }b,e,p,q; int deep,k,ans; cy lca(cy t,int fdeep) { bool bz=true; int maxx=fdeep; for(deep=0;bz;deep+=k) { int l=t.y-t.x,r=t.z-t.y; if (l==r) return t; k=maxx; if (l<r){ k=min((r-1)/l,k); t.x+=l*k; t.y+=l*k; } else { k=min((l-1)/r,k); t.y-=k*r; t.z-=k*r; } maxx-=k; if (maxx<=0) bz=false; } return t; } bool check(cy a,cy b) { if (a.x==b.x && a.y==b.y && a.z==b.z) return true; else return false; } int main() { b.getin(); e.getin(); p=lca(b,maxn); int deepb=deep; q=lca(e,maxn); int deepe=deep; if (!check(p,q)) printf("NO"); else { printf("YES\n"); if (deepb<deepe) { swap(deepb,deepe); swap(b,e); } b=lca(b,deepb-deepe); ans+=deepb-deepe; if (check(b,e)) printf("%d",ans); else { deepb=deepe; int l=1,r=deepb; while (l<r){ int mid=(l+r)>>1; p=lca(b,mid); q=lca(e,mid); if (check(p,q)) r=mid; else l=mid+1; } ans+=r*2; printf("%d",ans); } } }