[ 2018 Multi-University Training Contest 4 ] [ HDU6333 ] Harvest of Apples

[ 2018 Multi-University Training Contest 4 ] [ HDU6336 ] E Matrix from Arrays

Zarxdy34 posted @ 2018年8月01日 21:28 in HDU with tags 容斥 周期函数 , 53 阅读

        题目大意:给出一个长度为L的数组\(A[0..L-1]\),用下面的方法来构造出一个无限大的矩阵:

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

        给出Q个询问\( ( Q \leq 100 ) \),求左上角为\(x_0,y_0\),右下角为\(x_1,y_1\)的子矩阵内的元素和。\( 1 \leq L \leq 10 , 0 \leq x_0 , y_0 , x_1 , y_1 \leq 10^8 \)。

        题解:首先可以先把\(M[i][j]\)的表达式写出来:\(M[i][j] = A[ (C_{i+j+1}^2 + i) % L]\),利用该式可以得到\(M[i][j] = M[i+2L][j] = M[i][j+2L]\),然后就可以很轻松地解决掉此题了。

        考场上没有发现这个性质,只是知道会存在循环节,且循环节长度不大于\(L^2\),利用这个性质来进行计算。另外由于最多只有L个不同的数,可以统计出每个数出现的次数再计算。

        对于图中的任意一个子矩阵,可以由四个以\( (0,0) \)为左上角顶点的矩阵容斥得到。然后要计算的是以\( (0,0) \)为左上角的矩阵内元素和,这个再容斥求。

        矩阵可以用两个直角梯形减去一个大三角形,直角梯形可以用以左上角为\( (0,0) \)的等腰直角三角形与一个平行四边形相加而成,平行四边形的底上的数字是有周期的,然后高又是固定的,可以在\( O(L^2) \)的时间内预处理出来。

        所以浪费了很多时间来搞这个东西...脑子都搞糊了...

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=10;

long long C2(int X) {return (long long)X*(X-1)/2;}

long long c[maxn];
int A[maxn];
int L,Q;

void Calc_Triangle(int X,int sgn)
{
	for (int i=0;i<L;i++) c[i]+=((C2(X)+L-i-1)/L)*sgn;
}

long long POS(int X,int Y) {return C2(X+Y+1)+X;}
int POSL(int X,int Y) {return POS(X,Y)%L;}

void Calc_Rectangle(int X0,int Y0,int DX,int DY,int Len,int Time)
{
	int c0[maxn];
	int c1[maxn][maxn];
	int vis[maxn][maxn];
	memset(c0,0,sizeof(c0));
	memset(c1,0,sizeof(c1));
	memset(vis,0,sizeof(vis));
	for (int i=0;i<L;i++)
	for (int j=0;j<L;j++)
		c1[i][j]=(Len+j+L-i-1)/L-(i<j?1:0);
	int cnt=0;
	while (1)
	{
		int PA=POSL(X0,Y0),PB=POSL(X0+DX,Y0+DY);
		if (vis[PA][PB]) break;
		vis[PA][PB]=++cnt;
		for (int i=0;i<L;i++) c0[i]+=c1[i][PA];
		X0+=DX,Y0+=DY;
	}
	long long K=Time/cnt;
	Time%=cnt;
	for (int i=0;i<L;i++) c[i]+=c0[i]*K;
	while (Time--)
	{
		int P=POSL(X0,Y0);
		for (int i=0;i<L;i++) c[i]+=c1[i][P];
		X0+=DX,Y0+=DY;
	}
	return;
}

long long Query(int X,int Y)
{
	if (X==-1 || Y==-1) return 0;
	memset(c,0,sizeof(c));
	Calc_Triangle(X+2,1);
	Calc_Triangle(Y+2,1);
	Calc_Triangle(X+Y+2,-1);

	Calc_Rectangle(0,X+1,0,1,X+1,Y);
	Calc_Rectangle(1,Y,1,0,Y+1,X);

	long long res=0;
	for (int i=0;i<L;i++) res+=c[i]*A[i];
	return res;
}

int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&L);
		for (int i=0;i<L;i++) scanf("%d",&A[i]);
		scanf("%d",&Q);
		while (Q--)
		{
			int X0,Y0,X1,Y1;
			scanf("%d%d%d%d",&X0,&Y0,&X1,&Y1);
			printf("%lld\n",Query(X1,Y1)-Query(X0-1,Y1)-Query(X1,Y0-1)+Query(X0-1,Y0-1));
		}
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter