Gym 101470J Stange Antennas【思维】

本文主要是介绍Gym 101470J Stange Antennas【思维】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

给出一个n*n大小的矩阵，现在要进行a次操作，每次操作有四个元素:

(x,y,p,dir)，表示在（x，y）处，往dir方向上放置一个直角边长度为p的三角形。

问覆盖位子为奇数次数的位子的个数。

思路：

①我们考虑将大问题分成若干个子问题这个问题就简单了。

对应每一种操作，我们将其分成列上边的操作，相当于一个三角形变成若干个列的覆盖。

②然后对于每一列的覆盖，我们对其进行模拟即可。

时间复杂度O（n^2）；

Ac代码：

#include <bits/stdc++.h>
#define maxs 200202
#define mme(i,j) memset(i,j,sizeof(i))
#define ll long long int
using namespace std;
int ans,n;
struct node
{int r,c,r2;
}a[12000000];
int cmp(node a,node b)
{return a.c<b.c;
}
void Slove(int ss,int ee)
{//printf("--- %d %d\n",ss,ee);int vis[35000];memset(vis,0,sizeof(vis));for(int i=ss;i<=ee;i++){vis[a[i].r]++;vis[a[i].r2+1]--;}int sum=0;for(int i=0;i<n;i++){sum+=vis[i];if(sum%2==1)ans++;}
}
int main()
{freopen("J.in","r",stdin);while(~scanf("%d",&n)){ans=0;int cnt=0;int q;scanf("%d",&q);while(q--){int x,y,p,dir;scanf("%d%d%d%d",&x,&y,&p,&dir);if(dir==0){int temp=p;y--;for(int i=y;i>=y-p+1;i--){if(i<0)break;a[cnt].r=x;a[cnt].c=i;a[cnt].r2=min(x+temp-1,n);cnt++;temp--;}}if(dir==1){int temp=p;for(int i=y;i<=y+p-1;i++){if(i>=n)break;a[cnt].r=x;a[cnt].c=i;a[cnt].r2=min(x+temp-1,n);cnt++;temp--;}}if(dir==3){int temp=p;x--;y--;for(int i=y;i>=y-p+1;i--){if(i<0)break;a[cnt].r=x;a[cnt].c=i;a[cnt].r2=max(x-temp+1,0);cnt++;temp--;}}if(dir==2){int temp=p;x--;for(int i=y;i<=y+p-1;i++){if(i>=n)break;a[cnt].r=x;a[cnt].c=i;a[cnt].r2=max(x-temp+1,0);cnt++;temp--;}}}for(int i=0;i<cnt;i++){if(a[i].r>a[i].r2)swap(a[i].r,a[i].r2);}sort(a,a+cnt,cmp);for(int i=0;i<cnt;i++){int ss=i,ee=i;while(ee+1<cnt&&a[ee].c==a[ee+1].c)ee++;Slove(ss,ee);i=ee;}printf("%d\n",ans);}
}