程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3830 Checkers

HDU 3830 Checkers

編輯：C++入門知識

HDU 3830 Checkers

題意：

有三個棋子可以隔一個棋子跳不能隔兩個跳問狀態u到狀態v最少跳幾步

思路：

對於一個狀態三個棋子的位置可以設為 x y z （小到大）

只有當y-x=z-y的時候跳的方法為兩種即 y跳過x 或 y跳過z

在上式等式不成立時短的一邊可以跳許多次直到大小關系改變

那麼這樣就形成了二叉樹的結構我們將y向左右跳的狀態分別作為原狀態的兒子將兩邊其中一個向中間跳的狀態作為原狀態的父親

那麼這時u和v的可達性就變成了他們是不是同一個根於是我們可以從u和v跳到頭判斷一下

如果能跳要跳幾次呢？？這時利用LCA 方法與倍增法相同即 u和v先爬到同一高度再同時爬

爬的方法和剛才的狀態向根移動相同由於沒有倍增打表因此同一深度後我們要用二分法確定爬的高度

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef unsigned long long LL;
#define M 1100
#define N 16

struct state {
	int x[3];
	void Sort() {
		sort(x, x + 3);
	}
	int Root() {
		int floor = 0;
		int a1 = x[1] - x[0], a2 = x[2] - x[1];
		while (a1 != a2) {
			if (a1 > a2) {
				int d = (a1 - 1) / a2;
				floor += d;
				x[2] -= d * a2;
				x[1] -= d * a2;
			} else {
				int d = (a2 - 1) / a1;
				floor += d;
				x[0] += d * a1;
				x[1] += d * a1;
			}
			Sort();
			a1 = x[1] - x[0], a2 = x[2] - x[1];
		}
		return floor;
	}
	bool operator==(const state ff) const {
		return (x[0] == ff.x[0]) && (x[1] == ff.x[1]) && (x[2] == ff.x[2]);
	}
	void GoUp(int floor) {
		while (floor) {
			int a1 = x[1] - x[0], a2 = x[2] - x[1];
			if (a1 > a2) {
				int d = (a1 - 1) / a2;
				if (d > floor)
					d = floor;
				floor -= d;
				x[2] -= d * a2;
				x[1] -= d * a2;
			} else {
				int d = (a2 - 1) / a1;
				if (d > floor)
					d = floor;
				floor -= d;
				x[0] += d * a1;
				x[1] += d * a1;
			}
			Sort();
		}
	}
} u, v, fau, fav;

int main() {
	int fu, fv, ans;
	while (~scanf("%d%d%d%d%d%d", &u.x[0], &u.x[1], &u.x[2], &v.x[0], &v.x[1],
			&v.x[2])) {
		u.Sort();
		v.Sort();
		fau = u;
		fav = v;
		fu = fau.Root();
		fv = fav.Root();
		if (fau == fav) {
			puts("YES");
			if (fu > fv) {
				ans = fu - fv;
				u.GoUp(ans);
			} else if (fv > fu) {
				ans = fv - fu;
				v.GoUp(ans);
			} else
				ans = 0;
			int l = 0, r = min(fu, fv), mid, tmp;
			while (l <= r) {
				mid = (l + r) >> 1;
				fau = u;
				fav = v;
				fau.GoUp(mid);
				fav.GoUp(mid);
				if (fau == fav) {
					r = mid - 1;
					tmp = mid;
				} else
					l = mid + 1;
			}
			printf("%d\n", ans + (tmp << 1));
		} else
			puts("NO");
	}
	return 0;
}