杭电多校04补题 HDU6336 Problem E. Matrix from Arrays【构造】

地址：http://acm.hdu.edu.cn/showproblem.php?pid=6336

题意：按照要求构造一个很大的矩阵，给你这个矩阵中任意两点，求这两点为左上右下两角所构成的矩阵中每个元素的和

思路：
        （开始找了半天斜边的规律，写了一发错误代码（下面也放出来了），后来想想规律倒是没错，就是这样一个个加矩阵中

最后元素，肯定会超时。）

        最后是打表发现规律，L为奇数时候是L*L的小方格循环构成的一个大矩阵，偶数时候是2*L*2*L的小方格循环构成的，不仿都看成2*L一循环。
        因为L不大可以先造一个2*L的数组M[2*L][2*L]，然后循环求这个数组中每个位置的前缀和，dp公式为：sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+M[i][j];
        之后用Sum（int x，int y）来计算每个（0,0）----（x，y） 的矩阵中各元素的和
        最后对于随意给的两点（x1,y1),(x2,y2)，其构成的矩阵中各元素的和为四个矩阵相加减（容斥定理）
        即：res=Sum(x2,y2)-Sum(x1-1,y2)-Sum(x2,y1-1)+Sum(x1-1,y1-1);
        ps：为了方便我们可以从an[1][1]开始输入，注意对细节的处理即可 

代码：

超时代码：（tle）：

#include <bits/stdc++.h>
#define ll long long 
#define N 15
using namespace std;
int an[N];
int main()
{
    int t,n,q;
    ll x1,y1,x2,y2;
    ll sum=0;
    cin>>t;
    while(t--)
    {
        
        cin>>n;
        for(int i=0;i<n;++i)
        {
            cin>>an[i];
        }
        cin>>q;
        for(int i=0;i<q;++i)
        {
            sum=0;
            cin>>x1>>y1>>x2>>y2;
            for(int i=x1;i<=x2;++i)
            {
                for(int j=y1;j<=y2;++j)
                {
                    sum+=an[((i+j+1)*(i+j)/2+i+1-1)%n];
                }
            }
            cout<<sum<<endl;
        }
    }
    return 0;
}

AC代码：（注意子函数中的Sum要用2*L来计算，开始用的是L，忘记构造的是2*L的矩阵了，wa了一发）

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 25
ll an[15];
ll M[105][105];
ll sum[N][N];
ll L;

ll Sum(ll x,ll y)
{
	ll num=0,len=2*L;
	
	num+=sum[len][len]*(x/len)*(y/len);
	num+=sum[x%len][len]*(y/len)+sum[len][y%len]*(x/len);
	num+=sum[x%len][y%len];
	return num;
} 
int main()
{
	ll t,q;
	ll x1,y1,x2,y2;
	ll res=0;
	cin>>t;
	while(t--)
	{
		
		cin>>L;
		for(ll i=0;i<L;++i)
		{
			cin>>an[i];
		}
		//储存2*L的数组
		ll cursor=0;
		for (ll i = 0;i<=100; ++i) 
		{
		    for (ll j = 0; j <= i; ++j) { 
		        M[j+1][i - j+1] = an[cursor];
		        cursor = (cursor + 1) % L;
		    }
		}
		//cout<<"1"<<endl;
		/*for(int i=1;i<=2*L;++i)
		{
			for(int j=1;j<=2*L;++j)
				cout<<M[i][j];
			cout<<endl;
		}*/
		//储存2*L-2*L数组的前缀和 
		memset(sum,0,sizeof(sum));
		for(ll i=1;i<=2*L;++i)
		{
			for(ll j=1;j<=2*L;++j)
			{
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+M[i][j];
				//cout<<sum[i][j]<<endl;
			}
		}
		//cout<<"2"<<endl;
		cin>>q;
		for(ll i=0;i<q;++i)
		{
			cin>>x1>>y1>>x2>>y2;
			//这里要加1，因为给的x,y坐标还是以（0,0）矩阵为原点考虑的
			x1++;y1++;y2++;x2++; 
			res=Sum(x2,y2)-Sum(x1-1,y2)-Sum(x2,y1-1)+Sum(x1-1,y1-1);
			cout<<res<<endl;
		}
		
		/*int n=8;
		for(int i=0;i<n;++i)
		{
			for(int j=0;j<n;++j)
			{
				cout<<M[i][j];
			}
			cout<<endl;
		}*/
	}
	return 0;
}