技术教程 编程教程 2021.9.22考试总结[NOIP模拟59] 正文

2021.9.22考试总结[NOIP模拟59]

2023-05-13,,

T1 柱状图

关于每个点可以作出两条斜率绝对值为\(1\)的直线。

将绝对值拆开，对在\(i\)左边的点\(j\)，\(h_i-i=h_j-j\)，右边则是把减号换成加号。

把每个点位置为横坐标，高度与位置的差或和为纵坐标扔到坐标系里，发现每条直线上下点数最接近时代价最小。

对每个点二分即可。

T1 

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

namespace IO{

	inline int read(){

		char ch=getchar(); int x=0,f=1;

		while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

		while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

		return x*f;

	}

	inline void write(LL x,char sp){

		char ch[20]; int len=0;

		if(x<0){ putchar('-'); x=~x+1; }

		do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);

		for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);

	}

	inline int max(int x,int y){ return x<y?y:x; }

	inline int min(int x,int y){ return x<y?x:y; }

	inline void swap(int& x,int& y){ x^=y^=x^=y; }

	inline void ckmax(int& x,int y){ x=x<y?y:x; }

	inline void ckmin(int& x,int y){ x=x<y?x:y; }

} using namespace IO;

const int NN=100010,L=-1e6,R=1e9+1e6;

int n,mx,id,h[NN];

LL ans;

struct segment_tree{

	int tot,root,lc[NN*40],rc[NN*40],siz[NN*40];

	LL sum[NN*40];

	void pushup(int rt){

		siz[rt]=siz[lc[rt]]+siz[rc[rt]];

		sum[rt]=sum[lc[rt]]+sum[rc[rt]];

	}

	void insert(int& rt,int l,int r,int pos,int v){

		if(!rt) rt=++tot;

		if(l==r){ siz[rt]+=v; sum[rt]+=1ll*pos*v; return; }

		int mid=(l+r)/2;

		if(mid<=0&&l<0) --mid;

		if(pos<=mid) insert(lc[rt],l,mid,pos,v);

		else insert(rc[rt],mid+1,r,pos,v);

		pushup(rt);

	}

	int querysz(int rt,int l,int r,int opl,int opr){

		if(!rt) return 0;

		if(l>=opl&&r<=opr) return siz[rt];

		int mid=(l+r)/2,res=0;

		if(mid<=0&&l<0) --mid;

		if(opl<=mid) res+=querysz(lc[rt],l,mid,opl,opr);

		if(opr>mid) res+=querysz(rc[rt],mid+1,r,opl,opr);

		return res;

	}

	LL querysm(int rt,int l,int r,int opl,int opr){

		if(!rt) return 0;

		if(l>=opl&&r<=opr) return sum[rt];

		int mid=(l+r)/2; LL res=0;

		if(mid<=0&&l<0) --mid;

		if(opl<=mid) res+=querysm(lc[rt],l,mid,opl,opr);

		if(opr>mid) res+=querysm(rc[rt],mid+1,r,opl,opr);

		return res;

	}

}tl,tr;

LL getans(int ht,int pos){

	LL res=0;

	res+=1ll*tl.querysz(tl.root,L,R,L,ht-pos-1)*(ht-pos)-tl.querysm(tl.root,L,R,L,ht-pos-1);

	res+=1ll*tr.querysz(tr.root,L,R,L,ht+pos-1)*(ht+pos)-tr.querysm(tr.root,L,R,L,ht+pos-1);

	res+=tl.querysm(tl.root,L,R,ht-pos+1,R)-1ll*tl.querysz(tl.root,L,R,ht-pos+1,R)*(ht-pos);

	res+=tr.querysm(tr.root,L,R,ht+pos+1,R)-1ll*tr.querysz(tr.root,L,R,ht+pos+1,R)*(ht+pos);

//	cout<<ht<<' '<<pos<<' '<<res<<endl;

	return res;

}

signed main(){

	freopen("c.in","r",stdin);

	freopen("c.out","w",stdout);

	n=read(); ans=1e18;

	for(int i=1;i<=n;i++){

		h[i]=read();

		if(h[i]>mx) mx=h[i], id=i;

		tr.insert(tr.root,L,R,h[i]+i,1);

	}

	for(int i=1;i<=n;i++){

		tl.insert(tl.root,L,R,h[i]-i, 1);

		tr.insert(tr.root,L,R,h[i]+i,-1);

		int l=max(i,n-i+1),r=max(l,mx+abs(id-i));

		while(l+1<r){

			int mid=l+r>>1;

			int upr=tl.querysz(tl.root,L,R,L,mid-i-1)+tr.querysz(tr.root,L,R,L,mid+i-1);

			int dwn=n-upr;

			if(upr<=dwn) l=mid;

			else r=mid;

		}

		ans=min(ans,min(getans(l,i),getans(r,i)));

	}

	write(ans,'\n');

	return 0;

}


T2 应急棍

随便找规律，发现每次在最小的正方形中从左到右先放中心再放边的中点。

随便写写式子，高精小数是不可能写的。

\(code:\)

T2 

#include<bits/stdc++.h>

#define int long long

using namespace std;

typedef long double DB;

namespace IO{

	inline int read(){

		char ch=getchar(); int x=0,f=1;

		while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

		while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

		return x*f;

	}

	inline void write(int x,char sp){

		char ch[20]; int len=0;

		if(x<0){ putchar('-'); x=~x+1; }

		do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);

		for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);

	}

	inline int max(int x,int y){ return x<y?y:x; }

	inline int min(int x,int y){ return x<y?x:y; }

	inline void swap(int& x,int& y){ x^=y^=x^=y; }

	inline void ckmax(int& x,int y){ x=x<y?y:x; }

	inline void ckmin(int& x,int y){ x=x<y?x:y; }

} using namespace IO;

DB l,x,y,len;

int c,t,n,tmp,pw4[31],pw2[64];

signed main(){

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	c=read(); t=read();

	scanf("%Lf",&l);

	pw2[0]=pw4[0]=1;

	for(int i=1;i<31;i++) pw4[i]=pw4[i-1]*4;

	for(int i=1;i<64;i++) pw2[i]=pw2[i-1]*2;

	while(t--){

		n=read();

		if(n==1) printf("%d %d\n",0,0);

		if(n==2) printf("%.10Lf %.10Lf\n",l,l);

		if(n==3) printf("%d %.10Lf\n",0,l);

		if(n==4) printf("%.10Lf %d\n",l,0);

		if(n<5) continue;

		n-=4; tmp=0;//cout<<n<<' '<<pw4[tmp]+2*pw2[tmp]*(pw2[tmp]+1)<<endl;

		while(n-pw4[tmp]-2*pw2[tmp]*(pw2[tmp]+1)>0){

			n-=pw4[tmp]+2*pw2[tmp]*(pw2[tmp]+1);

			++tmp;

		}

		len=l/(DB)pw2[tmp];

		if(n<=pw4[tmp]){

			x=len/2.0+(DB)((n-1)/pw2[tmp])*len;

			y=len/2.0+(DB)((n-1)%pw2[tmp])*len;

			printf("%.10Lf %.10Lf\n",x,y);

			continue;

		}

		else n-=pw4[tmp];

		x=len*(DB)((n-1)/(pw2[tmp+1]+1));//cout<<len<<' '<<x<<' '<<n<<' '<<pw2[tmp+1]<<endl;

		if((n-1)%(pw2[tmp+1]+1)>=pw2[tmp]) x+=len/2.0, y=len*(DB)((n-1)%(pw2[tmp+1]+1)-pw2[tmp]);

		else y=len*(DB)((n-1)%(pw2[tmp+1]+1))+len/2.0;

		printf("%.10Lf %.10Lf\n",x,y);

	}

	return 0;

}


T3 擒敌拳

每个矩形的贡献是关于位置的一次函数。

单调栈维护出矩形最大管辖区间后李超线段树处理。

前两天刚学的东西，真滴NB。

\(code:\)

T3 

#include<bits/stdc++.h>

#define int long long

using namespace std;

namespace IO{

	inline int read(){

		char ch=getchar(); int x=0,f=1;

		while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

		while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

		return x*f;

	}

	inline void write(int x,char sp){

		char ch[20]; int len=0;

		if(x<0){ putchar('-'); x=~x+1; }

		do{ ch[len++]=(1<<4)+(1<<5)+x%10; x/=10; }while(x);

		for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);

	}

	inline int max(int x,int y){ return x<y?y:x; }

	inline int min(int x,int y){ return x<y?x:y; }

	inline void swap(int& x,int& y){ x^=y^=x^=y; }

	inline void ckmax(int& x,int y){ x=x<y?y:x; }

	inline void ckmin(int& x,int y){ x=x<y?x:y; }

} using namespace IO;

const int NN=200010;

int n,top,h[NN],stk[NN],ans[NN],timr[NN],timl[NN];

namespace LC_segtree{

	#define ld rt<<1

	#define rd (rt<<1)|1

	struct segs{

		int l,r,k,b;

		segs(){}

		segs(int a,int e,int c,int d){ l=a; r=e; k=c; b=d; }

		int calc(int pos){ return b+k*pos; }

		int cross(segs x){ return (b-x.b)/(x.k-k); }

	}s[NN<<2];

	void build(int rt,int l,int r){

		s[rt]=segs(1,n,0,-1e18);

		if(l==r) return;

		int mid=l+r>>1;

		build(ld,l,mid);

		build(rd,mid+1,r);

	}

	void insert(int rt,int l,int r,segs v){//cout<<s[rt].k<<' '<<s[rt].b<<' '<<v.k<<' '<<v.b<<' '<<s[rt].calc(l)<<' '<<v.calc(l)<<endl;

		if(l==r){

			if(s[rt].calc(l)<v.calc(l)) s[rt]=v;

			return;

		}

		if(l>=v.l&&r<=v.r){

			if(s[rt].calc(l)<=v.calc(l)&&s[rt].calc(r)<=v.calc(r)) s[rt]=v;

			else if(s[rt].calc(l)<=v.calc(l)||s[rt].calc(r)<=v.calc(r)){

				int mid=l+r>>1;

				if(s[rt].calc(mid)<v.calc(mid)) swap(s[rt],v);

				if(s[rt].cross(v)<=mid) insert(ld,l,mid,v);

				if(s[rt].cross(v)>=mid) insert(rd,mid+1,r,v);

			}

		} else{

			int mid=l+r>>1;

			if(v.l<=mid) insert(ld,l,mid,v);

			if(v.r>mid) insert(rd,mid+1,r,v);

		}

	}

	int query(int rt,int l,int r,int pos){//cout<<pos<<' '<<s[rt].k<<' '<<s[rt].b<<' '<<s[rt].calc(pos)<<endl;

		if(l==r) return s[rt].calc(pos);

		int res=s[rt].calc(pos),mid=l+r>>1;

		if(pos<=mid) return max(res,query(ld,l,mid,pos));

		else return max(res,query(rd,mid+1,r,pos));

	}

} using namespace LC_segtree;

signed main(){

	freopen("b.in","r",stdin);

	freopen("b.out","w",stdout);

	n=read(); build(1,1,n);

	for(int i=1;i<=n;i++) h[i]=read();

	for(int i=1;i<=n;i++){

		while(h[stk[top]]>h[i]) timr[stk[top--]]=i-1;

		stk[++top]=i;

	}

	while(top) timr[stk[top--]]=n;

	for(int i=n;i;i--){

		while(h[stk[top]]>h[i]) timl[stk[top--]]=i;

		stk[++top]=i;

	}

	for(int i=1;i<=n;i++){

//		cout<<timl[i]<<' '<<timr[i]<<endl;

		insert(1,1,n,segs(i,timr[i],h[i],-h[i]*timl[i]));

		ans[i]=max(ans[i-1],query(1,1,n,i));

	}

	for(int i=1;i<=n;i++) write(ans[i],i==n?'\n':' ');

	return 0;

}


T4 边数

太弱，待补（根本补不完

2021.9.22考试总结[NOIP模拟59]的相关教程结束。

《2021.9.22考试总结[NOIP模拟59].doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!