3
29
2016
2

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: 632
Grade 8 Result jesso 说:
Aug 28, 2022 03:32:22 PM

Jessore Divisional education board of Bangladesh has successfully conducted the Grade 8th terminal examination tests for both Junior School Certificate & Junior Dakhil Certificate course students at all districts under the division to the academic year of 2022, there are a huge number of students are appeared from all Secondary schools under the board like as previous years, Grade 8 Result jessore and this is most important examination tests for class 8th standard students of the country.Government of Bangladesh, Secondary and Higher Secondary Education Board has successfully completed the JSC & JDC examinations in the month of November 2022 to all eligible students of the division at all selected examination centers at all rural and urban area schools, both of Junior School Certificate & Junior Dakhil Certificate terminal exams are conducted as per date sheet announced by all education board Bangladesh.

pavzi.com 说:
Apr 16, 2023 06:44:44 PM

We provide you with the finest web content on each and every topic possible with help of the editorial and content team.Pavzi Post is a startup by passionate webmasters and bloggers who have a passion to provide engaging content which is accurate, interesting and worthy to read. We are more like a web community where you can pavzi.com find different information, resources, and topics on day-to-day incidents or news.


登录 *


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