首页 > 基础算法 > 模拟法 > hdu 1366 The Willy Memorial Program-模拟-[解题报告]
2013
12-09

hdu 1366 The Willy Memorial Program-模拟-[解题报告]

The Willy Memorial Program

问题描述 :

Willy the spider used to live in the chemistry laboratory of Dr. Petro. He used to wander about the lab pipes and sometimes inside empty ones. One night while he was in a pipe, he fell asleep. The next morning, Dr. Petro came to the lab. He didn’t notice Willy while opening the valve to fill the pipes with hot water. Meanwhile, Stanley the gray mouse got what was going to happen. No time to lose! Stan ran hard to reach the valve before Willy gets drawn, but… Alas! He couldn’t make it!

Poor Willy was boiled in hot water, but his memory is still in our hearts. Though Stan tried his best, we want to write a program, in the memory of Willy, to compute the time Stan had, to rescue Willy, assuming he started to run just when the doctor opened the valve.

To simplify the problem, assume the pipes are all vertical cylinders with diameter 1 cm. Every pipe is open from the top and closed at the bottom. Some of the pipes are connected through special horizontal pipes named links. The links have very high flow capacity, but are so tiny that at any given time, the volume of water inside them is negligible. The water enters from top of one of the pipes with a constant rate of 0.25πcm3/sec and begins to fill the pipe from the bottom until the water reaches a link through which it flows horizontally and begins to fill the connected pipe. From elementary physics we know if two pipes are connected and the surface of the water is above the connecting link, the level of water in both pipes remains the same when we try to fill one of them. In this case the water fills each pipe with a rate equal to half of the rate of incoming water. As an example, consider the following configuration:

First, the lower 2 centimeters of the left pipe is filled with water at full rate, then, the lower 3 centimeters of the right pipe is filled, and after that, the upper part of the two pipes are filled in parallel at half rate. The input to your program is a configuration of pipes and links, and a target level in one of the pipes (the heavy dotted line in the above figure). The program should report how long it takes for the level of water to reach the target level. For the above configuration, the output is 9 seconds.

It is assumed that the water falls very rapidly, such that the time required for the water to fall can be neglected. The target level is always assumed to be a bit higher than the specified level for it. As an example, if we set the target point to level 4 in the left pipe in the figure above, the elapsed time for water to reach that target is assumed to be 5 (not 2), Also note that if the water reaches to the top of a pipe (say in level x), it won’t pour out outside the pipe until empty spaces in connected pipes below level x are filled (if can be filled, i.e. the level of water reaches the connecting links). (Note that there may be some links at level x, to which water is entered). After all such spaces are filled; the water level would not go up further.

输入:

To describe positions, we assume the coordinates are expressed as (x, y) and the origin lies in the top-left of all pipes and links. (Note that y coordinates are increased downwards). All coordinates are integer numbers between 0 and 100, inclusive.
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is p (1 <= p <= 20), the number of pipes, followed by p lines, each describing a pipe. Each pipe description line consists of three numbers. The first two are (x, y) coordinates of the upper-left corner of the pipe and the third number is the height of the pipe (at least 1 cm and at most 20 cm). Note that diameter of each pipe is 1 cm.

After input data describing the pipes, there is a line containing a single integer l, which is the number of links (0 l 50). After it, there are l lines describing links. Each link description contains 3 integers. The first two are (x, y) coordinates of the left end-point of the link and the third is the length of the link (at least 1 cm and at most 20 cm). It is assumed that the width of the link is zero.

The last line for each test case contains two numbers. The first is the number of target pipe (starting from one, with the order appeared in test data). The second line is the desired y for the level of water in the target pipe (note that the specified level may be out of the pipe at all).

You can assume the following about the input:

The water enters into the first pipe.
No link crosses a pipe.
No two links have the same y coordinates.
No two pipes have the same upper-left x coordinates.
Both endpoints of each link are connected to pipes.

输出:

The output file should contain exactly t lines with no blank lines in between, each corresponding to one test case. Each output line should contain the time required for the water to reach the target level in the target pipe (an integer number). If in a specific test case, the water never reaches the target level, the line should contain No Solution string in it.

样例输入:

1
2
2 0 6
5 1 6
1
3 4 2
2 2

样例输出:

9

数据好小,然后乱搞。。。每次都从最下面开始一格一格灌水,然后判断有该格有没有管子相连,有的话就把连的那个管子和当前的管子合并,然后又重新从下面开始灌水,

直到达到或者溢出。。。

PS:好恶心的模拟题啊。。。WA了好久,发现循环变量名写错了一个。。。然后还是WA。。。最后才知道模拟的时候有一个判断的细节没有处理好,这个一定要注意,模拟题什么的要最仔细了,一定得想清楚。。- -#

写的很挫很挫的代码。。在zoj上用G++交会CE,然后把库函数改了,用C交AC。。。    - -|||||||,话说POJ的C++可以过。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>

#define N 1000000

using namespace std;

struct ty
{
    int x,y,len,bj;
    int linkx[75];
    int linky[75];
}pipe[50];
struct ty2
{
    int v,bj,link;
}f[120];
int ans;

int ok()
{
    int i,j,ii,flag[50],k;
    ans=0;
    memset(flag,0,sizeof(flag));
    flag[1]=1;
    for(i=0;i<=110;i++)f[i].link=-1;
    for(i=0;i<=110;i++)
    {
        if((pipe[1].y<=i)&&(i<pipe[1].y+pipe[1].len))f[i].v+=1;
        if(i<pipe[1].y)f[i].v+=10000000;
    }
    for(j=1;j<=pipe[1].linky[0];j++)
        f[pipe[1].linky[j]].link=pipe[1].linkx[j];
    if(pipe[1].bj!=-1)f[pipe[1].bj].bj=1;
    while(1)
    {
        for(i=110;i>=0;i--)
        {
            //printf("%d        %d\n",i,f[i].bj);
            if(f[i].v>=10000000)return f[i+2].bj;
            //printf("%d\n",f[i].bj);
            if(f[i+1].bj==1)return 1;
            //printf("%d   %d       %d         %d         %d\n",i,f[i].v,f[i].bj,f[i].link,ans);
            ans+=f[i].v;
            f[i].v=0;
            if((f[i].link>=0)&&(flag[f[i].link]==0))
            {
                k=f[i].link;
                f[i].link=-1;
                flag[k]=1;
                for(j=0;j<=110;j++)
                {
                    if((pipe[k].y<=j)&&(j<pipe[k].y+pipe[k].len))f[j].v+=1;
                    if(j<pipe[k].y)f[j].v+=1000000000;
                }
                for(j=1;j<=pipe[k].linky[0];j++)
                      f[pipe[k].linky[j]].link=pipe[k].linkx[j];
                //printf("        %d\n",pipe[k].bj);
                if(pipe[k].bj!=-1)f[pipe[k].bj].bj=1;
                break;
            }
            //if(f[i].bj==1)return 1;
        }
        if(i==-1)return 0;
    }
}

int main()
{
    int t,p,l,x,y,len,t1,t2;
    scanf("%d",&t);
    while(t--)
    {
        memset(pipe,0,sizeof(pipe));
        memset(f,0,sizeof(f));
        scanf("%d",&p);
        for(int i=1;i<=p;i++)
        {
            scanf("%d%d%d",&pipe[i].x,&pipe[i].y,&pipe[i].len);
            pipe[i].bj=-1;
        }
        scanf("%d",&l);
        for(int i=1;i<=l;i++)
        {
            scanf("%d%d%d",&x,&y,&len);
            for(int j=1;j<=p;j++)
            {
                if(pipe[j].x+1==x)t1=j;
                if(pipe[j].x==x+len)t2=j;
            }
            pipe[t1].linkx[++pipe[t1].linkx[0]]=t2;
            pipe[t1].linky[++pipe[t1].linky[0]]=y;
            pipe[t2].linkx[++pipe[t2].linkx[0]]=t1;
            pipe[t2].linky[++pipe[t2].linky[0]]=y;
        }
        scanf("%d%d",&x,&y);
        pipe[x].bj=y;
        if(y<pipe[x].y||y>pipe[x].y+pipe[x].len){printf("No Solution\n");continue;}
        if(ok())printf("%d\n",ans);
        else    printf("No Solution\n");
    }
    return 0;
}

解题转自:http://blog.csdn.net/wilsonlym/article/details/7578287


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧