首页 > ACM题库 > HDU-杭电 > hdu 1952 Gladiators[解题报告]C++
2013
12-26

hdu 1952 Gladiators[解题报告]C++

Gladiators

问题描述 :

In the TV game show Gladiators, the final competition is to run through a steeplechase course. To get some variation, the producer has decided to change the course each week. The course is always built out of m obstacles, all of different heights, placed along a straight line. An obstacle consists of two initially connected platforms which may be separated. Between the two platforms of an obstacle, other higher obstacles may be put. Also, obstacles may be put after one another.

Figure 1. To the left: An obstacle seen from the side. To the right: A steeplechase course consisting of 5 obstacles. The contestants run from left to right.

The producer thinks it is most desirable that the results from different weeks may be compared to each other. Therefore, he wants to build courses of similar degree of difficulty.
A proposed measure of difficulty is the number of platforms that are higher than their immediately preceeding platform along the course. Moreover, the leftmost (first) platform of the course always give rise to one point since it is located above the floor. E.g. the course to the right in figure 1 has four points of difficulty.
Your mission is to find out how many ways there are to build a course of a given point of difficulty,from a given number of obstacles.

输入:

On the first line of input is a single positive integer n, telling the number of test scenarios to follow.
Each test scenario consists of one line containing two non negative integers m and k, where m <= 50 is the number of obstacles, and k is the point of difficulty asked for.

输出:

On the first line of input is a single positive integer n, telling the number of test scenarios to follow.
Each test scenario consists of one line containing two non negative integers m and k, where m <= 50 is the number of obstacles, and k is the point of difficulty asked for.

样例输入:

6 0
1 0
1 1
2 1
2 2
3 1
3 2

样例输出:

0
1
1
2
1
8

/*This Code is Submitted by billforum for Problem 1952 at 2012-06-08 15:39:09*/
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <exception>
#include <cstring>
#include <stdlib.h>
using namespace std;
const int Len=1000000;
int next[Len+5];
void getNext(int next[],char str[])
{
        int len=strlen(str);
        int i=0,j=-1;
        while(i<len)
        {
                if((j==-1)||(str[i]==str[j]))
                {
                        j++;
                        i++;
                        next[i]=j;
                }
                else j=next[j];
        }
        
        
        return;
}
void print(int next[],int len)
{
        for(int i=0;i<len;i++)
                printf("%d ",next[i]);
}
int cmp(char s1[],char s2[])
{
        int i=0,j=0;//i->s1,j->s2
        int len1=strlen(s1),len2=strlen(s2);
        int times=0;
        while(i<len1)
        {
                if((j==-1)||(s1[i]==s2[j]))
                {
                        i++;
                        j++;
                        if(j>=len2) 
                        {
                                j=0;
                                times++;
                        }
                }
                else j=next[j];
        }
        return times;
}
int main(int argc, char **argv)
{
        
        char str1[Len+5];
        memset(next,0,sizeof(next));
        next[0]=-1;
        while(scanf("%s",str1)==1)
        {
                if(strcmp(str1,".")==0) break;
                int len1=strlen(str1);
                
                str1[len1]='.';
                str1[len1+1]='\0';
            
                getNext(next,str1);
                 len1=strlen(str1);
                //print(next,len1);
                //cout<<endl;
                if((len1-1)%(len1-1-next[len1-1])==0)
                        printf("%d\n",(len1-1)/(len1-1-next[len1-1]));
                else printf("1\n");
                
        }
        return 0;
}

  

解题转自:http://www.cnblogs.com/wuzhibin/archive/2012/06/08/2541870.html


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。