AI编程社区

题目

给出长度为n 的A矩阵 ， 按

int cursor = 0;

for (int i = 0; ; ++i) {    for (int j = 0; j <= i; ++j) {         M[j][i - j] = A[cursor];        cursor = (cursor + 1) % L;    }}构造出无限矩阵M ， 然后给出l1 , r1 , l2, r2 ; 查询以(l1,r1)左上角  (l2,r2)右上角 的矩阵和题意：用上面的转化规则十分容易的想到可能是有什么规律 ， 所以我们打了个表出来发现 ， n为奇数是相同矩阵的周期为n , n为偶数相同矩阵的周期为2*n ; 然后。。。。没有想到二维矩阵的前缀和，。。所以一直打不出来；。。我们先看一个图 ，如果对二维矩阵前缀和敏感这题目就是直接秒杀的事情复制

 

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
 
ll a[50];
ll map[50][50];
int L;
 
void init(){
    memset(map,0,sizeof map);
    int cursor=0;
    for (int i = 0;i<L*4; ++i) {
        for (int j = 0; j <= i; ++j) {
            map[j][i-j] = a[cursor];
            cursor=(cursor+1)%(L);
        }
    }
    for(int i=0;i<2*L;i++){
        for(int j=0;j<2*L;j++){
            if((i>0)&&(j>0))map[i][j]+=map[i-1][j]+map[i][j-1]-map[i-1][j-1];
            if((i>0)&&(j==0))map[i][j]+=map[i-1][j];
            if((i==0)&&(j>0))map[i][j]+=map[i][j-1];
        }
    }
}
ll f(int x,int y){
    if(x<0||y<0)return 0;
    ll ans=0;
    ll xx=x/L;//这里不用long long就会wa 
    ll yy=y/L;
    ll sx=x%L;
    ll sy=y%L;
    ans+=xx*yy*map[L-1][L-1];
    ans+=yy*map[sx][L-1];
    ans+=xx*map[L-1][sy];
    ans+=map[sx][sy];
    return ans;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&L);
        for(int i=0;i<L;i++){
            scanf("%lld",&a[i]);
        }
        init();
        int q;
        scanf("%d",&q);
        L=L*2;
        while(q--){
            int x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            printf("%lld\n",f(x2,y2)-f(x2,y1-1)-f(x1-1,y2)+f(x1-1,y1-1));
        }
    }
    return 0;
}复制

 

复制