首页 > ACM题库 > HDU-杭电 > hdu 2497 Pick up sticks-数学相关-[解题报告]C++
2014
02-09

hdu 2497 Pick up sticks-数学相关-[解题报告]C++

Pick up sticks

问题描述 :



Pick up sticks is a fascinating game. A collection of coloured sticks are dumped in a tangled heap on the table. Players take turns trying to pick up a single stick at a time without moving any of the other sticks. It is very difficult to pick up a stick if there is another stick lying on top of it. The players therefore try to pick up the sticks in an order such that they never have to pick up a stick from underneath another stick.

输入:

The input consists of several test cases. The first line of each test case contains two integers n and m each at least one and no greater than one million. The integer n is the number of sticks, and m is the number of lines that follow. The sticks are numbered from 1 to n. Each of the following lines contains a pair of integers a, b, indicating that there is a point where stick a lies on top of stick b. The last line of input is 0 0. These zeros are not values of n and m, and should not be processed as such.

输出:

The input consists of several test cases. The first line of each test case contains two integers n and m each at least one and no greater than one million. The integer n is the number of sticks, and m is the number of lines that follow. The sticks are numbered from 1 to n. Each of the following lines contains a pair of integers a, b, indicating that there is a point where stick a lies on top of stick b. The last line of input is 0 0. These zeros are not values of n and m, and should not be processed as such.

样例输入:

3 2
1 2
2 3
0 0

样例输出:

1
2
3

Pick up
sticks

Time
Limit: 10000/5000 MS (Java/Others)   
Memory Limit: 65536/32768 K (Java/Others)

Total
Submission(s): 31   
Accepted Submission(s): 12

 

 

Problem
Description

 

 

 

Pick up
sticks is a fascinating game. A collection of coloured sticks are
dumped in a tangled heap on the table. Players take turns trying to
pick up a single stick at a time without moving any of the other
sticks. It is very difficult to pick up a stick if there is another
stick lying on top of it. The players therefore try to pick up the
sticks in an order such that they never have to pick up a stick
from underneath another stick.

 

 

Input

The input
consists of several test cases. The first line of each test case
contains two integers n and m each at least one and no greater than
one million. The integer n is the number of sticks, and m is the
number of lines that follow. The sticks are numbered from 1 to n.
Each of the following lines contains a pair of integers a, b,
indicating that there is a point where stick a lies on top of stick
b. The last line of input is 0 0. These zeros are not values of n
and m, and should not be processed as such.

 

 

Output

For each
test case, output n lines of integers, listing the sticks in the
order in which they could be picked up without ever picking up a
stick with another stick on top of it. If there are multiple such
correct orders, any one will do. If there is no such correct order,
output a single line containing the word IMPOSSIBLE.

 

 

Sample
Input

3
2

1
2

2
3

0
0

 

 

Sample
Output

1

2

3

 

 

Source

 University of Waterloo
Local Contest 2009.09

 

 

 

 

 


昨天晚上想到
3点多还没有结果,今天早上,为了解决这道题,旷了三节微积分课,最后,经实验室学长指点终于做出来了,原来是在写toposort的时候太不仔细了,把u的数值给搞成索引了,现在终于解决了,这下可舒缓了一口气。虽然做的相当的悲剧。但是,这道题给我留下的财富也是相当可观的。至于微积分课,这个礼拜五花个一个下午去搞定吧,毕竟我学数学,也是因为数学的很多东西能应用到编程中去。

 


下面的
code是用C实现的代码很简洁就不必说明了

code:

#include
<stdio.h>

#include
<string.h>

#include
<stdlib.h>

#define
len 1000005

int
ans[len],head[len],next[len],val[len],degree[len],n,m;

bool
toposort(){

        
int i,front,rear,u;

        
for(i=rear=1;i<=n;i++)

                  
if(degree[i]==0)

                           
ans[rear++]=i;

        
for(front=1;front<rear;front++){

                  
for(u=head[ans[front]];u;u=next[u])

                           
if(–degree[val[u]]==0)

                                    
ans[rear++]=val[u];

        
}

        
if(rear==n+1)  return
true;

        
else          
return false;

}

int
main(void){

        
int i,x,y,k;

        
while(scanf(“%d%d”,&n,&m)==2&&m+n){

                  
memset(head,0,sizeof(head));

                  
memset(degree,0,sizeof(degree));

                  
for(i=k=1;i<=m;i++){

                           
scanf(“%d%d”,&x,&y);

                           
degree[y]++;

                           
val[k]=y;

                           
next[k]=head[x];   
head[x]=k++;

                  
}

                  
if(toposort())

                           
for(i=1;i<=n;i++)

                                    
printf(“%d\n”,ans[i]);

                  
else

                           
puts(“IMPOSSIBLE”);

        
}

        
return 0;

}




解题转自:http://blog.sina.com.cn/s/blog_64018c250100r16v.html


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

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。