首页 > ACM题库 > HDU-杭电 > Hdu 1475 Keeps Going and Going and …[解题报告] C++
2013
12-11

Hdu 1475 Keeps Going and Going and …[解题报告] C++

Keeps Going and Going and …

问题描述 :

Lazy functional languages like Haskell and Miranda support features that are not found in other programming languages, including infinite lists. Consider the following simple (and useful) recursive declaration:
letrec
count n = cons n (count (n+1))
in
count 0The function cons constructs lists, so the above declaration creates the following structure:

cons 0 (count 1)
= cons 0 (cons 1 (count 2))
= cons 0 (cons 1 (cons 2 …))
= [0,1,2,...]

Lazy languages can do this because they only evaluate expressions that are actually used. If a program creates an infinite list and only looks at items 2 and 3 in it, the values in positions 0 and 1 are never evaluated and the list structure is only evaluated so far as the fourth node.

It is also possible to use more than one function to build an infinite list. Here is a declaration that creates the list ["even","odd","even",...]:

letrec
even = cons “even” odd
odd = cons “odd” even
in
even

There are also functions that manipulate infinite lists. The functions take and drop can be used to remove elements from the start of the list, returning the (removed) front elements or the remainder of the list, respectively. Another useful function is zip, which combines two lists like the slider on a zipper combines the teeth. For example,

zip (count 0) (count 10) = [0,10,1,11,2,12,...]

Your task is to implement a subset of this functionality.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

输入:

The first line of input consists of two positive integers, n and m. n is the number of declarations to follow and m is the number of test cases.Each declaration takes the form name = expr. There are two forms for expr : zip name1 name2 and x0 x1 … xi name3. In the first case, name is the result of zipping name1 and name2 together. The other case defines the first i + 1 non-negative integers in the list name (where i is at least 0) and name3 is the name of the list that continues it (mandatory–all lists will be infinite).

The test cases take the form name s e, where s and e are non-negative integers, s <= e and e – s < 250.

No line of input will be longer than 80 characters. Names consist of a single capital letter.

输出:

For each test case, print the integers in positions s to e of the list name. List elements are numbered starting with 0.

样例输入:

5 3
S = 4 3 2 1 A
O = 1 O
E = 0 E
A = zip E O
Z = zip Z S
A 43455436 43455438
S 2 5
Z 1 10

样例输出:

0 1 0
2 1 0 1
4 4 3 4 2 3 1 4 0 2


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

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的