noip模拟34 solutions

我从来不为失败找借口，因为败了就是败了，没人听你诉说任何事情

今天很伤感，以来考试没考好，二来改题改半天也改不出来

这次算是炸出来了我经常范的一些错误，比如除以0

一共只有25pts，是我模拟考试以来最最最惨的成绩了吧

好像考场上的时候没有太想好思路就开始打了。。。。。。

二分这个不用说，一眼就是二分。。。。

一开始码了一个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); }

这个吧我考场上想到了一种线段树+树剖的做法。

这个做法吧是通过两个式子的加减实现的，记录非常的麻烦，而且还带两个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); } } }

所以我因为这个题错过了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); }