首页 > ACM题库 > HDU-杭电 > HDU 2965-Business Cards-组合数学-[解题报告]HOJ
2014
02-24

HDU 2965-Business Cards-组合数学-[解题报告]HOJ

Business Cards

问题描述 :

Running a paper shop is not an easy job, especially with harsh customers. Today they brought their own rectangular sheets of paper, asking you to cut it into rectangular business cards of specific size.

Moreover, they require that all the paper (which may not be cheap, but is definitely not that expensive!) has to be used, i.e. no tiny bit may be left over.
Moreover, the brilliant idea of cutting the sheet into very small pieces, and then gluing them together in desired sheets was laughed at.

An example of a 9 *6 paper sheet divided into 2 * 3 cards is given below.

输入:

The input contains several test cases. The first line contains the number of test cases t (t <= 10^5). Then t test cases follow. Each of them consists of one line containing four integers a, b, c, d (1 <=a, b, c, d <= 10^9).

Numbers a and b are dimensions of each business card; c and d are dimensions of the paper sheet.

输出:

The input contains several test cases. The first line contains the number of test cases t (t <= 10^5). Then t test cases follow. Each of them consists of one line containing four integers a, b, c, d (1 <=a, b, c, d <= 10^9).

Numbers a and b are dimensions of each business card; c and d are dimensions of the paper sheet.

样例输入:

4
2 3 9 6
2 3 8 6
2 3 6 8
2 3 5 7

样例输出:

YES
YES
YES
NO

类似于骨牌问题。我的做法就是首先看能不能横着排满,然后看能不能竖着排满,都不行的话就考虑一些横着排,一些竖着排,看能不能满足要求,最后也就转化为求ax+by=n有没有非负解的问题。可是我用扩展欧几里得打了,超时,无奈只能纯枚举了,枚举放1个、2个、3个…直到放不下为止。这说明测试数据很操蛋。

/*
 * hdu2965/win.cpp
 * Created on: 2012-11-4
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
typedef long long LL;
int gcd(int a, int b) {
    int r;
    while(b) {
        r = a % b;
        a = b, b = r;
    }
    return a;
}
inline bool judge2(int a, int b, int z) {
    int x = 1;
    while(a * x < z) {
        if((z - a * x) % b == 0) {
            return true;
        }
        x++;
    }
    return false;
}

inline bool judge(int x, int y, int n, int m) {
    int t = gcd(x, y);
    if(n % t != 0 || m % t != 0) {
        return false;
    }
    x /= t, y /= t, m /= t, n /= t;
    if(n % x == 0 && m % y == 0) {
        return true;
    }
    if(n % y == 0 && m % x == 0) {
        return true;
    }
    if(n % x == 0 && n % y == 0 && judge2(x, y, m)) {
        return true;
    }
    if(m % x == 0 && m % y == 0 && judge2(x, y, n)) {
        return true;
    }
    return false;
}
int get_int() {
    int res = 0, ch;
    while (!((ch = getchar()) >= '0' && ch <= '9')) {
        if (ch == EOF)
            return 1 << 30;
    }
    res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + (ch - '0');
    return res;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T, x, y, n, m;
    T = get_int();
    while(T--) {
        x = get_int();
        y = get_int();
        n = get_int();
        m = get_int();
        bool ret = judge(x, y, n, m);
        puts(ret ? "YES" : "NO");
    }
    return 0;
}

解题参考:http://www.cnblogs.com/moonbay/archive/2012/11/06/2757790.html


  1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮