深圳手机端网站建设专业公司,百度最怕哪个投诉电话,建设银行泰州分行网站,海诚网站建设正题 题目大意
对一个全白矩阵每次选择一个矩阵颜色取反。
然后求最后所有黑色联通块的周长之和。 解题思路
因为是算周长#xff0c;所以我们将一个矩阵拆分成4条边#xff0c;然后将横竖分开处理。
若处理横的边#xff0c;我们按照xxx为关键字排序。
然后对于xxx不同…正题 题目大意
对一个全白矩阵每次选择一个矩阵颜色取反。
然后求最后所有黑色联通块的周长之和。 解题思路
因为是算周长所以我们将一个矩阵拆分成4条边然后将横竖分开处理。
若处理横的边我们按照xxx为关键字排序。
然后对于xxx不同的边分开处理那么一行最多NNN个点我们先将这些点离散化。
我们发现一条被覆盖了奇数次的边才会被统计入答案所以我们可以用一个差分数组维护计算一条边经过了多少次然后统计答案。
因为总共只有8∗N8*N8∗N个点所以可以过。
时间复杂度O(NlogN)O(N\ log\ N)O(N log N) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N50100;
struct line{int x,l,r;
}a[2*N],e[2*N];
int num,n,b[2*N],s[2*N],cnt,v[2*N],ans;
void addl(int x,int l,int r)
{a[num](line){x,l,r};}
void adde(int x,int l,int r)
{e[num](line){x,l,r};}
bool cmp(line x,line y)
{return x.xy.x;}
void work(line *a)
{int L1,R0;for(R1;Rnum;){while(a[R].xa[R1].x) R;cnt0;for(int iL;iR;i)b[cnt]a[i].l,b[cnt]a[i].r;sort(b1,b1cnt);cntunique(b1,b1cnt)-b-1;for(int i1;icnt;i)v[b[i]]i,s[i]0;for(int iL;iR;i)s[v[a[i].l]],s[v[a[i].r]]--;for(int i1;icnt;i)s[i]s[i-1];for(int i1;icnt;i)ans(s[i]1)*(b[i1]-b[i]);R;LR;}
}
int main()
{scanf(%d,n);for(int i1;in;i){int x1,y1,x2,y2;scanf(%d%d%d%d,x1,y1,x2,y2);x2,y2;num;addl(x1,y1,y2);adde(y2,x1,x2);num;adde(y1,x1,x2);addl(x2,y1,y2);}sort(a1,a1num,cmp);sort(e1,e1num,cmp);work(a);work(e);printf(%d,ans);
}
