题面
题解
这个是CSP前最后一场测试的 T2,打的不是很好,没有想到这题正解,但是这题暴力分很多ww
二进制拆位的思想要有((
30分
暴力模拟 \(O(nmT)\)
70分
满足 \(1 \leq a[i][j], k[i] \leq 2\)
对每种肥料做一遍前缀和,得出每个点被哪些种类覆盖. \(O(T+nm)\). 因为只有两种所以很可做.
100分
部分分启发我们二进制拆位(虽然测试的时候没启发到我)
总之拆位.
对每一位的 \(0\) 和 \(1\) 分别做一遍前缀和,最后如果与 \(a[i][j]\) 不同的位上有肥料,他就安详地去世了.
效率就是\(O((T+nm)\log nm)\)
然后你会发现你 RE
MLE
了
实现要注意:
不要用 vector,空间真的很容易炸
把二维数组压成一位数组
把枚举位数的循环扔外面,数组可以少一位
然后你就快乐 AC
了
(当然这题有别的做法,什么树状数组之类的
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+5;
int n,m,T;
int a[N<<2],d[2][N<<2],xa[N],ya[N],xb[N],yb[N],k[N],ans[N<<2];
inline int f(int i, int j) { return i*(m+3)+j; }
int main()
{
scanf("%d%d%d",&n,&m,&T);
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&a[f(i,j)]);
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ans[f(i,j)]=1;
for(int i=1; i<=T; i++) scanf("%d%d%d%d%d",&xa[i],&ya[i],&xb[i],&yb[i],&k[i]);
for(int c=0; c<22; c++)
{
for(int t=0; t<=1; t++) for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) d[t][f(i,j)]=0;
for(int i=1; i<=T; i++)
{
d[(k[i]>>c)&1][f(xa[i],ya[i])]++;
d[(k[i]>>c)&1][f(xb[i]+1,yb[i]+1)]++;
d[(k[i]>>c)&1][f(xa[i],yb[i]+1)]--;
d[(k[i]>>c)&1][f(xb[i]+1,ya[i])]--;
}
for(int t=0; t<=1; t++) for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)
d[t][f(i,j)]+=d[t][f(i,j-1)]+d[t][f(i-1,j)]-d[t][f(i-1,j-1)];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
int t=(a[f(i,j)]>>c)&1;
if(d[t^1][f(i,j)]>0) ans[f(i,j)]=0;
}
}
int cnt=0;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(!ans[f(i,j)]) cnt++;
printf("%d\n",cnt);
return 0;
}
标签:nm,int,题解,5093,这题,数组,DTOJ,拆位
From: https://www.cnblogs.com/copper-carbonate/p/16886591.html