CF-1031-C. Smilo and Minecraft（二维前缀和）

思路讲解

简单来说，就是第一次炸了以后还能存活下来的金块，一定能活下来。

那么形式化的理解就是说第一次炸完以后，剩下的空间就足够其他炸弹进行一些精细操作了。

然后枚举+二维前缀和，就可以用二维前缀和来求。

FOR(i,1,N){
	FOR(j,1,M){
		Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]+(G[i][j]=='g')-Sum[i-1][j-1];
	}
}
ll ans=0;
FOR(i,1,N){
	FOR(j,1,M){
		if(G[i][j]=='.'){
			ll xl=max(i-K+1,1ll),xr=min(i+K-1,N),yl=max(1ll,j-K+1),yr=min(M,j+K-1);
			ll lans=Sum[xr][yr]+Sum[xl-1][yl-1]-Sum[xl-1][yr]-Sum[xr][yl-1];
			ans=max(ans,Sum[N][M]-lans);
		}
	}
}

AC代码

https://codeforces.com/contest/2113/submission/325681423

源代码

// Problem: C. Smilo and Minecraft  C. Smilo 和 Minecraft
// Contest: Codeforces - Codeforces Round 1031 (Div. 2)Codeforces 第 1031 轮（第 2 组）
// URL: https://codeforces.com/contest/2113/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(5e2)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
char G[MAXN][MAXN];
ll Sum[MAXN][MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N>>M>>K;
	init();
	FOR(i,1,N){
		FOR(j,1,M){
			cin>>G[i][j];
		}
	}
	FOR(i,1,N){
		FOR(j,1,M){
			Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]+(G[i][j]=='g')-Sum[i-1][j-1];
		}
	}
#ifdef LOCAL
    FOR(i,0,N){
		FOR(j,0,M){
			cerr<<Sum[i][j]<<" ";
		}
		cerr<<"\n";
	}
#endif
	ll ans=0;
	FOR(i,1,N){
		FOR(j,1,M){
			if(G[i][j]=='.'){
				ll xl=max(i-K+1,1ll),xr=min(i+K-1,N),yl=max(1ll,j-K+1),yr=min(M,j+K-1);
				ll lans=Sum[xr][yr]+Sum[xl-1][yl-1]-Sum[xl-1][yr]-Sum[xr][yl-1];
#ifdef LOCAL
	debug(Sum[xl-1][yr]);debug(Sum[xl][yr-1]);
    debug(i);debug(j);debug(xl);debug(yl);debug(yr);debug(xr);debug(lans);
#endif
				ans=max(ans,Sum[N][M]-lans);
			}
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2113/submission/325681423
*/

心路历程（WA，TLE，MLE……）