欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu6336 多校第四场E题 Matrix from Arrays

程序员文章站 2022-07-12 09:31:12
...

首先打表找出规律,它是以边长为2*n的正方形为一个周期向下和后扩散的,所以将周期的下标存到二维数组中,然后对于每个询问,求出完整周期有多少个,然后不完整的单独算即可。solve函数求的是(0,0)到(x,y)的和.

所以结果就是:

solve(x2,y2)-solve(x2,y1-1)-solve(x1-1,y2)+solve(x1-1,y1-1);

 

#pragma GCC optimize(2)
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#include<time.h>
#include <iomanip>
#define lowbit(x) (x&(-x))
#define inf  0x7fffffff
#define linf 0x7fffffffffffffff
#define mem(x,y) memset(x,y,sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);i++)
#define fdn(i,x,y) for(int i=(x);i>=(y);i--)
#define sp(x) setprecision(x)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define sc(n) scanf("%s",n)
#define pf(x) printf("%d\n",x)
#define pfl(x) printf("%lld\n",x)
#define pff(x) printf("%lf\n",x)
#define debug printf("!!\n");
#define N 100005
#define M 4000009
#define pi acos(-1)
#define eps 1e-2
//cout.setf(ios::fixed);
//freopen("out.txt","w",stdout);// freopen("in.txt","r",stdin);
using namespace std;
typedef long long  ll;
typedef long long  LL;
typedef double db;
int a[135][135],b[15],m,n;
int ini()
{
    int cursor = 0;
    for (int i = 0; i<=100; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            a[j][i - j] = cursor+1;
            cursor = (cursor + 1) % n;
        }
    }
}
ll solve(ll x,ll y)
{
    if(x<0||y<0) return 0;
    ll ans=0;
    m=2*n;
    ll cnt=((x+1)/m)*((y+1)/m);

    if(cnt)
    {
       fup(i,0,2*n-1)
            fup(j,0,2*n-1)
                ans+=b[a[i][j]];
        ans*=cnt;
    }
    else
    {
        if((x+1)/m)
        {
            fup(i,0,2*n-1)
                fup(j,0,(y+1)%m-1)
                    ans+=b[a[i][j]];
            ans*=((x+1)/m);
            fup(i,0,(x+1)%m-1)
                fup(j,0,(y+1)%m-1)
                    ans+=b[a[i][j]];
        }
        else if((y+1)/m)
        {
            fup(i,0,(x+1)%m-1)
                fup(j,0,2*n-1)
                    ans+=b[a[i][j]];
            ans*=((y+1)/m);
            fup(i,0,(x+1)%m-1)
                fup(j,0,(y+1)%m-1)
                    ans+=b[a[i][j]];
        }
        else
        {
            fup(i,0,x)
                fup(j,0,y)
                    ans+=b[a[i][j]];
        }
        return ans;
    }
    ll sum1=0;
    fup(i,0,(x+1)%m-1)
        fup(j,0,2*n-1)
            sum1+=b[a[i][j]];
    ans+=(sum1*((y+1)/m));

    sum1=0;

    fup(i,0,2*n-1)
        fup(j,0,(y+1)%m-1)
            sum1+=b[a[i][j]];
    ans+=(sum1*((x+1)/m));

    fup(i,0,(x+1)%m-1)
        fup(j,0,(y+1)%m-1)
            ans+=b[a[i][j]];

    return ans;

}
int main()
{
    int t;
    sd(t);
    while(t--)
    {
        sd(n);
        fup(i,1,n)
            sd(b[i]);
        int q;
        ini();
        sd(q);
        while(q--)
        {
            int x1,x2,y1,y2;
            sdd(x1,y1);
            sdd(x2,y2);
            ll ans=solve(x2,y2)-solve(x2,y1-1)-solve(x1-1,y2)+solve(x1-1,y1-1);
            pfl(ans);
        }
    }
}

 

相关标签: 打表 多校