11.17 模拟赛&&day-2

/*

后天就要复赛了啊啊啊啊啊.

可能是因为我是一个比较念旧的人吧.

讲真 还真是有点不舍.

转眼间一年的时间就过去了.

2015.12-2016.11.

OI的一年.

NOIP gryz RP++.

*/

水灾（sliker.cpp/c/pas） 1000MS 64MB

大雨应经下了几天雨，却还是没有停的样子。土豪CCY刚从外地赚完1e元回来，知道不久除了自己别墅，其他的地方都将会被洪水淹没。

CCY所在的城市可以用一个N*M(N,M<=50)的地图表示，地图上有五种符号：“. * X D S”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，CCY和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始发生洪水）。“D”表示CCY的别墅。“S”表示CCY现在的位置。

CCY每分钟可以向相邻位置移动，而洪水将会在CCY移动之后把相邻的没有的土地淹没（从已淹没的土地）。

求CCY回到别墅的最少时间。如果聪哥回不了家，就很可能会被淹死，那么他就要膜拜黄金大神涨RP来呼叫直升飞机，所以输出“ORZ hzwer!!!”。

输入文件 sliker.in

输出文件 sliker.out

Input

3 3

D.*

…

.S.

Output

3

Input

3 3

D.*

…

..S

Output

ORZ hzwer!!!

Input

3 6

D…*.

.X.X..

….S.

Output

6

/*

寒假原题.

两遍bfs即可.

论bfs中标志数组的重要性.

然而当时我只打了个表.....

然后学长讲了以后我就懵逼了.

发现自己成长了好多(这都是后话...)

*/

#include<iostream>

#include<cstdio>

#include<queue>

#define MAXN 51

using namespace std;

int n,m,s[MAXN][MAXN],sx,sy,tx,ty;

char g[MAXN][MAXN];

bool b[MAXN][MAXN];

struct node{int x,y,t;};

int dx[5]={0,1,0,-1,0};

int dy[5]={0,0,1,0,-1};

queue<node>q;

inline void slovebfs()

{

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

      for(int j=1;j<=m;j++) s[i][j]=1e5;

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

      for(int j=1;j<=m;j++)

         if(g[i][j]=='*') q.push((node){i,j}),s[i][j]=0;

    node u;int x,y,xx,yy;

    while(!q.empty())

    {

        u=q.front();q.pop();x=u.x,y=u.y;

        for(int i=1;i<=4;i++)

        {

            xx=x+dx[i],yy=y+dy[i];

            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]!='X'&&g[xx][yy]!='D')

            {

                if(s[xx][yy]>s[x][y]+1)

                  s[xx][yy]=s[x][y]+1,q.push((node){xx,yy});

            }

        }

    }

}

inline void bfs()

{

    int x,y,xx,yy;

    node u;

    q.push((node){sx,sy,0});

    b[sx][sy]=true;

    while(!q.empty())

    {

        u=q.front();q.pop();

        x=u.x,y=u.y;

        if(x==tx&&y==ty){printf("%d",u.t);return;}

        for(int i=1;i<=4;i++)

        {

            xx=x+dx[i],yy=y+dy[i];

            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!b[xx][yy]&&g[xx][yy]!='X')

            {

                if(u.t+1<s[xx][yy])

                  b[xx][yy]=true,q.push((node){xx,yy,u.t+1});

            }

        }

    }

    printf("ORZ hzwer!!!");

}

int main()

{

    freopen("sliker.in","r",stdin);

    freopen("sliker.out","w",stdout);

    scanf("%d%d",&n,&m);

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

      {

        cin>>g[i]+1;

        for(int j=1;j<=m;j++)

        {

          if(g[i][j]=='S') sx=i,sy=j;

          if(g[i][j]=='D') tx=i,ty=j;

        }

      }

    slovebfs();

    bfs();

    return 0;

}

某种数列问题 (jx.cpp/c/pas) 1000MS 256MB

众所周知，chenzeyu97有无数的妹子(阿掉！>_<)，而且他还有很多恶趣味的问题，继上次纠结于一排妹子的排法以后，今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排，然后对于每个妹子有一个美丽度，当然美丽度越大越好，chenzeyu97妹子很多，但是质量上不容乐观，经常出现很多美丽度为负数的妹子(喜闻乐见)，chenzeyu97希望从一排妹子里找出3队连续的妹子，使她们的美丽度和最大。注意，一个妹子不能被编入多个队伍而且一定要拿出三队，不然czy会闲着没事做~。

简单滴说就是：

给定一个数列，从中找到3个无交集的连续子数列使其和最大。

【输入文件】

第一行一个数n，表示数列长度。

接下来有n行，每行一个数，第i行为第i个数。

【输出文件】

仅有一个数，表示最大和。

【样例输入】 jx.in

10

-1

2

3

-4

0

1

-6

-1

1

-2

【样例输出】 jx.out

7

【样例说明】

第一队妹子取2，3。

第二队妹子取0，1。

第三队妹子取1。

【数据范围】

请大家放心，虽然chenzeyu97妹子无数，但是这次他叫来的个数n是有限的。=v=

对于30%的数据，妹子数不大于200。

对于60%的数据，妹子数不大于2000。

对于100%的数据，妹子数1000000。

而且，由于chenzeyu97没有CCR那样的影响力，所以他的妹子选完的最大美丽度和不超过maxlongint。(注:CCR随便选就爆long long，因为他是把妹狂魔=V=)。

/*

一开始分别跑了三次最大子段和.

骗了骗大数据的分(只要正数段数>=3就对).

然后正解还是比较好想的.

然而一开始我竟然凭第六感认为内存不够orz...

闲的没事儿滚动一下...

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#define MAXN 1000001

#define LL long long

using namespace std;

LL f[2][4][2],n,a[MAXN],ans;

LL read()

{

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

int main()

{

    freopen("jx.in","r",stdin);

    freopen("jx.out","w",stdout);

    n=read();

    memset(f,-127/3,sizeof f);

    f[0][0][0]=0;

    for(int i=1;i<=n;i++) a[i]=read();

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

      for(int j=0;j<=min(i,3);j++)

        {

            f[i&1][j][0]=max(f[(i-1)&1][j][0],f[(i-1)&1][j][1]);

            if(j)f[i&1][j][1]=max(f[(i-1)&1][j-1][0],

            max(f[(i-1)&1][j-1][1],f[(i-1)&1][j][1]))+a[i];

            else f[i&1][j][0]=a[i];

        }

    ans=max(f[n&1][3][0],f[n&1][3][1]);

    cout<<ans;

    return 0;

}

巴特西

11.17 模拟赛&&day-2

最新文章

热门文章