noip仿真模拟34 solutions

我从不为不成功找借口,由于败了便是败了,没有人听你述说一切事儿

今日很悲伤,至今考試没有考好,二来改题改大半天也改不出来

此次算得上炸出来我经常范的一些不正确,例如除于0

一共仅有25pts,就是我考试模拟至今最最最惨的考试成绩了吧

T1 Merchant

仿佛考试场上的情况下沒有太想好构思就逐渐打过。。。。。。

二分这一别说,一眼便是二分。。。。

一开始码了一个01挎包用于分辨,复杂\(\mathcal{O(n^2logn)}\)

之后发觉不对,我好像立即取前m个较大的就好了,复杂性\(\mathcal{O(nlog^2n)}\)

这一是我考试场上的22pts编码,为什么,由于我除于0,立即段错误

考试场下,我立即想起来 nth_element ,这东西能够\(\mathcal{O(n)}\)求前m大的数啊

随后我立即把sort换为它,WA 44pts,为什么,由于也没有将负值取值为0

假如前m数量中有负值,我彻底能够不用他,因此 要和0取max

AC_code

#include<bits/stdc  .h>
using namespace std;
#define re register int
#define ll long long
const int N=1e6 5;
ll n,m,s,maxn;
ll k[N],b[N],no[N];
ll f[N],bb[N];
bool check(ll x){
	for(re i=1;i<=n;i  ){
		no[i]=k[i]*x b[i];
		no[i]=max(no[i],0ll);
	}
	nth_element(no 1,no n-m 1,no n 1);
	ll tmp=0;
	for(re i=n;i>=n-m 1;i--){
		tmp =no[i];
		if(tmp>=s)return true;
	}
	return false;
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&s);
	bool flag=false;
	for(re i=1;i<=n;i  ){
		scanf("%lld%lld",&k[i],&b[i]);
		bb[i]=b[i];
	}
	sort(bb 1,bb n 1);
	ll tmp=0;
	for(re i=n;i>=n-m 1;i--){
		tmp =bb[i];
		if(tmp>=s)flag=true;
	}
	ll l=0,r=1000000000ll,mid;
	while(l<r){
		mid=l r>>1;
		if(check(mid))r=mid;
		else l=mid 1;
	}
	printf("%lld",r);
}


T2 Equation

这个吧我考试场上想起了一种线段树 树剖的作法。

这一作法吧是根据2个算式的加减法完成的,纪录十分的不便,并且还带2个log

码长270,为了更好地祭拜这般其长的编码,我特意把他粘在这儿

0pts

#include<bits/stdc  .h>
using namespace std;
#define re register int
#define ll long long
const int N=1e6 5;
int n,q;
int to[N],nxt[N],head[N],rp;
void add_edg(int x,int y){
	to[  rp]=y;
	nxt[rp]=head[x];
	head[x]=rp;
}
ll val[N],len[N];
int siz[N],son[N],fa[N],dep[N],top[N];
int dfn[N],cnt,idf[N];
void dfs_fi(int x){
	siz[x]=1;son[x]=0;
	for(re i=head[x];i;i=nxt[i]){
		int y=to[i];
		dep[y]=dep[x] 1;
		dfs_fi(y);
		siz[x] =siz[y];
		if(!son[x]||siz[y]>siz[son[x]])son[x]=y;
	}
}
void dfs_se(int x,int f){
	top[x]=f;dfn[x]=  cnt;idf[cnt]=x;
	if(son[x])dfs_se(son[x],f);
	for(re i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==son[x])continue;
		dfs_se(y,y);
	}
}
int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
struct XDS{
	#define ls x<<1
	#define rs x<<1|1
	ll tr[N];
	bool typ[N],tyq[N];
	bool tp[N],tq[N];
	bool rep,req;
	void pushup(int x){
		if(tyq[ls]&&typ[rs]){
			typ[x]=typ[ls];
			tyq[x]=!tyq[rs];
			tr[x]=tr[ls]-tr[rs];
			return ;
		}
		if(!tyq[ls]&&!typ[rs]){
			typ[x]=!typ[ls];
			tyq[x]=tyq[rs];
			tr[x]=tr[rs]-tr[ls];
			return ;
		}
		if(tyq[ls]&&!typ[rs]){
			typ[x]=typ[ls];
			tyq[x]=tyq[rs];
			tr[x]=tr[ls] tr[rs];
			return ;
		}
		if(!tyq[ls]&&typ[rs]){
			typ[x]=typ[ls];
			tyq[x]=tyq[rs];
			tr[x]=tr[ls] tr[rs];
			return ;
		}
	}
	void build(int x,int l,int r){
		if(l==r){
			typ[x]=tyq[x]=true;
			tr[x]=val[idf[l]];
			return ;
		}
		int mid=l r>>1;
		build(ls,l,mid);
		build(rs,mid 1,r);
		pushup(x);
		return ;
	}
	void ins(int x,int l,int r,int pos,ll v){
		if(l==r){
			typ[x]=tyq[x]=true;
			tr[x]=v;
			return ;
		}
		int mid=l r>>1;
		if(pos<=mid)ins(ls,l,mid,pos,v);
		else ins(rs,mid 1,r,pos,v);
		pushup(x);
		return ;
	}
	ll query(int x,int l,int r,int ql,int qr){
		if(ql>qr)return 0;
		if(ql<=l&&r<=qr){
			tp[x]=typ[x];
			tq[x]=tyq[x];
			return tr[x];
		}
		int mid=l r>>1;
		ll tmp1=0,tmp2=0;
		if(ql<=mid)tmp1=query(ls,l,mid,ql,qr);
		if(qr>mid)tmp2=query(rs,mid 1,r,ql,qr);
		if(!tmp1){
			tp[x]=tp[rs];tq[x]=tq[rs];		return tmp2;
		}
		if(!tmp2){
			tp[x]=tp[ls];tq[x]=tq[ls];
			return tmp1;
		}
		if(tq[ls]&&tp[rs]){
			tp[x]=tp[ls];tq[x]=!tq[rs];
			return tmp1-tmp2;
		}
		if(!tq[ls]&&!tp[rs]){
			tp[x]=!tp[ls];tq[x]=tq[rs];
			return tmp2-tmp1;
		}
		tp[x]=tp[ls];tq[x]=tq[rs];
		return tmp1 tmp2;
	}
	#undef ls
	#undef rs
}xds;
bool rxp,rxq,ryp,ryq;
ll get_tHIS(int x,int y){
	rxp=false;rxq=true;
	ryp=false;ryq=true;
	ll rex=0,rey=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]){
			int tmp=xds.query(1,1,n,dfn[top[x]],dfn[x]);
			if(xds.tq[1]&&rxp){
				rxp=xds.tp[1];rxq=!rxq;
				rex=tmp-rex;
			}
			else if(!xds.tq[1]&&!rxp){
				rxp=!xds.tp[1];rxq=rxq;
				rex=rex-tmp;
			}
			else {
				rxp=xds.tp[1];rxq=rxq;
				rex =tmp;
			}
			x=fa[top[x]];
		}
		else{
			int tmp=xds.query(1,1,n,dfn[top[y]],dfn[y]);
			if(xds.tq[1]&&ryp){
				ryp=xds.tp[1];ryq=!ryq;
				rey=tmp-rey;
			}
			else if(!xds.tq[1]&&!ryp){
				ryp=!xds.tp[1];ryq=ryq;
				rey=rey-tmp;
			}
			else {
				ryp=xds.tp[1];ryq=ryq;
				rey =tmp;
			}
			y=fa[top[y]];
		}
	}
	if(dep[x]>dep[y]){
		int tmp=xds.query(1,1,n,dfn[y] 1,dfn[x]);
		if(xds.tq[1]&&rxp){
			rxp=xds.tp[1];rxq=!rxq;
			rex=tmp-rex;
		}
		else if(!xds.tq[1]&&!rxp){
			rxp=!xds.tp[1];rxq=rxq;
			rex=rex-tmp;
		}
		else {
			rxp=xds.tp[1];rxq=rxq;
			rex =tmp;
		}
	}
	else{
		int tmp=xds.query(1,1,n,dfn[x] 1,dfn[y]);
		//cout<<tmp<<endl;
		if(xds.tq[1]&&ryp){
			ryp=xds.tp[1];ryq=!ryq;
			rey=tmp-rey;
		}
		else if(!xds.tq[1]&&!ryp){
			ryp=!xds.tp[1];ryq=ryq;
			rey=rey-tmp;
		}
		else {
			ryp=xds.tp[1];ryq=ryq;
			rey =tmp;
		}
	}
	if(rxp&&ryp){
		ryq=!ryq;
		return rex-rey;
	}
	if(!rxp&&!ryp){
		rxq=!rxq;
		return rey-rex;
	}
	return rex rey;
}
signed main(){
	scanf("%d%d",&n,&q);
	for(re i=2;i<=n;i  ){
		int x;scanf("%d%lld",&x,&val[i]);
		add_edg(x,i);fa[i]=x;
	}
	dfs_fi(1);dfs_se(1,1);
	xds.build(1,1,n);
	while(q--){
		int ty;
		scanf("%d",&ty);
		if(ty==1){
			int u,v;ll s;
			scanf("%d%d%lld",&u,&v,&s);
			if(u==v){
				ll bi=s/2;
				ll now=get_this(1,v);
				if(1==v)printf("none\n");
				else if(rxq&&ryq)printf("%lld\n",now-bi);
				else if(!rxq&&!ryq)printf("%lld\n",-now-bi);
				else if(!rxq&&ryq)printf("%lld\n",now bi);
				else printf("%lld\n",-now bi);
				continue;
			}
			ll tmp=get_this(u,v);
			//cout<<dfn[u]<<" "<<dfn[v]<<endl;
			//cout<<rxq<<" "<<ryq<<" "<<tmp<<endl;
			if(rxq&&ryq&&s==tmp)
				printf("inf\n");
			else if(rxq&&ryq&&s!=tmp)
				printf("none\n");
			else {
				ll now;
				if(rxq&&!ryq){
					ll bi=(s tmp)/2;
					now=get_this(1,u);
					if(rxq&&ryq)printf("%lld\n",now-bi);
					else if(!rxq&&!ryq)printf("%lld\n",-now-bi);
					else if(!rxq&&ryq)printf("%lld\n",now bi);
					else printf("%lld\n",-now bi);
				}
				else{
					ll bi=(s tmp)/2;
					now=get_this(1,v);
					if(rxq&&ryq)printf("%lld\n",now-bi);
					else if(!rxq&&!ryq)printf("%lld\n",-now-bi);
					else if(!rxq&&ryq)printf("%lld\n",now bi);
					else printf("%lld\n",-now bi);
				}
			}
		}
		else{
			int u;ll w;
			scanf("%d%lld",&u,&w);
			xds.ins(1,1,n,dfn[u],w);
		}
	}
}


可是之后发觉实际上沒有那麼繁杂,立即运用边权和x1来表明每一个点的点权

大家只必须 根据奇偶数来分辨应当加或是减

立即树状数组维护保养就好了

AC_code

#include<bits/stdc  .h>
using namespace std;
#define re register int
#define ll long long
const int N=1e6 5;
int n,q,fa[N];
ll val[N];
int to[N],nxt[N],head[N],rp;
void add_edg(int x,int y){
	to[  rp]=y;
	nxt[rp]=head[x];
	head[x]=rp;
}
int dfn[N],dfm[N],cnt,idf[N];
int dep[N];
void dfs(int x){
	dfn[x]=  cnt;
	idf[cnt]=x;
	for(re i=head[x];i;i=nxt[i]){
		int y=to[i];
		dep[y]=dep[x] 1;
		dfs(y);
	}
	dfm[x]=cnt;
}
ll tr[N];
int lb(int x){return x&(-x);}
void ins(int x,ll v){
	for(re i=x;i<=n;i =lb(i))
		tr[i] =v;
}
ll query(int x){
	ll ret=0;
	for(re i=x;i;i-=lb(i))
		ret =tr[i];
	return ret;
}
signed main(){
	scanf("%d%d",&n,&q);
	for(re i=2;i<=n;i  ){
		scanf("%d%lld",&fa[i],&val[i]);
		add_edg(fa[i],i);
	}
	dfs(1);
	for(re i=2;i<=n;i  ){
		int tmp;
		if(dep[i]%2)tmp=-1;
		else tmp=1;
		ins(dfn[i],val[i]*tmp);
		ins(dfm[i] 1,-val[i]*tmp);
	}
	while(q--){
		int typ;
		scanf("%d",&typ);
		if(typ==1){
			int u,v;
			ll s;
			scanf("%d%d%lld",&u,&v,&s);
			ll tmpu=query(dfn[u]);
			ll tmpv=query(dfn[v]);
			if(dep[u]%2)tmpu=-tmpu;
			if(dep[v]%2)tmpv=-tmpv;
			if(dep[u]%2==dep[v]%2){
				ll tmp=tmpu tmpv-s;
				if(tmp%2)printf("none\n");
				else if(dep[u]%2)printf("%lld\n",tmp/2);
				else if(dep[v]%2==0)printf("%lld\n",-tmp/2);
			}
			else{
				ll tmp=tmpu tmpv;
				if(tmp==s)printf("inf\n");
				else printf("none\n");
			}
		}
		else{
			int u,tmp;
			ll w;
			scanf("%d%lld",&u,&w);
			if(dep[u]%2)tmp=-1;
			else tmp=1;
			ins(dfn[u],-val[u]*tmp);
			ins(dfm[u] 1,val[u]*tmp);
			val[u]=w;
			ins(dfn[u],val[u]*tmp);
			ins(dfm[u] 1,-val[u]*tmp);
		}
	}
}


T3 Rectangle

所以我由于这一题错过A层????

实际上挺难过的,自身改题一直尤其慢,并且构思还一直有误差

就这个题一开始我觉得偏了许多,

我就用当今的树状数组去升级前边的,而题解是立即将前边的取值回来

我是呕吐啊,确实很是无可奈何,最终不得已只有去看看编码

总得来说便是编码工作能力过度弱了

这一便是一个用树状数组提升的枚举类型题;

你发觉仅有在界限上有点儿的情况下这一方形才算是合理合法的,

那麼大家装作每一列仅有一个点,那麼大家就可以固定不动这一点

从这一点往前枚举类型前边每一列的点,大家假如想要这多列做为矩形框的界限

这两个点务必应选上,大家只必须 寻找这些y尤其大尤其小的就好了

立即把每一个矩形框都组成出去

那麼假如拓展到好几个点的情况下,大家只必须 依据这多列的点吧全部编码序列分为好多个块就好了

AC_code

#include<bits/stdc  .h>
using namespace std;
#define re register int
#define ll long long
const int N=1e4 5;
const int M=2505;
const ll mod=1e9 7;
int n;
int sca[M][M];
bool vis[M][M];
ll ans;
struct BIT{
	ll tr[M];
	int lb(int x){return x&(-x);}
	void ins(int x,ll v){
		for(re i=x;i<=2500;i =lb(i))
			tr[i] =v;
	}
	ll query(int x){
		ll ret=0;
		for(re i=x;i;i-=lb(i))
			ret =tr[i];
		return ret;
	}
}bit[M],num[M];
signed main(){
	scanf("%d",&n);
	for(re i=1;i<=n;i  ){
		int x,y;
		scanf("%d%d",&x,&y);
		sca[x][  sca[x][0]]=y;
	}
	for(re i=1;i<=2500;i  ){
		sca[i][sca[i][0] 1]=2501;
		sort(sca[i] 1,sca[i] sca[i][0] 1);
	}
	for(re i=1;i<=2500;i  ){
		if(!sca[i][0])continue;
		for(re j=1;j<=sca[i][0];j  ){
			vis[i][sca[i][j]]=true;
			num[i].ins(sca[i][j],1);
			bit[i].ins(sca[i][j],sca[i][j]);
		}
		for(re j=i-1;j>=1;j--){
			if(!sca[j][0])continue;
			for(re k=1;k<=sca[j][0];k  ){
				if(vis[i][sca[j][k]])continue;
				vis[i][sca[j][k]]=true;
				num[i].ins(sca[j][k],1);
				bit[i].ins(sca[j][k],sca[j][k]);
			}
			int noi=1,noj=1;
			int upy=max(sca[i][1],sca[j][1]);
			while(sca[i][noi 1]<=upy)noi  ;
			while(sca[j][noj 1]<=upy)noj  ;
			while(noi<=sca[i][0]&&noj<=sca[j][0]){
				int mx=min(sca[i][noi 1],sca[j][noj 1]);
				int mn=min(sca[i][noi],sca[j][noj]);
				ll uy=bit[i].query(mx-1) mod-bit[i].query(upy-1);
				ll dy=bit[i].query(mn);
				ll us=num[i].query(mx-1) mod-num[i].query(upy-1);
				ll ds=num[i].query(mn);
				ans=(ans (uy*ds%mod mod-dy*us%mod)%mod*(i-j)%mod)%mod;
				upy=mx;
				if(sca[i][noi 1]<=mx)noi  ;
				if(sca[j][noj 1]<=mx)noj  ;
			}
		}
	}
	printf("%lld",ans);
}