首页 > ACM题库 > HDU-杭电 > HDU 3556-Continued Fraction[解题报告]HOJ
2014
11-05

HDU 3556-Continued Fraction[解题报告]HOJ

Continued Fraction

问题描述 :

Dumbear loves numbers very much.
One day Dumbear found that each number can be expressed as a continued fraction. See below.
Bomb
Formally, we say a number k can be expressed as a continued faction if
Bomb
where a0, a1, …, an are positive integers except that a0 maybe be 0 and an cannot be 1.
Dumbear also found a sequence which looks like the Farey sequence. Initially the sequenceBomband if we insert an elementBombbetween all the two adjacent elementBomb,Bombin Di, then we get a sequence Di+1. So you can seeBombandBombAssume initially you are on the elementBombin D0, and if now you are on the element k in Di, then if you go left(‘L’)(or right(‘R’)) you will be on the left(or right) element of k in Di+1. So a sequence composed of ‘L’ and ‘R’ denotes a number. Such as ‘RL’ denotes the number Bomb

Now give you a sequence composed of ‘L’ and ‘R’, you should print the continued fraction form of the number. You should use ‘-‘ to show the vinculum(the horizontal line), you should print one space both in front and back of ‘+’, and all parts up or down the vinculum should be right aligned. You should not print unnecessary space, ‘-‘ or other character. See details in sample.

输入:

There are several test cases in the input.
For each test case, there is a single line contains only a sequence composed of ‘L’ and ‘R’. The length of the sequence will not exceed 10000.
The input terminates by end of file marker.

输出:

There are several test cases in the input.
For each test case, there is a single line contains only a sequence composed of ‘L’ and ‘R’. The length of the sequence will not exceed 10000.
The input terminates by end of file marker.

样例输入:

LR
RL

样例输出:

        1 
0 + ----- 
        1
    1 + -
        2
    1
1 + -
    2

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long ll;
const int MAX = 100000;
const int LEN = 100000;
char buffer[MAX];
ll a[MAX];
ll space[LEN],vin[LEN],bit[LEN];

static ll BIT[18] = {-1,9LL,99LL,999LL,9999LL,99999LL,999999LL,9999999LL,99999999LL,999999999LL,9999999999LL,99999999999LL,999999999999LL,
			9999999999999LL,99999999999999LL,999999999999999LL};
inline int getBit(const ll& x) {
        for (int i = 0; i < 18; ++i) {
                if (x <= BIT[i]) return i;
        }
        return 18;
}

int main() {
	//freopen("C.out", "w", stdout);
	while (~scanf(" %s", buffer)) {
		int len = strlen(buffer);
		int deep = 0, cur;
                if (buffer[0] == 'L') a[deep++] = 0;
		cur = 1;
		for (int i = 1; i < len; ++i) {
                        if (buffer[i] == buffer[i-1]) {
                                ++cur;
                        } else {
                                a[deep++] = cur;
                                cur = 1;
                        }
		}
                a[deep] = ++cur;
                if (deep == 0) {
			printf("%I64d\n", a[0]);
			continue;
                }
                for (int i = 0; i <= deep; ++i) {
                        bit[i] = getBit(a[i]);
                }
                vin[deep-1] = bit[deep];
                for (int i = deep-2; i >= 0; --i) vin[i] = vin[i+1] + 3 + bit[i+1];
		int LENGTH = vin[0] + 3 + bit[0];
                space[0] = 0;
                for (int i = 1; i <= deep; ++i) {
                        space[i] = space[i-1] + bit[i-1] + 3;
                }

		//printf("LENGTH = %d\n", LENGTH);
                for (int i = 0; i < deep; ++i) {
                        for (int j = 1; j < LENGTH; ++j) putchar(' ');
                        putchar('1');
                        putchar('\n');
                        for (int j = 0; j < space[i]; ++j) putchar(' ');
                        printf("%I64d + ", a[i]);
                        for (int j = 0; j < vin[i]; ++j) putchar('-');
                        putchar('\n');
                }
                for (int j = 0; j < LENGTH-bit[deep]; ++j) putchar(' ');
                printf("%I64d\n", a[deep]);
	}
	return 0;
}
/*
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLLLLLLLLLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLLLLLLLLLLLLLLLLLLLLLLLLLLRLRLRLLRLRLRLRLRLRRRRRRRRRRR
*/

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

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;