3
29
2016
0

Diary of March 29th

上午打了场TC
人生第一场TC 只A了两道也能到RANK48……
由于神奇的计分制直接定到了1393 有点开心
Dirak神犇实力爆蛋 T1实力FST 嘿嘿嘿

首先三块不相交肯定能被一条垂直的线或者水平的线分成两块和一块
然后预处理出左上左下右上右下到 $i,j$ 为止拿一个的最大值
然后处理出上面下面左边右边到第 $i$ 行或者 第 $j$ 列为止拿两个的最大值
随便搞一搞了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=1505;
int n,m,k,a[N][N];
int Zs[N][N],Ys[N][N],Zx[N][N],Yx[N][N],Area[N][N];
int S[N],X[N],Z[N],Y[N];
int main(){
	n=IN(),m=IN(),k=IN();
	Rep(i,1,n) Rep(j,1,m)
		a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+IN();
	Rep(i,1,n-k+1) Rep(j,1,m-k+1)
		Area[i][j]=a[i+k-1][j+k-1]-a[i-1][j+k-1]-a[i+k-1][j-1]+a[i-1][j-1];
	Rep(i,k,n) Rep(j,k,m)
		Zs[i][j]=max(max(Zs[i-1][j],Zs[i][j-1]),Area[i-k+1][j-k+1]);
	Rep(i,k,n) Drp(j,m-k+1,1)
		Ys[i][j]=max(max(Ys[i-1][j],Ys[i][j+1]),Area[i-k+1][j]);
	Drp(i,n-k+1,1) Rep(j,k,m)
		Zx[i][j]=max(max(Zx[i+1][j],Zx[i][j-1]),Area[i][j-k+1]);
	Drp(i,n-k+1,1) Drp(j,m-k+1,1)
		Yx[i][j]=max(max(Yx[i+1][j],Yx[i][j+1]),Area[i][j]);
	Rep(i,k,n){
		Rep(j,k,m-k) S[i]=max(S[i],Zs[i][j]+Ys[i][j+1]);
		Rep(j,1,m-k+1) S[i]=max(S[i],Zs[i-k][m]+Area[i-k+1][j]);
	}
	Drp(i,n-k+1,1){
		Rep(j,k,m-k) X[i]=max(X[i],Zx[i][j]+Yx[i][j+1]);
		Rep(j,1,m-k+1) X[i]=max(X[i],Zx[i+k][m]+Area[i][j]);
	}
	Rep(j,k,m){
		Rep(i,k,n-k) Z[j]=max(Z[j],Zs[i][j]+Zx[i+1][j]);
		Rep(i,1,n-k+1) Z[j]=max(Z[j],Zs[n][j-k]+Area[i][j-k+1]);
	}
	Drp(j,m-k+1,1){
		Rep(i,k,n-k) Y[j]=max(Y[j],Ys[i][j]+Yx[i+1][j]);
		Rep(i,1,n-k+1) Y[j]=max(Y[j],Ys[n][j+k]+Area[i][j]);
	}
	int Ans=0;
	Rep(i,k,n-k){
		Ans=max(Ans,S[i]+Zx[i+1][m]);
		Ans=max(Ans,X[i+1]+Zs[i][m]);
	}
	Rep(j,k,m-k){
		Ans=max(Ans,Z[j]+Ys[n][j+1]);
		Ans=max(Ans,Y[j+1]+Zs[n][j]);
	}
	OUT(Ans);
}
好颓啊……做完这题就四点了 ヾ(。`Д´。)
我到底在干啥
先离散然后倍增
$F_{i,j}$ 表示从第 $i$ 个位置出发取 $2^j$ 个线段右端点最靠前的位置+1
$Ans_{i,j}$表示从位置 $i$ 到位置 $j$ 最多能放几个
首先 答案就是$Ans_{1,Js}$ $Js$即离散之后最大的那个位置
然后编号从小到大 考虑这条线段加进去会不会影响答案
即 会不会影响从它向左延伸最大的一段空白到向右延伸最大的一段空白这段的答案
不会的话就加进去
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=200005;
struct Cpn{
	int l,r,id;
}a[N];
map<int,int>Ls;
int n,L[N<<1],Js,Cnt;
int Sx,Pw[20],F[N<<1][20];
bool cmp1(Cpn a,Cpn b){return a.l==b.l?a.r<b.r:a.l<b.l;}
bool cmp2(Cpn a,Cpn b){return a.id<b.id;}
void PreCalc(){
	memset(F,60,sizeof F);
	int j=n;
	for (int i=Js;i>=1;i--){
		F[i][0]=F[i+1][0];
		while (j>0&&a[j].l==i){
			F[i][0]=min(F[i][0],a[j].r+1);
			j--;
		}
	}
	Rep(j,1,Sx) Rep(i,1,Js-Pw[j]+1)
		if (F[i][j-1]<=Js+1) F[i][j]=F[F[i][j-1]][j-1];
}
int GetAns(int l,int r){
	if (l>r) return 0;
	int ret=0;
	Drp(j,Sx,0) if (F[l][j]<=r+1) ret+=Pw[j],l=F[l][j];
	return ret;
}
int Mn[N<<3],Mx[N<<3];
bool Ln[N<<3],Lx[N<<3],Us[N<<3],Lu[N<<3];
void Build(int i,int l,int r){
	if (l==r){Mn[i]=Js,Mx[i]=1,Us[i]=0;return;}
	int mid=l+r>>1;
	Mn[i]=Js,Mx[i]=1,Ln[i]=Lx[i]=0,Us[i]=0;
	Build(i<<1,l,mid),Build(i<<1|1,mid+1,r);
}
void PDUs(int i){
	if (!Lu[i]) return;
	Us[i<<1]=Lu[i<<1]=Us[i<<1|1]=Lu[i<<1|1]=1;
	Lu[i]=0;
}
void Use(int i,int l,int r,int Fr,int Bh){
	if (l==Fr&&r==Bh){Us[i]=Lu[i]=1;return;}
	int mid=l+r>>1;
	PDUs(i);
	if (Bh<=mid) Use(i<<1,l,mid,Fr,Bh);
	else if (Fr>mid) Use(i<<1|1,mid+1,r,Fr,Bh);
	else Use(i<<1,l,mid,Fr,mid),Use(i<<1|1,mid+1,r,mid+1,Bh);
	Us[i]=Us[i<<1]|Us[i<<1|1];
}
bool Find(int i,int l,int r,int Fr,int Bh){
	if (l==Fr&&r==Bh) return Us[i];
	int mid=l+r>>1;
	if (Bh<=mid) return Find(i<<1,l,mid,Fr,Bh);
	else if (Fr>mid) return Find(i<<1|1,mid+1,r,Fr,Bh);
	return Find(i<<1,l,mid,Fr,mid)|Find(i<<1|1,mid+1,r,mid+1,Bh);
}
void PDMn(int i){
	if (!Ln[i]) return;
	if (Mn[i<<1]>Mn[i]) Mn[i<<1]=Mn[i],Ln[i<<1]=1;
	if (Mn[i<<1|1]>Mn[i]) Mn[i<<1|1]=Mn[i],Ln[i<<1|1]=1;
	Ln[i]=0;
}
int QMin(int i,int l,int r,int pos){
	if (l==r) return Mn[i];
	PDMn(i);
	int mid=l+r>>1;
	if (pos<=mid) return QMin(i<<1,l,mid,pos);
		else return QMin(i<<1|1,mid+1,r,pos);
}
void MdfMin(int i,int l,int r,int Fr,int Bh,int v){
	if (l==Fr&&r==Bh){
		if (v<Mn[i]) Mn[i]=v,Ln[i]=1;
		return;
	}
	PDMn(i);
	int mid=l+r>>1;
	if (Bh<=mid) MdfMin(i<<1,l,mid,Fr,Bh,v);
	else if (Fr>mid) MdfMin(i<<1|1,mid+1,r,Fr,Bh,v);
	else MdfMin(i<<1,l,mid,Fr,mid,v),MdfMin(i<<1|1,mid+1,r,mid+1,Bh,v);
}
void PDMx(int i){
	if (!Lx[i]) return;	
	if (Mx[i<<1]<Mx[i]) Mx[i<<1]=Mx[i],Lx[i<<1]=1;
	if (Mx[i<<1|1]<Mx[i]) Mx[i<<1|1]=Mx[i],Lx[i<<1|1]=1;
	Lx[i]=0;
}
int QMax(int i,int l,int r,int pos){
	if (l==r) return Mx[i];
	PDMx(i);
	int mid=l+r>>1;
	if (pos<=mid) return QMax(i<<1,l,mid,pos);
		else return QMax(i<<1|1,mid+1,r,pos);
}
void MdfMax(int i,int l,int r,int Fr,int Bh,int v){
	if (l==Fr&&r==Bh){
		if (v>Mx[i]) Mx[i]=v,Lx[i]=1;
		return;
	}
	PDMx(i);
	int mid=l+r>>1;
	if (Bh<=mid) MdfMax(i<<1,l,mid,Fr,Bh,v);
	else if (Fr>mid) MdfMax(i<<1|1,mid+1,r,Fr,Bh,v);
	else MdfMax(i<<1,l,mid,Fr,mid,v),MdfMax(i<<1|1,mid+1,r,mid+1,Bh,v);
}
int main(){
	n=IN();
	Rep(i,1,n){
		a[i].l=IN(),a[i].r=IN(),a[i].id=i;
		L[++Cnt]=a[i].l,L[++Cnt]=a[i].r;
	}
	
	sort(L+1,L+Cnt+1);
	Ls[L[1]]=Js=1;
	Rep(i,2,Cnt) if (L[i]!=L[i-1]) Ls[L[i]]=++Js;
	Rep(i,1,n) a[i].l=Ls[a[i].l],a[i].r=Ls[a[i].r];
	
	Sx=0;Pw[0]=1;
	while (Pw[Sx]*2<=n) Sx++,Pw[Sx]=Pw[Sx-1]<<1;
	sort(a+1,a+n+1,cmp1);
	PreCalc();
	
	sort(a+1,a+n+1,cmp2);
	int Ans=GetAns(1,Js);
	OUT(Ans),putchar('\n');
	Build(1,1,Js);
	Rep(i,1,n){
		int Lx=QMax(1,1,Js,a[i].l),Rx=QMin(1,1,Js,a[i].r);
		bool Cu=Find(1,1,Js,a[i].l,a[i].r);
		if (Lx>a[i].l || Rx<a[i].r || Cu) continue;
		if (GetAns(Lx,Rx)!=GetAns(Lx,a[i].l-1)+GetAns(a[i].r+1,Rx)+1) continue;
		OUT(i),putchar(' ');
		MdfMax(1,1,Js,a[i].l,Js,a[i].r+1);
		MdfMin(1,1,Js,1,a[i].r,a[i].l-1);
		Use(1,1,Js,a[i].l,a[i].r);
	}
}

 

Category: Diary | Tags: 贪心 倍增 线段树 | Read Count: 190

登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com