具有营销型网站有哪些,免费建立自己喜欢的盒,全国微信公众号100强排行榜,私人wordpress题干#xff1a;
小a正在玩一款即时战略游戏#xff0c;现在他要用航空母舰对敌方阵地进行轰炸 地方阵地可以看做是nmnm的矩形 航空母舰总共会派出qq架飞机。 飞机有两种#xff0c;第一种飞机会轰炸以(xi,yi)(xi,yi)为中心#xff0c;对角线长为lili的正菱形(也就是两条对…题干
小a正在玩一款即时战略游戏现在他要用航空母舰对敌方阵地进行轰炸 地方阵地可以看做是n×mn×m的矩形 航空母舰总共会派出qq架飞机。 飞机有两种第一种飞机会轰炸以(xi,yi)(xi,yi)为中心对角线长为lili的正菱形(也就是两条对角线分别于xx轴 yy轴平行的正方形)而第二种飞机只会轰炸正菱形的上半部分(包括第xixi行) (具体看样例解释) 现在小a想知道所有格子被轰炸次数的异或和 注意不保证被轰炸的格子一定在矩形范围内若越界请忽略
输入描述:
第一行三个整数n,m,qn,m,q分别表示矩阵的长/宽/询问次数
接下来qq行每行四个整数opt,x,y,lopt,x,y,l表示飞机类型轰炸的坐标以及对角线长度
保证ll为奇数
输出描述:
一个整数表示所有格子被轰炸次数的异或和
示例1
输入
复制
4 5 4
1 2 2 1
1 3 3 5
1 3 2 3
2 2 4 3
输出
复制
2
说明 每次的操作矩阵即操作后的矩阵的值如下 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 3 1 1 0 2 2 2 1 1 0 2 1 1 0 0 0 1 1 0 0 3 2 2 1 2 2 2 1 1 0 2 1 1 0 最后把所有元素异或后为2
备注:
1⩽n,m⩽10001⩽n,m⩽10001⩽q⩽5∗1051⩽q⩽5∗105
保证opt1/2,1⩽x,y,l⩽max(N,M)opt1/2,1⩽x,y,l⩽max(N,M)
读入文件过大请使用较快的读入方式 解题报告 这题考查的是对差分数组和前缀和的理解。四个数组分别记录朝着四个方向下放的个数最后求个前缀就代表着这一行中从这个点开始作为起点的轰炸区域个数四个数组分别向着四个方向下放最终得到的四个数组分别是前。可以找个边长为1的操作模拟一下虽然看着别扭但是没啥问题。也就是数组中是差分数组最后查询是前缀和查询。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 3030,ADD 1000;
int a[MAX][MAX],b[MAX][MAX],c[MAX][MAX],d[MAX][MAX];
void up(int x,int y,int l) {a[x-l/2][y],b[x-l/2][y1]--;a[x1][y-l/2-1]--,b[x1][yl/22];
}
void down(int x,int y,int l){c[x1][y-l/21],d[x1][yl/2]--;c[xl/21][y1]--,d[xl/21][y];
}
int main() {int n,m,q;cinnmq;for(int op,x,y,l,i 1; iq; i) {scanf(%d%d%d%d,op,x,y,l);xADD,yADD;if(op 1) up(x,y,l),down(x,y,l);if(op 2) up(x,y,l);}for(int i 1; inADD*2; i) {for(int j 1; jmADD*2; j) {a[i][j] a[i-1][j1];b[i][j] b[i-1][j-1];c[i][j] c[i-1][j-1];d[i][j] d[i-1][j1]; }}int ans 0;for(int i 1; inADD*2; i) {int tmp 0;for(int j 1; jmADD*2; j) {tmp a[i][j] b[i][j] c[i][j] d[i][j];if(iADD1 iADDn jADD1 jADDm) ans ^tmp;}} cout ans endl;return 0 ;
}
