【洛谷】P5542 [USACO19FEB] Painting The Barn S（二维前缀和优化）

本文主要是介绍【洛谷】P5542 [USACO19FEB] Painting The Barn S（二维前缀和优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

这本暴力思路是不是很清晰，但是纯暴力这数据范围必t，我们观察发现其实耗时就是标记涂过的地方，所以我们现在将重心放在我们该如何优化上，不卖关子了，其实这是一个非常经典的二维前缀和优化~（具体细节观看代码，稳稳AC）

ACcode:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
int n,k,a[N][N],s[N][N];
void solve() {cin>>n>>k;for(int i=1;i<=n;i++){int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;x1++,x2++,y1++,y2++;//因为我们规定的数组下标从一开始a[x1][y1]++;a[x2][y2]++;a[x1][y2]--;a[x2][y1]--; }int ans=0;for(int i=1;i<=1000;i++)for(int j=1;j<=1000;j++){s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];if(s[i][j]==k)ans++;}cout<<ans<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t=1;//cin>>t;while(t--) {solve();}return 0;
}

over~

这篇关于【洛谷】P5542 [USACO19FEB] Painting The Barn S（二维前缀和优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---