HDU 6336 Problem E. Matrix from Arrays（找规律）

Problem E. Matrix from Arrays

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 530    Accepted Submission(s): 229

 

Problem Description

Kazari has an array A length of L, she plans to generate an infinite matrix M using A.
The procedure is given below in C/C++:

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;
    }
}

Her friends don't believe that she has the ability to generate such a huge matrix, so they come up with a lot of queries about M, each of which focus the sum over some sub matrix. Kazari hates to spend time on these boring queries. She asks you, an excellent coder, to help her solve these queries.

 

 

Input

The first line of the input contains an integer T (1≤T≤100) denoting the number of test cases.
Each test case starts with an integer L (1≤L≤10) denoting the length of A.
The second line contains L integers A0,A1,...,AL−1 (1≤Ai≤100).
The third line contains an integer Q (1≤Q≤100) denoting the number of queries.
Each of next Q lines consists of four integers x0,y0,x1,y1 (0≤x0≤x1≤108,0≤y0≤y1≤108) querying the sum over the sub matrix whose upper-leftmost cell is (x0,y0) and lower-rightest cell is (x1,y1).

 

 

Output

For each test case, print an integer representing the sum over the specific sub matrix for each query.

 

 

Sample Input

1 3 1 10 100 5 3 3 3 3 2 3 3 3 2 3 5 8 5 1 10 10 9 99 999 1000

 

 

Sample Output

1 101 1068 2238 33076541

题意：给你一个长度为l的a数组，然后按题目所给代码构造m矩阵，q次询问，每次查询给出左上角(l,r)和右下角(ll,rr)，求m数组中这个矩形里所有数的和。

思路：当然是先按题目中那样打表出来。然后发现l是偶数周期为2*l，奇数周期为l。于是用周期2*l。

然后就可以考虑和二维树状数组一样的求法了。

m数组求出二维前缀和，然后对查询(x,y,xx,yy)就计算sum(xx,yy)-sum(x-1,yy)-sum(xx,y-1)+sum(x-1,y-1)就行了。

这道题给我的启示：

遇到这种找规律的题，一定要打一个大一点的表。比赛的时候我只打了2*l的表，导致没看出来周期就是2*l

如果题目中给你了代码，尽量复制下来再改变量名或者不改，自己手动敲错一点就完了。

在其他难题毫无头绪的时候，应该直接放弃开这道题，因为规律题一旦找到规律就能迎刃而解，相对难题而言应该先做这道题。

千万不要盲目跟榜。歪榜是正常现象，要尽量把所有题目都读完！！！

注意两个整数相除，向下取整要加括号。(x/l)*(y/l)

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2100;
ll a[maxn],m[maxn][maxn];
ll l,ans,tmp,n,q,x,y,xx,yy;
ll cal(ll x,ll y)
{
    if(x<0||y<0) return 0;
    return (x/l)*(y/l)*m[l-1][l-1]+(x/l)*m[l-1][y%l]+(y/l)*m[x%l][l-1]+m[x%l][y%l];
}
int main()
{
    int T,f;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&l);f=0;
        for(int i=0;i<l;i++) scanf("%lld",&a[i]);
        for(int i=0;i<=4*l;i++)
        for(int j=0;j<=i;j++)
        {
            m[j][i-j]=a[f++];
            f%=l;
        }
        /*
        for(int i=0;i<2*l;i++,puts(""))
        for(int j=0;j<2*l;j++)
        {
            cout<<m[i][j]<<'\t';
        }
        */
        for(int i=0;i<2*l;i++)
        for(int j=0;j<2*l;j++)
        {
            if(i) m[i][j]+=m[i-1][j];
            if(j) m[i][j]+=m[i][j-1];
            if(i&&j) m[i][j]-=m[i-1][j-1];
        }
        l*=2;
        //cout<<m[l-1][l-1]<<endl;
        scanf("%lld",&q);
        while(q--)
        {
            scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy);
            ans=cal(xx,yy)-cal(x-1,yy)-cal(xx,y-1)+cal(x-1,y-1);
            printf("%lld\n",ans);
        }
    }
}