APIO2014/Practice Session

Posted on By 二价氢

#总结

这三题代码量都能控制在80行以内2333

题解应该到下一个屏幕了吧……

#题目描述

##Task 1 DIVIDE-AND-CONQUER

英文题面

坐标轴上个点,每个点的坐标为,有两个属性,

选定一个区间使得

最大化

##Task 2 LUXURY-BURROW

英文题面

圈定一个子矩阵,面积最小为,最大化子矩阵元素最小值

##Task 3 TRADING

英文题面

平面上若干条斜率为1的线段,横坐标从到$R_ix=L_iy$$的值,求每个点最上方的线段

#做法

##Task 1

由暴力的公式可以知道:一个区间可以被选的充分条件是,推得

我们用线段树维护的最大的的值

然后对于每个,找到满足的最小的

总时间复杂度

##Task 2

二分答案,通过的最大子矩阵DP判定答案合法性

##Task 3

根据题目知道,线段的斜率都为1,那么延长线段,直线交轴的纵坐标的值就能代替函数的值

用线段树维护这个值即可

P.S. ZKW线段树特别方便

#AC Code

##Task 1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;
const int maxn=100005,maxm=131072;
long long x[maxn],g[maxn],d[maxn];
int pos[262150],ipos[262150];
pair<long long,int> segv[maxn];
int seg[262150];
long long val[maxn];
int n;
int qmax(int l,int r)
{
	int ans=0;
	l=l+maxm-1;r=r+maxm+1;
	while (l^r^1)
	{
		if (~l&1) ans=max(ans,seg[l+1]);
		if ( r&1) ans=max(ans,seg[r-1]);
		l>>=1;r>>=1;
	}
	return ans;
}
int main()
{
#ifdef EVAL
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
#endif
	int apos=0,aapos;
	long long ans=0;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&x[i],&g[i],&d[i]);
		g[i]+=g[i-1];
		d[i]+=d[i-1];
		val[i]=d[i]-x[i];
		segv[i]=make_pair(d[i]-x[i],i);
	}
	sort(&val[1],&val[n+1]);
	sort(&segv[1],&segv[n+1]);
	for (int i=1;i<=n;i++)
	{
		pos[segv[i].second]=i,seg[i+maxm]=segv[i].second;
	}
	for (int i=maxm;i>=1;i--)
		seg[i]=max(seg[i*2],seg[i*2+1]);
	for (int i=1;i<=n;i++)
	{
		aapos=lower_bound(&val[1],&val[n+1],d[i-1]-x[i])-&val[0];
		apos=qmax(aapos,n);
		ans=max(ans,g[apos]-g[i-1]);
	}
	printf("%lld\n",ans);
	return 0;
}

##Task 2

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1005;
int Map[maxn][maxn],val[maxn][maxn],h[maxn][maxn],la[maxn][maxn],ra[maxn][maxn];
int sta[maxn],tp;
int m,n,k;
int i,j;
int vmax=0;
int dp()
{
	int ans=0,lo,ro;
	//--
	memset(h,0,sizeof(h));
	for (i=1;i<=n;i++)
	{
		lo=0;ro=m+1;
		for (j=1;j<=m;j++)
		{
			if (!Map[i][j])
				h[i][j]=la[i][j]=0,lo=j;
			else
			{
				h[i][j]=(i==1)?1:h[i-1][j]+1;
				la[i][j]=(i==1)?lo+1:max(la[i-1][j],lo+1);
			}
		}
		for (j=m;j>=1;j--)
		{
			if (!Map[i][j])
				ra[i][j]=n+1,ro=j;
			else
			{
				ra[i][j]=(i==1)?(ro-1):min(ra[i-1][j],ro-1);
				ans=max(ans,h[i][j]*(ra[i][j]-la[i][j]+1));
			}
		}
	}
	return ans;
}
void erfen()
{
	int l=0,r=vmax+1,mid,ans,rans=0;
	while (l<r-1)
	{
		mid=(l+r)/2;
		for (i=1;i<=n;i++)
			for (j=1;j<=m;j++)
				Map[i][j]=(val[i][j]>=mid);
		if (dp()>=k)
			l=mid;
		else
			r=mid-1;
	}
	for (mid=l+2;mid>=l;mid--)
	{
		for (i=1;i<=n;i++)
			for (j=1;j<=m;j++)
				Map[i][j]=(val[i][j]>=mid);
		if ((ans=dp())>=k)
			break;
	}
	printf("%d %d\n",mid,ans);
}
int main()
{
#ifdef EVAL
	freopen("burrow.in","r",stdin);
	freopen("burrow.out","w",stdout);
#endif
	scanf("%d%d%d",&n,&m,&k);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			scanf("%d",&val[i][j]),vmax=max(vmax,val[i][j]);
	erfen();
	return 0;
}

##Task 3

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=300005,maxm=524288;
int n,m;
int seg[1048580];
void edit(int l,int r,int v)
{
	l=l+maxm-1;r=r+maxm+1;
	while (l^r^1)
	{
		if (~l&1) seg[l+1]=max(seg[l+1],v);
		if ( r&1) seg[r-1]=max(seg[r-1],v);
		l>>=1;r>>=1;
	}
}
int query(int x)
{
	int ans(0x80808080);
	x=x+maxm;
	while (x)
	{
		ans=max(ans,seg[x]);
		x>>=1;
	}
	return ans;
}
int main()
{
	int li,ri,xi;
#ifdef EVAL
	freopen("trading.in","r",stdin);
	freopen("trading.out","w",stdout);
#endif
	memset(seg,0x80,sizeof(seg));
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&li,&ri,&xi);
		edit(li,ri,xi-li);
	}
	for (int i=1;i<=n;i++)
	{
		xi=query(i);
		printf("%d ",(xi==int(0x80808080))?0:xi+i);
	}
	printf("\n");
	return 0;
}