VIJOS-P1199 核弹危机

JDOJ 1347: VIJOS-P1199 核弹危机

题目传送门

Description

shibowen和ganggang正在玩红警,可不料shibowen造出了核弹正要发射......(ganggang @_@) 已知核弹的攻击范围是边长n的正方形,ganggang的基地是边长m的正方形 基地样例: ...#.# .#...# ##...# ...... ..#### .#.... #表示房屋,.表示平地,求核弹最多能摧毁多少房屋(被核弹攻击的房屋都会消失,好强啊~~~~~~~)。

Input

第一行基地边长m(10000> m> 0) 第二行核弹攻击边长n(10000> m> -1) 接下来m行输入基地

Output

摧毁最多房屋数

Sample Input

6 3 ...#.# ###### ...... ...... #..... ...###

Sample Output

5

事实证明,这儿的数据水到爆炸,试想,m<10000,读入都读不下...

听说这里的m最大才8.

8///%%%

所以么我们可以考虑爆搜。

但是这种做法极为低级。

我们来介绍几种高级做法。

树状数组 or 前缀和

都是二维的。

树状数组的思路很好想,二维的树状数组统计的是从(1,1)到(x,y)这个区间的#个数。

然后我们就可以应用一下前缀和的思想。

VIJOS-P1199 核弹危机

通过这个图,我们可以看出来想要求出基佬紫区域的区间和,可以变成:

getsum(i,j)-getsum(i-n,j)-getsum(i,j-n)+getsum(i-n,j-n)

所以就很简单地出解了:

代码:

#include<cstdio>
#include<algorithm>
using namespace std;
int m,ans,n;
int c[1001][1001];
char str[1001];
void fix(int x,int y)
{
    for(int i=x;i<=m;i+=i&-i)
        for(int j=y;j<=m;j+=j&-j)
            c[i][j]++;
}
int getsum(int x,int y)
{
    int ret=0;
    for(int i=x;i;i-=i&-i)
        for(int j=y;j;j-=j&-j)
            ret+=c[i][j];
    return ret;
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",str+1);
        for(int j=1;j<=m;j++) 
            if(str[j]=='#')
                fix(i,j);
    }
    for(int i=n;i<=m;i++)
        for(int j=n;j<=m;j++)
            ans=max(ans,getsum(i,j)-getsum(i-n,j)-getsum(i,j-n)+getsum(i-n,j-n));
    printf("%d",ans);
    return 0;
}

这里我着重请大家注意一下读入,字符读入坑点很多,比如换行也得读进来...

然后我来介绍大佬写的前缀和@ysy

思路大同小异,附上第二份代码(绝壁比我的丑)

请大家择优录取(疯狂暗示)

代码II:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1010
int n,m,many[N][N],ans; char str[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        for(int j=1;j<=n;j++) if(str[j]=='#')
            many[i][j]++;
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        many[i][j]+=many[i][j-1];
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        many[i][j]+=many[i-1][j];
    for(int i=m;i<=n;i++) for(int j=m;j<=n;j++)
        ans=max(ans,many[i][j]+many[i-m][j-m]-many[i-m][j]-many[i][j-m]);
    printf("%d\n",ans);
}

你看还没有return 0。。。

上一篇:Asia Yokohama Regional Contest 2018 G题 What Goes Up Must Come Down


下一篇:树状数组维护前缀和、后缀和、个数|牛牛的Link Power