首页 > ACM题库 > HDU-杭电 > HDU 3083-The Mystery of Triangle -计算几何-[解题报告]HOJ
2014
03-01

HDU 3083-The Mystery of Triangle -计算几何-[解题报告]HOJ

The Mystery of Triangle

问题描述 :

There’re some unresolved problems of triangle so far. For example, whether there’s a three middle integer Helen triangle? It is unable to prove its existence until now; they have not found such a triangle. But I’ m sure you can solve this problem. Now, there is an equilateral triangle(等边三角形),each edge is divided into two equal parts. Such as the picture
Simplify The Circuit

and if each edge is divided into three equal parts,
the triangle becomes
Simplify The Circuit

,now you task is to count the number of triangles, diamonds(菱形), and parallelograms(平行四边形).

输入:

Each line will contain a integer n (1 < n < 2^31 – 1). It means each edge of triangle is divided into n equal parts. Process to the end of input.

输出:

Each line will contain a integer n (1 < n < 2^31 – 1). It means each edge of triangle is divided into n equal parts. Process to the end of input.

样例输入:

2
3

样例输出:

Triangle: 5
Diamond: 3
Parallelogram: 3
Triangle: 13
Diamond: 9
Parallelogram: 15

不知道大牛们有没有简洁的方法,反正我是一步一步慢慢推公式做出来的。居然推了一下午啊,囧。。。真是老了不中用了。。。

其实推完后再整理整理,发现还是挺简单的,其实就是几个数列而已

数列①1, 2, 3, 4, 5, 6, 7, 8, 。。。

数列②1, 3, 6, 10, 15, 21, 28, 36。。。

数列③1, 4, 10, 20, 35, 56, 。。。

数列④1, 5, 15, 35, 70

数列⑤3, 10, 21, 36,。。。

数列⑥1, 6, 15, 28, 。。。

我主要是把问题进行分解,三角形个数=正放三角形个数+倒放三角形个数

正放三角形个数=边长为1的正放三角形个数+边长为2的正放三角形个数+。。。

而边长为k的正放三角形个数为合法的每一层的边长为k的正放三解形的个数

而每一层的边长为k的正放三解形的个数正好是数列①,所以正放三角形个数正好是数列③

倒立的三角形个数稍难算,得分奇偶。当n为奇数时,是数列⑤的前n项和数列;当n为偶数时是数列⑥的前n项和数列,当然,⑤和⑥分别是数列②的偶数项和奇数项构成的子数列。

菱形个数最好算,就是倒立三角形个数*3

算平行四边形个数的时候,我是先只考虑两条边平行大三角形底边,另两边平行于大三角形左边的平行四边行,显然,总的平形四边形数为这个数的3倍

而刚才说的这种平行四边形的个数正好是数列④

把这几个公式整理成通项的形式就可以计算了,最后再考虑一些特殊情况,还有就是计算的时候时时取模防止溢出,就OK了,我是1Y的,哈哈~~~

/*
 * hdu3083/win.cpp
 * Created on: 2012-7-15
 * 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;

const int MOD = 20091226;
typedef long long LL;

inline int getS(LL n) {
    LL mod = MOD * 6;
    LL ret = (n % mod) * ((n + 1) % mod);
    ret %= mod;
    ret *= (n + 2) % mod;
    ret %= mod;
    ret /= 6;
    return (int)ret;
}

inline int getX(LL n) {
    if(n <= 1) {
        return 0;
    }
    int mod = MOD * 24;
    LL ret = (n + 1) % mod;
    if(n % 2 == 1) {
        ret = (((2 * ret  - 3) * ret) % mod - 2) * ret;
    }else {
        ret = (n % mod) * ((n + 2) % mod);
        ret %= mod;
        ret *= (2 * n - 1) % mod;
    }
    ret %= mod;
    ret /= 24;
    return ret;
}

inline int getP(LL n) {
    if(n < 1) {
        return 0;
    }
    int mod = MOD * 8;
    LL ret = n % mod;
    ret = ((((ret * (ret + 1))% mod) * (ret + 2))% mod) * (ret + 3);
    ret %= mod;
    ret /= 8;
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int n;
    LL t, d, p, s, x;
    while(scanf("%d", &n) == 1) {
        s = getS(n);
        x = getX(n);
        t = s + x;
        d = 3 * x;
        p = getP(n - 1);
        printf("Triangle: %d\n", t % MOD);
        printf("Diamond: %d\n", d % MOD);
        printf("Parallelogram: %d\n", p % MOD);
    }
    return 0;
}

参考:http://www.cnblogs.com/moonbay/archive/2012/07/15/2592736.html


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?