uva 618 - Doing Windows(暴力+数学)

标签：style   blog   class   code   tar   ext   

题目链接：uva 618 - Doing Windows

题目大意：给出电脑桌面的大小W和H，现在在桌面上有4个窗口，给出窗口的初始大小，问说能不能通过调整各个窗口的大小（长宽比例不能变）使得4个屏幕刚好占满整个屏幕，并且互相不覆盖。

解题思路：其实可以直接暴力出所有情况，不过细节比较多，而且要考虑所有的细节。

我的做法的是先将4个窗口缩小至最小的状态，然后枚举左下角的窗口，

有四种可能

蓝色部分为另外枚举的窗口，3，4种情况要分别保证说长、宽相等，然后S部分就是子问题。

所以用一个二进制数来表示窗口被使用的情况，然后如果只剩一块，看随后一块和剩下的矩形长宽是否成比例。

#include 
#include 

const int N = 5;
typedef long long ll;

inline ll gcd (ll a, ll b) {
	return b == 0 ? a : gcd(b, a%b);
}

inline int bitCount(int x) {
	return x == 0 ? 0 : bitCount(x/2) + (x&1);
}

struct state {
	ll r, c;
	state (ll r = 0, ll c = 0) {
		this->r = r;
		this->c = c;
	}
	void get() {
		scanf("%lld%lld", &r, &c);
		ll d = gcd(r, c);
		r /= d;
		c /= d;
	}
}w[N];

bool solve (ll R, ll C, int s);

inline bool cmp (state a, state b) {
	return a.r * b.c == b.r * a.c;
}

void cat (state u, state v, state& a, state& b, int s) {
	ll p, q;
	if (s == 0) {
		ll d = gcd(u.r, v.r);
		p = v.r / d;
		q = u.r / d;
	} else {
		ll d = gcd(u.c, v.c);
		p = v.c / d;
		q = u.c / d;
	}
	a.r = u.r * p;
	a.c = u.c * p;
	b.r = v.r * q;
	b.c = v.c * q;
}

bool judge(ll R, ll C, state v, int s, int sign) {

	if (sign == 0) {

		if (R % v.r)
			return false;

		ll k = R / v.r;
		C -= v.c * k;
		if (C  2 && judgeTow(R, C, w[i], s-(1




uva 618 - Doing Windows(暴力+数学),搜素材,soscw.com
uva 618 - Doing Windows(暴力+数学)
标签：style   blog   class   code   tar   ext   
原文地址：http://blog.csdn.net/keshuai19940722/article/details/24839099