poj 2434;bzoj 1686 [Usaco2005 Open]Waves 波纹

Description

Input

    第1行：四个用空格隔开的整数Pj Bi，B2，R. P(1≤P≤5)表示石子的个数，Bi(-5×100000≤Bi≤5×100000)和B2（-5×100000≤B2≤5×100000）表示两个河堤的z坐标，R(1≤R≤5×100000)表示你要描述湖面多少秒．没有两个石子会在同一时间砸到同一地点，两个河堤一定有不同的坐标，没有石子会砸到河堤上去．

    第2到P+1行：每行有三个用空格隔开的整数描述了一颗石子，X，K T(-5×100000≤X，K T≤5×100000).X．y表示石子砸的地点的坐标，T表示石子是什么时候砸下去的．

Output

    输出是一个9半9的矩阵，中心在(0，0)点．左下点的坐标为(-4，-4)，右上点的坐标为(4，4)．这个矩阵表现的是R秒时湖面状态．

Sample Input

2 4 100 4
-3 0 1
0 0 2

Sample Output

--------X
-*------X
*-*-*---X
-o-*-*--X
o-----*-X
-o-*-*--X
*-*-*---X
-*------X
--------X

WA了n+1发……

最后发现我的输出把整个图形上下翻转了……改完就A了……T_T

 

正确的做饭应该是枚举每个对所求的输出有影响的波，然后直接跑，遇到在俩堤岸之间往返的就求出时间取个模……然而我实在比较挫，直接跑了，反正不会T……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m1,m2,r,x,y,t,xx,yy,ti,ll,rr,qaq,i,j;
bool f;
int map[][];
void sp(){
    while(ti--){
        if (f){
            yy++;
            if (yy==m1||yy==m2) yy--,f=;
        }else{
            yy--;
            if (yy==m1||yy==m2) yy++,f=;
        }
    }
}
void op(){
    ll=max(,x-t),rr=min(,x+t);
    for (i=ll;i<=rr;i++){
        ti=min(i-(x-t),(x+t)-i);xx=i,yy=y;
        f=;sp();
        if (yy>=&&yy<=) map[xx][yy]+=qaq;
        if (i==x-t||i==x+t) continue;
        ti=min(i-(x-t),(x+t)-i);xx=i;yy=y;
        f=;sp();
        if (yy>=&&yy<=) map[xx][yy]+=qaq;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m1,&m2,&r);
    m1+=;m2+=;
    while(n--){
        scanf("%d%d%d",&y,&x,&t);
        x+=;y+=;
        t=r-t;
        qaq=;op();
        t-=;
        if (t>=) qaq=-,op();
    }
    for (i=;i>=;i--){
        for (j=;j<=;j++)
        if (j==m1||j==m2) printf("X");else if (map[i][j]==) printf("-");else if (map[i][j]>=) printf("*");else if (map[i][j]<=-) printf("o");
        printf("\n");
    }
}

然后还有修改后的

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m1,m2,r,x,y,t,xx,yy,ti,ll,rr,qaq,i,j;
bool f;
int map[][];
void ssp(){
    if (f){
        if (ti<m2-yy){
            yy+=ti;
            return;
        }
        if (ti<=m2-yy){
            yy+=ti-;
            return;
        }
        ti-=m2-yy;
        yy=m2-;
        f=;ssp();
    }else{
        if (ti<yy-m1){
            yy-=ti;
            return;
        }
        if (ti<=yy-m1){
            yy-=ti-;
            return;
        }
        ti-=yy-m1;
        yy=m1+;
        f=;ssp();
    }
}
void sp(){
    if (yy<m1&&(!f)) yy-=ti;else
    if (yy>m2&&f) yy+=ti;else
    if (yy>m2&&(!f)){
        if (ti<yy-m2) yy-=ti;else
        if (ti<=yy-m2) yy-=ti-;else
        ti-=yy-m2,f=,yy=m2+,sp();
        return;
    }else
    if (yy<m1&&f){
        if (ti<m1-yy) yy+=ti;else
        if (ti<=m1-yy) yy+=ti-;else
        ti+=m1-yy,f=,yy=m1-,sp();
        return;
    }else{
        ti%=(m2-m1-)*;
        ssp();
    }
    return;
}
void op(){
    ll=max(,x-t),rr=min(,x+t);
    for (i=ll;i<=rr;i++){
        ti=min(i-(x-t),(x+t)-i);xx=i,yy=y;
        f=;sp();
        if (yy>=&&yy<=) map[xx][yy]+=qaq;
        if (i==x-t||i==x+t) continue;
        ti=min(i-(x-t),(x+t)-i);xx=i;yy=y;
        f=;sp();
        if (yy>=&&yy<=) map[xx][yy]+=qaq;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m1,&m2,&r);
    if (m1>m2) swap(m1,m2);
    m1+=;m2+=;
    while(n--){
        scanf("%d%d%d",&y,&x,&t);
        x+=;y+=;
        t=r-t;
        qaq=;op();
        t-=;
        if (t>=) qaq=-,op();
    }
    for (i=;i>=;i--){
        for (j=;j<=;j++)
        if (j==m1||j==m2) printf("X");else if (map[i][j]==) printf("-");else if (map[i][j]>=) printf("*");else if (map[i][j]<=-) printf("o");
        printf("\n");
    }
}