UVa12558_Egyptian Fractions (HARD version)

题目

题目

bala

稳稳地超时了O_O…Time limit,Time limit exceed 。

在uDebug上找了组数据，嗯确认过眼神，算法效率太低，但是没出错哈哈，还是挺欣慰的~

（其实，就运行了173.2 s 的…哪里效率低了，比你手算快多了）//手动狗头//

果然还是得ctrl+v一个狗头，才有那味儿

Time limit

//对于整个问题，一头雾水 
// 方向________________>>>>>>>>> 
//那就先弄懂小规模问题： a / b 分解 成三个埃及分数。列出所有情况。 
//2020/4/18    
//9:00 -  21:30
//@reasonbao 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

typedef long long int ll;

ll  ans[100];
ll  ans_best[100];
bool g_is_ok = false;
int g_restrict[10];
int g_k = 0;

//比较 y1 / x1  与  y2 / x2 的大小 
int CompareFraction(ll y1, ll x1, ll y2, ll x2) {
	ll fraction_front = y1 * x2, fraction_next = y2 * x1;	//通分交叉相乘，乘积可能非常大
	if (fraction_front == fraction_next) return 0;
	else if (fraction_front > fraction_next) return 1;
	else return 2;
}

////估价函数
//bool Assess(ll fenzi, ll fenmu, ll layer, ll biggest) {
//	if (CompareFraction(fenzi, fenmu, layer, biggest) == 2)
//		return true;		//"假想最大值",至少应该要比剩余的分数大或等于 
//	if (CompareFraction(fenzi, fenmu, layer, biggest) == 0 && layer == 1) 
//		return true;
//	return false;		    //若剩余层数 * 最大埃及分数  < 剩余的分数，" 剪枝 " 
//} 

//最大公约数，用于约分 
ll Gcd(ll a, ll b) {
	if (b == 0) return a;
	else return Gcd(b, a % b); 
}


//约分
void Reduce(ll &fenzi, ll &fenmu) {
	if (fenzi == 0) {
		fenzi = 0;
		fenmu = 1;
	}
	else {
		ll gcd = Gcd(fenzi, fenmu);
		fenzi /= gcd;
		fenmu /= gcd;
	}
} 

void Add(ll &y1, ll &x1, ll y2, ll x2) {
	ll fraction_front = y1 * x2, fraction_next = y2 * x1;	//通分交叉相乘，乘积可能非常大
	x1 = x1 * x2;
	y1 = fraction_front + fraction_next;
	Reduce(y1, x1);
}

//估价函数 2.0
bool Assess(ll fenzi, ll fenmu, ll layer, ll biggest) {
	if (CompareFraction(fenzi, fenmu, layer, biggest) == 0 && layer == 1) 
		return true;	 
	
	long long int max_fenzi = 0, max_fenmu = 1;	
	ll from = biggest;
	for (int i = 0; i < layer; i++) {
		Add(max_fenzi, max_fenmu, 1, from ++ );
	}
//	cout << max_fenzi << " " << max_fenmu;
	if (CompareFraction(fenzi, fenmu, max_fenzi, max_fenmu) == 2 ||  CompareFraction(fenzi, fenmu, max_fenzi, max_fenmu) == 0)
		return true;		//"最大值",至少应该要比剩余的分数大或等于
		
	return false;		    //若剩余层数实际最大埃及分数之和  < 剩余的分数，" 剪枝 "，没必要继续深度或者广度 
} 
 
void Sub(ll &y1, ll &x1, ll y2, ll x2) {
	ll fraction_front = y1 * x2, fraction_next = y2 * x1;	//通分交叉相乘，乘积可能非常大
	x1 = x1 * x2;
	y1 = fraction_front - fraction_next;
	Reduce(y1, x1);
}
 
//比较相同深度情况下的更优解
void Better(ll pos) {
	if ( !ans_best[pos] || ans[pos] <= ans_best[pos]) {
		for (int i = 0; i <= pos; i ++ ) 
			ans_best[i] = ans[i];
	}
}

void Dfs(ll remain_fenzi, ll remain_fenmu, ll from, ll cur, ll maxd) {
	
	if (cur == maxd ) {
//		cout << " cur = " << cur << endl; 
		if ( ! remain_fenzi) {
//			cout << "数组情况：————";
//			for (int m = 0; m < maxd; m ++ ) cout << ans[m] << " "; cout << endl << endl;
			Better(maxd - 1);
			g_is_ok = true;
		}
		return;
	}
	
	for (ll i = from; ; i ++ ) {	//向第cur层填入埃及分数,。 注：from初始化为1，即 1 / 1 
	
		if (! Assess(remain_fenzi, remain_fenmu, maxd - cur, i)) return;	//不可能事件，返回上一层 (上一层尝试其他数),不知道这算不算 ""剪枝"" 
		
		
		while (CompareFraction(remain_fenzi, remain_fenmu, 1, i) == 2) {	//等于2 表示 1/i > 剩下的分数 
			i ++ ;	//直到找到该层可填的数 (条件：1 / i 比剩余分数 小 或者 等)
//			cout << "i = " << i << endl; 
//			cout << "cur = " << cur << endl; 
		}
		//判断是否在限制数组中 ,是则使用下一个 i 
		bool is_restrict = false;
		for (int mmm = 0; mmm < g_k; mmm++) {
			if (g_restrict[mmm] == i) {
				is_restrict = true;
				break;
			}
		}
		if (is_restrict) continue;
		
		//判断是佛剩余层数还不是1，直接给减没了
		if (CompareFraction(remain_fenzi, remain_fenmu, 1, i) == 0 && maxd - cur != 1 ) continue; 
		
		ans[cur] = i;
//		cout << "减之前："; cout << remain_fenzi << "/" << remain_fenmu << " - " << 1 << "/" << i << endl;
		
		ll remain_fenzi_tmp = remain_fenzi;
		ll remain_fenmu_tmp = remain_fenmu;
		
		Sub(remain_fenzi_tmp, remain_fenmu_tmp, 1, i); 
		
//		cout << "减之后："; cout << remain_fenzi_tmp << "/" << remain_fenmu_tmp << endl;
		
		Dfs(remain_fenzi_tmp, remain_fenmu_tmp, i + 1, cur + 1, maxd);
	}
} 

void OutputResult(ll a, ll b, ll maxd) {
//	printf("%lld/%lld=", a, b);
	cout << a << "/" << b << "=";
	for (int i = 0; i < maxd; i ++ ) {
		if (i >= 1) cout << "+";
		cout << 1 << "/" << ans_best[i];
//		printf("%lld/%lld", 1, ans_best[i]);
	}
	cout << endl;
}

int main() {
	
//	Assess(3,4,3,4); 
//	freopen("in11.txt", "r", stdin); 	//在stdio里 
//	freopen("out11.txt", "w", stdout); 
	ll a,b;
	int kase = 1;
	int num;
	cin >> num;
	while (num -- ) {
//	while (cin >> a >> b >> g_k) {
		cin >> a >> b >> g_k;
		memset(g_restrict, 0, sizeof(g_restrict));
		for (int i = 0; i < g_k; i++) {
			cin >> g_restrict[i];
		}
		
		printf("Case %d: ", kase ++ );
		for (ll maxd = 1; ; maxd ++ ) {	//对DFS的深度进行枚举，也就是限制深度（实现题目中：加数少的情况比多的好） 
			memset(ans, 0, sizeof(ans));
			memset(ans_best, 0, sizeof(ans_best));
			Dfs(a, b, 1, 0, maxd);

			if (g_is_ok)	{
				OutputResult(a, b, maxd);
				break;
			}
		}
		g_is_ok = false;	//记得重置 
	}
	
	
	return 0;
}