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这个吧我考场上想到了一种线段树+树剖的做法。
这个做法吧是通过两个式子的加减实现的，记录非常的麻烦，而且还带两个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来表示每个点的点权
我们只需要通过奇偶来判断应该加还是减