海南住房与城乡建设网站电商网站开发案例

海南住房与城乡建设网站,电商网站开发案例,新浪云 安装wordpress,专业网页设计工具原题 题目描述 有一个 10^9 乘 10^9的方格网格。让 (i,j)表示从上往下数第 (i1)行、从左往右数第 (j1) 列的方格 每个方格要么是黑色要么是白色。方格 (i,j)的颜色由字符 P[i mod N][j mod N]表示#xff0c;其中 B 表示黑色#xff0c;W 表示白色。这里,a mod b表…原题题目描述有一个 10^9 乘 10^9的方格网格。让 (i,j)表示从上往下数第 (i1)行、从左往右数第 (j1) 列的方格每个方格要么是黑色要么是白色。方格 (i,j)的颜色由字符 P[i mod N][j mod N]表示其中B表示黑色W表示白色。这里,a mod b表示a除以b的余数。回答 Q个查询。每个查询给出四个整数 A,B,C,D要求你找出以 (A,B)为左上角、(C,D)为右下角的矩形区域内包含的黑色方格数量。题目思路令f(x,y)为满足条件的黑色方格的个数,则所求的答案就是f(c1,d1)-f(a,d1)-f(c1,b)f(a,b)。但是如直接计算肯定比较麻烦可以利用他的一些性质。当x8,y7时如右图所示可以将其分解为A*(x/n)*(y/n)、B*(y/n)、C*(x/n),D。其中Af(n,n),Bf(x%nn),Cf(y%n,n),Df(x%n,y%n)。即可以将其分解为f(n,n)*(x/n)*(y/n) (y/n)*f(x%n,n) (x/n)*f(n,y%n) f(x%n,y%n)。最后f(1,1)~f(n,n)可以使用前缀和的方式快速求出。#includebits/stdc.h using namespace std; using LLlong long;//给long long去个别名LL const int N1010; int n,q,h[N][N]; LL f(LL x,LL y){ if(xnyn){ return h[x][y]; } return f(n,n)*(x/n)*(y/n)(x/n)*f(n,y%n)(y/n)*f(x%n,n)f(x%n,y%n); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinnq; for(int i1;in;i){ for(int j1;jn;j){ char c; cinc; h[i][j](cB)h[i-1][j]h[i][j-1]-h[i-1][j-1]; } } //前缀和优化↑ while(q--){//处理q次查询 int a,b,c,d; cinabcd; c; d; coutf(c,d)-f(a,d)-f(c,b)f(a,b)\n; } return 0; }