提高培优D15 T1

常规
1

LCA建模+二分答案。考虑转移的情况。发现前两种会导致范围不断扩大，而后两种最终会收缩到$Y - X = Z - Y$。发现如果可以转移最终都会收缩到同一状态。可以将转移抽象成为一种树，每一个点就是$\left (X, Y, Z \right) 每一次的操作3，4便是向上跳跃，而1，2为其逆操作。可以检验操作后的终态是一样的来判断是否可以转移。而转移次数则是 {2}Dep_{lca(u,v)} -Dep_u - Dep_v$。考虑求解LCA，设$d_1 = Y - X,d_2 = Z - Y$ 已$d_1 < d_2$为例，发现每次跳跃$d_2$缩短的距离是一样的。跳跃次数就是$\frac{(d_2 - 1)}{d_1}$那么对于y, z减去此跳跃值便可。而$d_1 > d_2$也是同理，只不过是由减法变成为加法。所以只需要先判断是否可以相互转移，并且维护跳跃的根结点的步数，对此求出深度再求出LCA最后计算贡献就可以。

注意：一次性跳跃的次数是总共可以跳跃的次数与一次性可以跳跃的最大值二者的最小值

#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define lfor(i, x, y) for (int i = (x); i <= (y); ++ i)
#define llfor(i, x, y) for (int i = (x); i < (y); ++ i)
#define rfor(i, x, y) for (int i = (x); i >= (y); -- i)
#define rlfor(i, x, y) for (int i = (x); i > (y); -- i)
#define For(i, p) for(int i = G.head[p]; ~i; i = G.nxt[i])
template <typename T>inline void read(T &x){bool f=0;x=0;char ch=getchar();while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-')ch=getchar(),f=1;while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=f?-x:x;}
template <typename T1,typename... T2>inline void read(T1 &x,T2& ...y){read(x);read(y...);}
using namespace std;

/*======================Header Template======================*/
typedef long long ll;
typedef long double ld;
typedef double db;
int tx, ty, tz;
bool f;

/*======================Define Area======================*/

int jump_root(int x, int y, int z) {
	int d1 = y - x, d2 = z - y;
	int ret = 0;
	while (d1 != d2) {
		if (d1 > d2) {ret += (d1 - 1) / d2; y -= (d1 - 1) / d2 * d2; z -= (d1 - 1) / d2 * d2;}
		else {ret += (d2 - 1) / d1; y += (d2 - 1) / d1 * d1; x += (d2 - 1) / d1 * d1;}
		d1 = y - x, d2 = z - y;
		//cout << "x:" << x << " y:" << y << " z:" << z << endl;
		//cout << "d1:" << d1 << " d2:" << d2 << endl;
	}
	if (!tx && !ty && !tz) tx = x, ty = y, tz = z;
	else if (tx == x && ty == y && tz == z) f = true;
	return ret;
}

bool check(int mid, int X, int Y, int Z, int x, int y, int z){
	int tmp = mid, d1 = Y - X, d2 = Z - Y;
	//cout << "1:" << endl;
	while (tmp > 0) {
		//cout << "d1:" << d1 << " d2:" << d2 << "tmp:" << tmp << endl;
		//cout << "X:" << X << " Y:" << Y << " Z:" << Z << endl;
		if (d1 == d2) break;
		if (d1 > d2) {int d3 = min((d1 - 1) / d2, tmp); tmp -= d3; Y -= d3 * d2; Z -= d3 * d2;}
		else {int d3 = min((d2 - 1) / d1, tmp); tmp -= d3; Y += d3 * d1; X += d3 * d1;}
		d1 = Y - X, d2 = Z - Y;
	}
	///cout << "2" << endl;
	tmp = mid, d1 = y - x, d2 = z - y;
	while (tmp > 0) {
		//cout << "d1:" << d1 << " d2:" << d2 << " tmp:" << tmp << endl;
		//cout << "x:" << x << " y:" << y << " z:" << z << endl;
		if (d1 == d2) break;
		if (d1 > d2) {int d3 = min((d1 - 1) / d2, tmp); tmp -= d3; y -= d3 * d2; z -= d3 * d2;}
		else {int d3 = min((d2 - 1) / d1, tmp); tmp -= d3; y += d3 * d1; x += d3 * d1;}
		d1 = y - x, d2 = z - y;
	}
	return (x == X) && (y == Y) && (z == Z);
}

int main() {
	ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int n[4], m[4]; cin >> n[0] >> n[1] >> n[2] >> m[0] >> m[1] >> m[2];
    sort(n, n + 3), sort(m, m + 3);
    int a = n[0], b = n[1], c = n[2], x = m[0], y = m[1], z = m[2];
    //cout << a << " " << b << " " << c << endl;
    //cout << x << " " << y << " " << z << endl;
    int deps = jump_root(a, b, c), dept = jump_root(x, y, z);
    if (dept > deps) swap(a, x), swap(b, y), swap(c, z), swap(dept, deps);
    //cout << "OK" << endl;
    //cout << deps << " " << dept << endl;
    int trans = deps - dept, d1 = b - a, d2 = c - b;
    int X = a, Y = b, Z = c;
    if (!f) {cout << "NO" << endl; return 0;}
    //cout << X << " " << Y << " " << Z << endl;
    while (trans > 0) {//TODO 也有min的操作
    	if (d1 == d2) break;
    	if (d1 > d2) {int d3 = min((d1 - 1) / d2, trans); trans -= d3; Y -= d3 * d2; Z -= d3 * d2;}
		else {int d3 = min((d2 - 1) / d1, trans); trans -= d3; Y += d3 * d1; X += d3 * d1;}
		d1 = Y - X, d2 = Z - Y;
		//cout << X << " " << Y << " " << Z << endl;
    }
    //cout << "CHECK" << endl;
    //cout << X << " " << Y << " " << Z << endl;
    //cout << x << " " << y << " " << z << endl;
    //cout << jump_root(X, Y, Z) << " " << jump_root(x, y, z) << endl;
    int l = 0, r = 2e9;
    while (l < r) {
    	int mid = (l + r) >> 1;
    	//cout << "---TODO:" << l << " " << r << " " << mid << endl;
    	if (check(mid, X, Y, Z, x, y, z)) r = mid;
    	else l = mid + 1;
    }
    cout << "YES" << endl;
    cout << 2 * l + deps - dept << endl;
	return 0;
}
/*
0 1 3
1 2 3
1 2000000000 1000000000

*/
1 个赞