数据太水，四重循环暴力解答 (o ° ω ° O )

#include <iostream>
using namespace std;
char a[10005][10005];
int n,m;
int main()
{
    int ans=0,tot;
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }            
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            tot=0;
            for(int q=i;q<=i+n-1;q++)
            {
                for(int p=j;p<=j+n-1;p++)
                {                
                    if(a[q][p]=='#')
                    tot++;
                    if(tot>ans)
                    ans=tot;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

/*pwq*/
#include<cstdio> 
#include<cstring>
using namespace std;
int a[1100][1100],k;
char tmp[1100];
int chk(int x,int y)
{
    int ret=0;
    for(int i=x;i<x+k;i++)
    {
        for(int j=y;j<y+k;j++)
        {
            if(a[i][j])
               ret++;
        }
    }
    return ret;
}
int main()
{
    int n,max=0;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",tmp);
        for(int j=1;j<=n;j++)
        {
            if(tmp[j-1]=='#')
                a[i][j]=1;
        }
    }
    for(int i=1;i<=n-k+1;i++)
    {
        for(int j=1;j<=n-k+1;j++)
        {
            int tmp=chk(i,j);
            if(max<tmp)
                max=tmp;
        }
    }
    printf("%d",max);
    return 0;  
}  

数据很水？其实可以做前缀和，速度快一些。

#include <iostream>

using namespace std;

int m,n;
bool jd[10000][10000]={0};

int main()
{
    cin>>m>>n;
    int i,j,k,now,ans=0;
    char c;
    for(i=0;i<m;i++)
    {
        for(j=0;j<m;j++)
        {
            cin>>c;
            if(c=='#')
            {
                jd[i][j]=true;
            }
        }
    }
    for(i=m-n;i>=0;i--)
    {
        now=0;
        for(j=0;j<n;j++)
        {
            for(k=0;k<n;k++)
            {
                if(jd[i+j][m-n+k])
                {
                    now++;
                }
            }
        }
        ans=max(ans,now);
        for(j=m-n-1;j>=0;j--)
        {
            for(k=0;k<n;k++)
            {
                if(jd[i+k][j])
                {
                    now++;
                }
                if(jd[i+k][j+n])
                {
                    now--;
                }
            }
            ans=max(ans,now);
        }
    }
    cout<<ans<<endl;
    return 0;
}

四重循环不超时……

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main()
{
    int m,n;
    scanf("%d %d",&m,&n);
    getchar();
    char d[m][m];
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<m;j++)
            d[i][j]=getchar();
        getchar();
    }
    int ans=-1;
    for(int i=0;i<m-n+1;i++)
        for(int j=0;j<m-n+1;j++)
        {
            int sum=0;
            for(int p=i;p<n+i;p++)
                for(int q=j;q<n+j;q++)
                    if(d[p][q]=='#')
                        sum++;
            ans=max(ans,sum);
        }
    cout<<ans<<endl;
    return 0;
}

So Water
```cpp
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int a[300][300];
int main()
{
int max=0;
memset(a,0,sizeof(a));
cin>>m>>n;
for(int i=1;i<=m;i++)
{
getchar();
for(int j=1;j<=m;j++)
{
char c;
c=getchar();
if(c=='#')a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+1;
else a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)

{

int nmax,vi,vj;
vi=i+n-1;if(vi>m)vi=m;
vj=j+n-1;if(vj>m)vj=m;
nmax=a[vi][vj]-a[i-1][vj]-a[vi][j-1]+a[i-1][j-1];
if(nmax>max)max=nmax;
}
}
if(n==0)cout<<0;
else cout<<max;
return 0;
}

容斥原理
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<stdlib.h>
using namespace std;
int m,n;
int f[1200][1200],sum,sumB[120][120],ans=0;

int main(){
cin >> m;
cin >> n;
if (n==0){cout << 0;return 0;}
memset(f,0,sizeof(f));
memset(sumB,0,sizeof(sumB));
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++){
char a;
cin >> a;
if (a=='#')f[i][j]=1;
else if (a=='.')f[i][j]=0;
if (j==m)getchar();
}
for (int right=1;right<=m;right++)sumB[0][right]=0;
for (int bottom=1;bottom<=m;bottom++){
sum=0;
for (int right=1;right<=m;right++){
sum+=f[bottom][right];
sumB[bottom][right]=sumB[bottom-1][right]+sum;
}
}
for (int i=1;i<=m-n+1;i++)
for (int j=1;j<=m-n+1;j++){
int b=sumB[i+n-1][j+n-1]-sumB[i+n-1][j-1]-sumB[i-1][j+n-1]+sumB[i-1][j-1];
if (b>ans)ans=b;
}
cout << ans;
return 0;
}

前缀和+枚举核弹头位置

#include<ctime>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[11234][11234];
int main()
{
    int i,j;
    cin>>n>>m;
    if(m==0){
        cout<<"0";
            return 0;
    }
    else{
        
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                char ch;
                cin>>ch;
                if(ch=='#'){
                    a[i][j]++;
                
                }
                a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            }
        }
    }           
    int ans=0;
    int x1=0,y1=0;
    for(i=1;i<=n-m+1;i++){
        for(j=1;j<=n-m+1;j++){
            //枚举弹头
            int t=a[i+m-1][j+m-1]-a[i-1][j+m-1]-a[i+m-1][j-1]+a[i-1][j-1];
            
            ans=max(ans,t);
    
            }
            
        }
cout<<ans<<endl;
    return 0;
}

so water

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>  
#include <cmath>  
#include <cstring>  
#include <set>  
using namespace std;
int a[11000][11000],k;
int check(int x,int y)
{
    int all=0;
    for(int i=x;i<x+k;i++)
    {
        for(int j=y;j<y+k;j++)
        {
            if(a[i][j])
                all++;
        }
    }
    return all;
}
int main()
{
    int n,max=0;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        char line[11000];
        scanf("%s",line);
        for(int j=1;j<=n;j++)
        {
            if(line[j-1]=='#')
                a[i][j]=1;
        }
    }
    for(int i=1;i<=n-k+1;i++)
    {
        for(int j=1;j<=n-k+1;j++)
        {
            int p=check(i,j);
            if(max<p)
                max=p;
        }
    }
    printf("%d",max);
    return 0;  
}  

#include <bits/stdc++.h>
using namespace std;
int ans[10001][10001];
char a; 
int main()
{
    int max=0,i,j,k,l,n,m;
    memset(ans,0,sizeof(ans));
    cin>>n;
    cin>>m;
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            cin>>a;
            if(a=='#') ans[i][j]=1;
        }
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            k=0;
            for(int h=i;h<i+m;h++) {
                for(int hh=j;hh<j+m;hh++) {
                    k+=ans[h][hh];
                }
            }
            if(k==m*m) {
                cout<<k<<endl;
                return 0;
            }
            if(k>max) max=k;
        }
    }
    cout<<max<<endl;
    return 0;
}

需要剪枝？

Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
24 lines compiled, 0.0 sec, 28016 bytes code, 1268 bytes data

测试数据 #0: Accepted, time = 0 ms, mem = 98656 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 98656 KiB, score = 20

测试数据 #2: Accepted, time = 0 ms, mem = 98656 KiB, score = 20

测试数据 #3: Accepted, time = 0 ms, mem = 98656 KiB, score = 20

测试数据 #4: Accepted, time = 0 ms, mem = 98656 KiB, score = 20

Accepted, time = 0 ms, mem = 98656 KiB, score = 100

暴力搜索
世界核平
#include <cstdio>
#include <cstring>

int main(){
freopen("in.txt","r",stdin);
int m,n;
scanf("%d%d",&m,&n);
char A[1000][1000];
memset(A,'.',sizeof(A));
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
scanf(" %c",&A[i][j]);
int cnt,ans=0;
for(int i=0;i<m;i++)
for(int j=0;j<m;j++){
cnt=0;
for(int ai=0;ai<n;ai++)
for(int aj=0;aj<n;aj++)
if(A[i+ai][j+aj]=='#')
cnt++;
ans=ans>cnt?ans:cnt;
}
printf("%d",ans);
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k=0,sum=0;
char a[1001];
int bome[1001][1001]={0},qu,su;
int ms(int ,int );

int main ()
{
cin>>m>>n;
for(int i=1;i<=m*m;i++)
cin>>a[i];

if(n>m)

n=m;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
{if(k>m*m)break;
k++;
if(a[k]=='#'){bome[i][j]=bome[i][j-1]+1;}
else {bome[i][j]=bome[i][j-1];}

}

for(int i=1;i<=m-n+1;i++)
for(int j=1;j<=m-n+1;j++)
if(sum<ms(i,j))
sum=ms(i,j);

cout<<sum;

return 0;
}

int ms(int q,int s )
{

int muqian=0;
for(int i=1;i<=n;i++)
{

muqian+=bome[q][s+n-1]-bome[q][s-1];

q++;
}
return muqian;

}

大水题，无力吐槽，暴搜直接过
pascal
program dsfa;
var a:array[1..10000,1..10000] of char;
i,j,k,l,n,m,s,t,v:longint;
begin
readln(m);
readln(n);
s:=0;
for i:=1 to m do
begin
for j:=1 to m do
read(a[i,j]);
readln;
end;
for i:=1 to m-n+1 do
for j:=1 to m-n+1 do
begin
t:=0;
for k:=i to i+n-1 do
for l:=j to j+n-1 do
if a[k,l]='#' then t:=t+1;
if t>s then s:=t;
end;
writeln(s);
end.

一个一个读字符需readln 否则回车被读入 答案就错了

记录信息
评测状态    Accepted
题目  P1199 核弹危机
递交时间    2016-06-14 13:28:29
代码语言    C++
评测机 ShadowShore
消耗时间    0 ms
消耗内存    98372 KiB
评测时间    2016-06-14 13:28:30
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 98372 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 98364 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 98372 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 98368 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 98368 KiB, score = 20
Accepted, time = 0 ms, mem = 98372 KiB, score = 100
代码
#include<cstdio>
using namespace std;
const int MAXN=10001;
struct house
{
  char a[MAXN];
}map[MAXN];
int m,n,ans=0;
int main()
{
  //freopen("crisis.in","r",stdin);
  //freopen("crisis.out","w",stdout);
  scanf("%d\n%d",&m,&n);
  for(int i=1;i<=m;i++)
    scanf("%s",&map[i].a[1]);
  for(int i=1;i<=m-n+1;i++)
    for(int j=1;j<=m-n+1;j++)
    {
      int count=0;
      for(int k=i;k<=i+n-1;k++)
        for(int t=j;t<=j+n-1;t++)
          if(map[k].a[t]=='#')count++;
      if(count>ans)ans=count;
    }
  printf("%d",ans);
  return 0;
}

数据小，没想到暴力也能过
#include<iostream>
using namespace std;

char s[10001][10001];
int n,m;
int main()
{
int max=0;
cin>>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cin>>s[i][j];
int t;
for (int i=1;i<=n-m+1;i++)
for (int j=1;j<=n-m+1;j++)
{
t=0;
for (int k=i;k<=i+m-1;k++)
for (int l=j;l<=j+m-1;l++)
if (s[k][l]=='#') t++;
if (max<t)max=t;
}
cout<<max;
}

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
int n,m;
char yu[10000][10000];
int d[10000][10000];
int ans(int x,int y)
{
int sum=0;
for(int i=y;i<y+m;i++)
{
sum+=d[x][i]-d[x+m][i];
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int k=0;k<n;k++)
{
cin>>yu[i][k];
}
}int sum;
for(int i=0;i<n;i++)
{
sum=0;
for(int k=n-1;k>=0;k--)
{
if(yu[i][k]=='#')sum++;
d[k][i]=sum;
}
}
int tt=0;
for(int i=0;i<n;i++)
{
for(int k=0;k<n;k++)
{
tt=max(ans(i,k),tt);
}
}
cout<<tt;
return 0;
}

#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;

unsigned short m,n;
char c;
unsigned int ans=0;
vector<vector<unsigned int> > map;

int main(){
scanf("%hu\n%hu\n",&n,&m);
map.resize(n+1);
for(vector<vector<unsigned int> >::iterator i=map.begin();i!=map.end();i++){
i->resize(n+1);
}

for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%c",&c);
map[i][j]=map[i-1][j]+map[i][j-1]-map[i-1][j-1]+(c=='#');
if(i>=m&&j>=m){
ans=max(ans,map[i][j]-map[i-m][j]-map[i][j-m]+map[i-m][j-m]);
}
}
scanf("\n");
}

if(m>n){
ans=map[n][n];
}
printf("%u\n",ans);
}
这数据神水啊，这样用的STL都秒过！
测试数据 #0: Accepted, time = 0 ms, mem = 516 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 516 KiB, score = 20
测试数据 #2: Accepted, time = 1 ms, mem = 520 KiB, score = 20
测试数据 #3: Accepted, time = 1 ms, mem = 516 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 520 KiB, score = 20

测试数据 #0: Accepted, time = 0 ms, mem = 520 KiB, score = 20
测试数据 #1: WrongAnswer, time = 0 ms, mem = 516 KiB, score = 0
测试数据 #2: Accepted, time = 0 ms, mem = 516 KiB, score = 20
测试数据 #3: WrongAnswer, time = 0 ms, mem = 512 KiB, score = 0
测试数据 #4: Accepted, time = 1 ms, mem = 516 KiB, score = 20
WrongAnswer, time = 1 ms, mem = 520 KiB, score = 60
代码
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int main()
{
long long int n,m;
vector<char>mapp;
vector< vector<char> >maap;
cin>>n>>m;
long long int i,j;
int fh=0;
for(j=0;j<n;++j)
{
mapp.push_back('a');
}
for(i=0;i<n;++i)
{
for(j=0;j<n;++j)
{
cin>>mapp[j];
if(mapp[j]=='#')fh++;
}
maap.push_back(mapp);
}
if(m>=n)
{
cout<<fh;
return 0;
}
static long long int x,y;
long long int i1,j1;
static long long int ans=-1;
static long long int w;
for(i=0;y<n;++i)
{
y=i+m;
for(j=0;x<n;++j)
{
x=j+m;
for(i1=i;i1<y;++i1)
{
for(j1=j;j1<x;++j1)
{
if(maap[i1][j1]=='#')w++;
}
}
ans=ans>w? ans:w;
w=0;
}
}
cout<<ans;
return 0;
}
无奈了。。。。。