【6336 HDU】Matrix from Arrays（矩阵找规律）

素颜马尾好姑娘i 2022-05-17 12:46 163阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6336][http_acm.hdu.edu.cn_showproblem.php_pid_6336]

题意：输入T组测试样例，然后给你L个数用下面的代码生成一个无限矩阵，然后输入q次询问，每次询问给你2个点（x0，y0），（x1，y1），求这2个点之间组成的矩阵和。

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

思路：如果暴力的话，肯定会超时，所以这道题有技巧。首先，这个无限矩阵是有规律的，当L是奇数时，它是以L\*L循环的；当L是偶数时，它是以2L\*2L循环的，如图1。

然后就是如果我们直接求点（x0，y0）到（x1，y1）点组成的矩阵和S的话，会比较难算，我们可以将其转换成求（0，0）点到（x1，y1）点组成的矩阵和S1-（0，0）点到（x1，y0-1）点组成的矩阵和S2-（0，0）点到（x0-1，y1）点组成的矩阵和S3+（0，0）点到（x0-1，y0-1）点组成的矩阵和S4，即S=S1-S2-S3+S4，如图2。

这样就简单多了，我们只用写一个函数用来求（0，0）点到（x，y）点组成的矩阵和就可以喽。

（这道题还有一个注意点儿是这道题中的矩阵的点是从（0,0）开始的，也就是说如果它给了你一个点是（2,3）代表的是矩阵里的第3行第4列的数而不是第2行第3列的数，我就wa在这个坑里，还在坑里呆了好久Ծ‸Ծ）

![70][]

![70 1][]

My DaiMa：

#include <iostream>
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int n,a[55][55];
    ll Count(int x,int y)//即求（0,0）点到（x，y）点组成的矩阵和
    {
        ll s1(0),s2(0),s3(0),s4(0);
        int N = 2*n;
        for(int i = 0; i < N; i++)//计算这个大矩阵中完整矩阵的矩阵和
        {
            for(int j = 0; j < N; j++)
                s1 += a[i][j];
        }
        s1 = s1*((x+1)/N)*((y+1)/N);
        for(int i = 0; i < (x+1)%N; i++)//计算跟完整矩阵同宽的零碎矩阵和
        {
            for(int j = 0; j < N; j++)
                s2 += a[i][j];
        }
        s2 = s2*((y+1)/N);
        for(int i = 0; i < N; i ++)//计算跟完整矩阵同长的零碎矩阵和
        {
            for(int j = 0; j < (y+1)%N; j++)
                s3 += a[i][j];
        }
        s3 = s3*((x+1)/N);
        for(int i = 0; i< (x+1)%N; i++)//计算剩下来的右下角的一小块儿矩阵和
        {
            for(int j = 0; j < (y+1)%N; j++)
                s4 += a[i][ j];
        }
        //printf("%lld\n",s1+s2+s3+s4);
        return s1+s2+s3+s4;
    }
    int main()
    {
        int t,b[15],q,x0,y0,x1,y1;
        cin >> t;
        while( t-- )
        {
            scanf("%d",&n);
            for(int i = 0;i < n; i++)
                scanf("%d",&b[i]);
            int cunt = 0;
            for(int i = 0;i < 5*n; i++)//只用生成一个5*n的矩阵即可
            {
                for(int j = 0; j<= i; j++)
                {
                    a[j][i-j] = b[cunt];
                    cunt = (cunt+1)%n;
                }
            }
            scanf("%d",&q);//输入询问次数
            while( q-- )
            {
                scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
                printf("%lld\n",Count(x1,y1)+Count(x0-1,y0-1)-Count(x0-1,y1)-Count(x1,y0-1));
            }
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6336]: http://acm.hdu.edu.cn/showproblem.php?pid=6336
[70]: /images/20220517/ca7e35c1cf8d4be9a289b399a6120599.png
[70 1]: /images/20220517/e8fce5c4ace14b16ac9c50904ee76672.png