csp

开考建好文件夹编译器不能用搞了半天换了台电脑

四道题看完一个小时过去了

第一题不会正解写了部分分还有点悬

第二题写暴力因为一个小错误调了半天

看时间不多了已经有点慌了

也没想正解直接开了下一题

从T3 T4选了T4写了部分分还写挂了

没有稳定好心态

和平常考试的感觉差了很多

T2

[CSP-S 2022] 假期计划

考场上没想正解用ST表写了个暴力痛失40分

考完一个小时就写出正解

我是大SB-_-

正解：

根据\(A,B\)正负性分情况讨论

线段树维护信息

当 \(B\)全为正时 \(ans = A_{max}*B_{min}\)
当 \(B\)全为负时 \(ans = A_{min}*B_{max}\)
当 \(B\)有正有负时
1. 当 \(A\)全为正时 \(ans = A_{min}*B_{min}\)
2. 当 \(A\)全为负时 \(ans = A_{max}*B_{max}\)
3. 当 \(A\)有正有负时 \(ans\)必定为负(先手选正后手必选负、先手选负后手必选正)
  1. 当A选正时 B会选最小的负使\(ans\)最小 A应选正最小使\(ans\)尽量大即\(ans = A_{正min} * B_{min}\)
  2. 当A选负时 B会选最大的正使\(ans\)最小 A应选负最大使\(ans\)尽量大即\(ans = A_{负max} * B_{max}\)

所以需要用线段树维护\(A_{max}\) \(A_{min}\) \(B_{max}\) \(B_{min}\) \(A_{正min}\) \(A_{负max}\)

std:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define ls p<<1

#define rs p<<1|1

const int N = 1e5+9;

int n,m,q,a[N],b[N];

struct tree

{

	int l,r;

	int mxA,mxB,miA,miB,zmiA,fmxA;

	tree()

	{

		l=r=0;

		miA=miB=zmiA=1e9+1;

		mxA=mxB=fmxA=-1e9-1;

	}

	#define l(x) t[x].l

	#define r(x) t[x].r

	#define mxA(x) t[x].mxA

	#define mxB(x) t[x].mxB

	#define miA(x) t[x].miA

	#define miB(x) t[x].miB

	#define zmiA(x) t[x].zmiA

	#define fmxA(x) t[x].fmxA

}t[N<<2];

tree operator +(const tree &l,const tree &r)

{

	tree p;

	p.l = l.l;

	p.r = r.r;

	p.mxA = max(l.mxA,r.mxA);

	p.mxB = max(l.mxB,r.mxB);

	p.miA = min(l.miA,r.miA);

	p.miB = min(l.miB,r.miB);

	p.zmiA = min(l.zmiA,r.zmiA);

	p.fmxA = max(l.fmxA,r.fmxA);

	return p;

}

void pushup(int p)

{

	t[p] = t[ls] + t[rs];

}

void build(int p,int l,int r)

{

	if(l == r)

	{

		l(p) = r(p) = l;

		miA(p)=mxA(p)=a[l];

		miB(p)=mxB(p)=b[l];

		if(a[l] > 0)zmiA(p)=a[l];

		else if(a[l] < 0)fmxA(p) = a[l];

		else zmiA(p) = fmxA(p) = a[l];

		return;

	}

	int mid = (l + r)>>1;

	build(ls,l,mid);

	build(rs,mid+1,r);

	pushup(p);

}

tree query(int p,int l,int r)

{

	if(l <= l(p) && r >= r(p))return t[p];

	int mid = (l(p)+r(p))>>1;

	if(r <= mid)return query(ls,l,r);

	else if(l > mid)return query(rs,l,r);

	else return query(ls,l,r)+query(rs,l,r);

} 

int main()

{

//	freopen("game.in","r",stdin);

//	freopen("game.out","w",stdout);

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= n;i++)scanf("%d",&a[i]);

	for(int i = 1;i <= m;i++)scanf("%d",&b[i]);

	build(1,1,max(n,m));

	while(q--)

	{

		int l1,r1,l2,r2;

		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

		tree A = query(1,l1,r1);

		tree B = query(1,l2,r2);

		if(B.miB >= 0)printf("%lld\n",1ll*A.mxA*B.miB);

		else if(B.mxB < 0)printf("%lld\n",1ll*A.miA*B.mxB);

		else if(A.miA >= 0)printf("%lld\n",1ll*A.miA*B.miB);

		else if(A.mxA < 0)printf("%lld\n",1ll*A.mxA*B.mxB);

		else printf("%lld\n",max(1ll*A.zmiA*B.miB,1ll*A.fmxA*B.mxB));

	}

	return 0;

}

巴特西

CSP 记

csp

T2

std:

最新文章

热门文章