题解:
https://files.cnblogs.com/files/clrs97/2023_ZJCPC_Tutorial.pdf
Code:
A. Look and Say
#include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int n; cin>>n; string s; cin>>s; char pre=' '; int cnt=0; for(auto ch:s) { if(ch==pre)cnt++; else { if(cnt)cout<<cnt<<pre; pre=ch;cnt=1; } } cout<<cnt<<pre; return 0; }
B. Master of Polygon
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N=200005,M=200005,K=17,inf=~0U>>1; int n,m,cq,i,xl,xr; bool ans[M]; int idseg[K][N],idque[K][M]; struct P{ int x,y; P(){} P(int _x,int _y){x=_x,y=_y;} P operator-(const P&b)const{return P(x-b.x,y-b.y);} P operator+(const P&b)const{return P(x+b.x,y+b.y);} ll operator*(const P&b)const{return 1LL*x*b.x+1LL*y*b.y;} bool operator==(const P&b)const{return x==b.x&&y==b.y;} void read(){scanf("%d%d",&x,&y);} }a[N]; struct Line{ P a,b; int xl,xr; int sx,sy,dx,dy; ll base; void fix(){ if(a.x>b.x)swap(a,b); xl=a.x,xr=b.x; sx=a.x,sy=a.y,dx=b.x-a.x,dy=b.y-a.y; base=1LL*sy*dx-1LL*sx*dy; } }seg[N],que[M]; struct Frac{ ll u,d; Frac(){} Frac(ll _u,ll _d){ u=_u,d=_d; if(d<0)u*=-1,d*=-1; } bool operator<(const Frac&b)const{return u*b.d<b.u*d;} bool operator>(const Frac&b)const{return u*b.d>b.u*d;} bool operator<=(const Frac&b)const{return u*b.d<=b.u*d;} bool operator>=(const Frac&b)const{return u*b.d>=b.u*d;} }slo[M]; inline int sgn(ll x){ if(x>0)return 1; return x?-1:0; } inline ll cross(const P&a,const P&b){return 1LL*a.x*b.y-1LL*a.y*b.x;} inline void umin(int&a,int b){a>b?(a=b):0;} inline void umax(int&a,int b){a<b?(a=b):0;} inline Frac gety(const Line&a,int x){ if(a.dx==0)return Frac(a.sy,1); return Frac(a.base+1LL*x*a.dy,a.dx); } inline bool point_on_segment(const P&p,const P&a,const P&b){ return cross(b-a,p-a)==0&&(p-a)*(p-b)<=0; } inline bool has_intersection(const Line&A,const Line&B){ if(!A.dx&&!A.dy)return point_on_segment(A.a,B.a,B.b); const P&a=A.a; const P&b=A.b; const P&p=B.a; const P&q=B.b; int d1=sgn(cross(b-a,p-a)),d2=sgn(cross(b-a,q-a)); int d3=sgn(cross(q-p,a-p)),d4=sgn(cross(q-p,b-p)); if(d1*d2<0&&d3*d4<0)return 1; if((d1==0&&point_on_segment(p,a,b))|| (d2==0&&point_on_segment(q,a,b))|| (d3==0&&point_on_segment(a,p,q))|| (d4==0&&point_on_segment(b,p,q)))return 1; return 0; } namespace CaseWholeSeg{ int cnt,q[N]; inline void init(){cnt=0;} inline void add(int x){q[++cnt]=x;} inline bool cmpseg(int A,int B){ const Line&p=seg[A]; const Line&q=seg[B]; int x=p.a==q.a?min(p.xr,q.xr):max(p.xl,q.xl); return gety(p,x)<gety(q,x); } inline void work(){sort(q+1,q+cnt+1,cmpseg);} inline bool ask(const Line&p){ int l=1,r=cnt,mid; while(l<=r){ mid=(l+r)>>1; const Line&o=seg[q[mid]]; if(has_intersection(p,o))return 1; int x=max(p.xl,o.xl); if(gety(p,x)<gety(o,x))r=mid-1;else l=mid+1; } return 0; } } namespace CaseWholeQue{ int xl,xr; int cs,idseg[N]; int cq,idque[M]; Frac yl[M],yr[M]; int cnt,cp,cl,cr,idl[N],idr[N]; P pool[N*2]; int ccur,chull; struct Component{ int st,en; bool isl,isr; Frac lmi,lma,rmi,rma; void upl(const Frac&b){ if(!isl){ isl=1; lmi=lma=b; return; } if(lmi>b)lmi=b; if(lma<b)lma=b; } void upr(const Frac&b){ if(!isr){ isr=1; rmi=rma=b; return; } if(rmi>b)rmi=b; if(rma<b)rma=b; } }com[N]; struct Point{ int x;Frac y; Point(){} Point(const P&b){x=b.x,y=Frac(b.y,1);} Point(int _x,const Frac&_y){x=_x,y=_y;} }cur[N*2],hull[N*2]; inline bool cmpx(const P&a,const P&b){return a.x<b.x;} inline void init(int _xl,int _xr){xl=_xl,xr=_xr;cs=cq=0;} inline void addseg(int x){idseg[++cs]=x;} inline void addque(int x){ idque[++cq]=x; yl[x]=gety(que[x],xl); yr[x]=gety(que[x],xr); } inline Frac slope(const Point&a,const Point&b){//a.x<b.x return Frac(b.y.u*a.y.d-a.y.u*b.y.d,(b.x-a.x)*a.y.d*b.y.d); } namespace CaseLeft{ inline bool cmpyl(int x,int y){return yl[x]<yl[y];} inline bool cmplma(int x,int y){return com[x].lma<com[y].lma;} inline bool cmplmi(int x,int y){return com[x].lmi>com[y].lmi;} inline void ext_down(int&n,Point*q,const Point&p){ if(n&&q[n].x==p.x){ if(q[n].y>=p.y)return; n--; } while(n>1&&slope(p,q[n])<=slope(q[n],q[n-1]))n--; q[++n]=p; } inline bool notin_down(const Point&p){ if(chull<=1)return 1; if(p.x>hull[1].x)return 1; int l=2,r=chull-1,t=1; while(l<=r){ int mid=(l+r)>>1; if(p.x==hull[mid].x)return p.y>=hull[mid].y; if(p.x>hull[mid].x)r=mid-1;else l=(t=mid)+1; } return slope(hull[t+1],p)>=slope(p,hull[t]); } inline void ext_up(int&n,Point*q,const Point&p){ if(n&&q[n].x==p.x){ if(q[n].y<=p.y)return; n--; } while(n>1&&slope(p,q[n])>=slope(q[n],q[n-1]))n--; q[++n]=p; } inline bool notin_up(const Point&p){ if(chull<=1)return 1; if(p.x>hull[1].x)return 1; int l=2,r=chull-1,t=1; while(l<=r){ int mid=(l+r)>>1; if(p.x==hull[mid].x)return p.y<=hull[mid].y; if(p.x>hull[mid].x)r=mid-1;else l=(t=mid)+1; } return slope(hull[t+1],p)<=slope(p,hull[t]); } inline void solve(){ if(!cl)return; int i,j,k,A,B; sort(idque+1,idque+cq+1,cmpyl); sort(idl+1,idl+cl+1,cmplma); //left Frac minl; for(i=cq,j=cl;i;i--){ A=idque[i]; if(ans[A])continue; while(j){ B=idl[j]; if(com[B].lma<yl[A])break; if(j==cl)minl=com[B].lmi; else if(minl>com[B].lmi)minl=com[B].lmi; j--; } if(j<cl&&minl<=yl[A])ans[A]=1; } //down chull=0; for(i=j=1;i<=cq;i++){ A=idque[i]; if(ans[A])continue; while(j<=cl){ B=idl[j]; if(com[B].lma>=yl[A])break; ccur=0; if(com[B].isr)ext_down(ccur,cur,Point(xr,com[B].rma)); for(k=com[B].en;k>=com[B].st;k--)ext_down(ccur,cur,pool[k]); ext_down(ccur,cur,Point(xl,com[B].lma)); if(com[B].isr){ chull=ccur; for(k=1;k<=ccur;k++)hull[k]=cur[k]; }else{ k=ccur; while(k>1&¬in_down(cur[k-1]))k--; while(chull&&hull[chull].x<=cur[k].x)chull--; for(;k<=ccur;k++)ext_down(chull,hull,cur[k]); } j++; } if(chull<=1)continue; int l=1,r=chull-1; if(hull[1].x==xr){ if(hull[1].y>=yr[A]){ ans[A]=1; continue; } if(chull==2)continue; l++; } int t=r--; const Frac&v=slo[A]; //min slope(hull[t+1],hull[t]) >= v while(l<=r){ int mid=(l+r)>>1; if(slope(hull[mid+1],hull[mid])>=v)r=(t=mid)-1;else l=mid+1; } if(slope(que[A].a,hull[t])>=slope(hull[t],que[A].b))ans[A]=1; } //up sort(idl+1,idl+cl+1,cmplmi); chull=0; for(i=cq,j=1;i;i--){ A=idque[i]; if(ans[A])continue; while(j<=cl){ B=idl[j]; if(com[B].lmi<=yl[A])break; ccur=0; if(com[B].isr)ext_up(ccur,cur,Point(xr,com[B].rmi)); for(k=com[B].en;k>=com[B].st;k--)ext_up(ccur,cur,pool[k]); ext_up(ccur,cur,Point(xl,com[B].lmi)); if(com[B].isr){ chull=ccur; for(k=1;k<=ccur;k++)hull[k]=cur[k]; }else{ k=ccur; while(k>1&¬in_up(cur[k-1]))k--; while(chull&&hull[chull].x<=cur[k].x)chull--; for(;k<=ccur;k++)ext_up(chull,hull,cur[k]); } j++; } if(chull<=1)continue; int l=1,r=chull-1; if(hull[1].x==xr){ if(hull[1].y<=yr[A]){ ans[A]=1; continue; } if(chull==2)continue; l++; } int t=r--; const Frac&v=slo[A]; while(l<=r){ int mid=(l+r)>>1; if(slope(hull[mid+1],hull[mid])<=v)r=(t=mid)-1;else l=mid+1; } if(slope(que[A].a,hull[t])<=slope(hull[t],que[A].b))ans[A]=1; } } } namespace CaseRight{ inline bool cmpyr(int x,int y){return yr[x]<yr[y];} inline bool cmprma(int x,int y){return com[x].rma<com[y].rma;} inline bool cmprmi(int x,int y){return com[x].rmi>com[y].rmi;} inline void ext_down(int&n,Point*q,const Point&p){ if(n&&q[n].x==p.x){ if(q[n].y>=p.y)return; n--; } while(n>1&&slope(q[n],p)>=slope(q[n-1],q[n]))n--; q[++n]=p; } inline bool notin_down(const Point&p){ if(chull<=1)return 1; if(p.x<hull[1].x)return 1; int l=2,r=chull-1,t=1; while(l<=r){ int mid=(l+r)>>1; if(p.x==hull[mid].x)return p.y>=hull[mid].y; if(p.x<hull[mid].x)r=mid-1;else l=(t=mid)+1; } return slope(hull[t],p)>=slope(p,hull[t+1]); } inline void ext_up(int&n,Point*q,const Point&p){ if(n&&q[n].x==p.x){ if(q[n].y<=p.y)return; n--; } while(n>1&&slope(q[n],p)<=slope(q[n-1],q[n]))n--; q[++n]=p; } inline bool notin_up(const Point&p){ if(chull<=1)return 1; if(p.x<hull[1].x)return 1; int l=2,r=chull-1,t=1; while(l<=r){ int mid=(l+r)>>1; if(p.x==hull[mid].x)return p.y<=hull[mid].y; if(p.x<hull[mid].x)r=mid-1;else l=(t=mid)+1; } return slope(hull[t],p)<=slope(p,hull[t+1]); } inline void solve(){ if(!cr)return; int i,j,k,A,B; sort(idque+1,idque+cq+1,cmpyr); sort(idr+1,idr+cr+1,cmprma); //right Frac minl; for(i=cq,j=cr;i;i--){ A=idque[i]; if(ans[A])continue; while(j){ B=idr[j]; if(com[B].rma<yr[A])break; if(j==cr)minl=com[B].rmi; else if(minl>com[B].rmi)minl=com[B].rmi; j--; } if(j<cr&&minl<=yr[A])ans[A]=1; } //down chull=0; for(i=j=1;i<=cq;i++){ A=idque[i]; if(ans[A])continue; while(j<=cr){ B=idr[j]; if(com[B].rma>=yr[A])break; ccur=0; if(com[B].isl)ext_down(ccur,cur,Point(xl,com[B].lma)); for(k=com[B].st;k<=com[B].en;k++)ext_down(ccur,cur,pool[k]); ext_down(ccur,cur,Point(xr,com[B].rma)); if(com[B].isl){ chull=ccur; for(k=1;k<=ccur;k++)hull[k]=cur[k]; }else{ k=ccur; while(k>1&¬in_down(cur[k-1]))k--; while(chull&&hull[chull].x>=cur[k].x)chull--; for(;k<=ccur;k++)ext_down(chull,hull,cur[k]); } j++; } if(chull<=1)continue; int l=1,r=chull-1; if(hull[1].x==xl){ if(hull[1].y>=yl[A]){ ans[A]=1; continue; } if(chull==2)continue; l++; } int t=r--; const Frac&v=slo[A]; //min slope(hull[t],hull[t+1]) <= v while(l<=r){ int mid=(l+r)>>1; if(slope(hull[mid],hull[mid+1])<=v)r=(t=mid)-1;else l=mid+1; } if(slope(que[A].a,hull[t])>=slope(hull[t],que[A].b))ans[A]=1; } //up sort(idr+1,idr+cr+1,cmprmi); chull=0; for(i=cq,j=1;i;i--){ A=idque[i]; if(ans[A])continue; while(j<=cr){ B=idr[j]; if(com[B].rmi<=yr[A])break; ccur=0; if(com[B].isl)ext_up(ccur,cur,Point(xl,com[B].lmi)); for(k=com[B].st;k<=com[B].en;k++)ext_up(ccur,cur,pool[k]); ext_up(ccur,cur,Point(xr,com[B].rmi)); if(com[B].isl){ chull=ccur; for(k=1;k<=ccur;k++)hull[k]=cur[k]; }else{ k=ccur; while(k>1&¬in_up(cur[k-1]))k--; while(chull&&hull[chull].x>=cur[k].x)chull--; for(;k<=ccur;k++)ext_up(chull,hull,cur[k]); } j++; } if(chull<=1)continue; int l=1,r=chull-1; if(hull[1].x==xl){ if(hull[1].y<=yl[A]){ ans[A]=1; continue; } if(chull==2)continue; l++; } int t=r--; const Frac&v=slo[A]; //min slope(hull[t],hull[t+1]) >= v while(l<=r){ int mid=(l+r)>>1; if(slope(hull[mid],hull[mid+1])>=v)r=(t=mid)-1;else l=mid+1; } if(slope(que[A].a,hull[t])<=slope(hull[t],que[A].b))ans[A]=1; } } } inline void work(){ if(!cs||!cq)return; int i,j,k,x; static int q[N]; static bool vis[N],is[N]; for(i=1;i<=cs;i++){ x=idseg[i]; is[x]=1; vis[x]=0; } cnt=cp=cl=cr=0; for(i=1;i<=cs;i++){ x=idseg[i]; if(vis[x])continue; cnt++; com[cnt].st=cp+1; com[cnt].isl=com[cnt].isr=0; vis[x]=1; int head=1,tail=1; q[1]=x; while(head<=tail){ x=q[head++]; const Line&p=seg[x]; if(p.xl>xl&&p.xr<xr){ pool[++cp]=p.a; pool[++cp]=p.b; }else if(p.xr<xr){ if(p.xl==p.xr){ com[cnt].upl(Frac(p.a.y,1)); com[cnt].upl(Frac(p.b.y,1)); }else{ pool[++cp]=p.b; com[cnt].upl(gety(p,xl)); } }else{ if(p.xl==p.xr){ com[cnt].upr(Frac(p.a.y,1)); com[cnt].upr(Frac(p.b.y,1)); }else{ pool[++cp]=p.a; com[cnt].upr(gety(p,xr)); } } for(j=x-1;j<=x+1;j+=2){ k=j; if(k<0)k+=n; if(k>=n)k-=n; if(!is[k]||vis[k])continue; const P&v=j<x?a[x]:a[x+1]; if(v.x<xl||v.x>xr)continue; vis[k]=1; q[++tail]=k; } } com[cnt].en=cp; if(com[cnt].isl)idl[++cl]=cnt; if(com[cnt].isr)idr[++cr]=cnt; sort(pool+com[cnt].st,pool+cp+1,cmpx); } for(i=1;i<=cs;i++)is[idseg[i]]=0; CaseLeft::solve(); CaseRight::solve(); } } void solve(int o,int l,int r,int cs,int cq){ if(l>=r||!cs||!cq)return; //Case 1: whole seg CaseWholeSeg::init(); CaseWholeQue::init(l,r); for(int i=0;i<cs;i++){ int id=idseg[o][i]; int a=seg[id].xl,b=seg[id].xr; if(a<=l&&b>=r)CaseWholeSeg::add(id); else CaseWholeQue::addseg(id); } CaseWholeSeg::work(); for(int i=0;i<cq;i++){ int id=idque[o][i]; int a=que[id].xl,b=que[id].xr; if(CaseWholeSeg::ask(que[id]))ans[id]=1; else if(a<=l&&b>=r)CaseWholeQue::addque(id); } //Case 2: whole query, partial seg CaseWholeQue::work(); if(l+1==r)return; int mid=(l+r)>>1; for(int _=0;_<2;_++){ int _l,_r,_cs=0,_cq=0; if(_==0)_l=l,_r=mid;else _l=mid,_r=r; for(int i=0;i<cs;i++){ int id=idseg[o][i]; int a=seg[id].xl,b=seg[id].xr; if(a<=l&&b>=r)continue; if(a>_r||b<_l)continue; idseg[o+1][_cs++]=id; } for(int i=0;i<cq;i++){ int id=idque[o][i]; if(ans[id])continue; int a=que[id].xl,b=que[id].xr; if(a<=l&&b>=r)continue; if(a>_r||b<_l)continue; idque[o+1][_cq++]=id; } solve(o+1,_l,_r,_cs,_cq); } } namespace CaseBothSameX{ int i,l,r,x,ce; struct E{ int x,y,v,p; E(){} E(int _x,int _y,int _v,int _p){x=_x,y=_y,v=_v,p=_p;} }e[N+M]; inline bool cmpe(const E&a,const E&b){ if(a.x!=b.x)return a.x<b.x; if(a.y!=b.y)return a.y<b.y; return a.p<b.p; } void solve(){ for(i=0;i<cq;i++){ x=idque[0][i]; if(ans[x])continue; if(que[x].xl!=que[x].xr)continue; l=que[x].a.y,r=que[x].b.y; if(l>r)swap(l,r); e[ce++]=E(que[x].xl,r,l,x); } for(i=0;i<n;i++)if(a[i].x==a[i+1].x){ l=a[i].y,r=a[i+1].y; if(l>r)swap(l,r); e[ce++]=E(a[i].x,l,r,-1); } sort(e,e+ce,cmpe); for(i=0;i<ce;i++){ if(i==0||e[i].x!=e[i-1].x)r=-inf; if(e[i].p<0)umax(r,e[i].v); else if(r>=e[i].v)ans[e[i].p]=1; } } } int main(){ scanf("%d%d",&n,&m); xl=inf,xr=-inf; for(i=0;i<n;i++){ a[i].read(); umin(xl,a[i].x); umax(xr,a[i].x); } a[n]=a[0]; for(i=0;i<n;i++){ seg[i].a=a[i]; seg[i].b=a[i+1]; seg[i].fix(); idseg[0][i]=i; } for(i=0;i<m;i++){ que[i].a.read(); que[i].b.read(); que[i].fix(); umax(que[i].xl,xl); umin(que[i].xr,xr); if(que[i].xl>que[i].xr)continue; if(que[i].xl==que[i].xr&&que[i].a.x!=que[i].b.x){ if(que[i].xl==xl)que[i].a=que[i].b; else que[i].b=que[i].a; que[i].fix(); } idque[0][cq++]=i; if(que[i].xl<que[i].xr)slo[i]=Frac(que[i].b.y-que[i].a.y,que[i].b.x-que[i].a.x); } solve(0,xl,xr,n,cq); CaseBothSameX::solve(); for(i=0;i<m;i++)puts(ans[i]?"YES":"NO"); }
C. Shuttle Tour
#include<cstdio> typedef long long ll; const int N=200005,K=55; char on[N]; int n,m,i,op,x,y,z,g[N],v[N<<1],w[N<<1],nxt[N<<1],ed,seg[N]; int at[N],pool[N],pos[N],cp; int cnt,pre[K],len[K],cross[K],start[K]; ll sum[N]; inline void umin(int&a,int b){a>b?(a=b):0;} inline void umax(int&a,int b){a<b?(a=b):0;} struct E{ int l[K],r[K];bool have; void clr(){ for(int i=1;i<=cnt;i++){ l[i]=N; r[i]=0; } have=0; } void init(int x,int o){ clr(); if(o){ l[at[x]]=r[at[x]]=pos[x]; have=1; } } void operator+=(const E&o){ for(int i=1;i<=cnt;i++){ umin(l[i],o.l[i]); umax(r[i],o.r[i]); } have|=o.have; } ll cal(){ if(!have)return -1; static int sub[K]; int i,j,k; ll ret=0; for(i=1;i<=cnt;i++){ sub[i]=l[i]<=r[i]; } for(i=cnt;i;i--)sub[pre[i]]+=sub[i]; for(i=cnt;i;i--){ j=pre[i],k=cross[i]; if(sub[i]&&sub[i]<sub[1]){ umin(l[j],k); umax(r[j],k); ret+=len[i]; umin(l[i],start[i]); umax(r[i],start[i]); } if(l[i]<r[i])ret+=sum[pool[r[i]]]-sum[pool[l[i]]]; } return ret*2; } }val[524305],ans; inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;} void dfs(int x,int y,int z){ pool[++cp]=x; pos[x]=cp; at[x]=z; bool first=1; for(int i=g[x];i;i=nxt[i]){ int u=v[i]; if(u==y)continue; sum[u]=sum[x]+w[i]; if(first){ dfs(u,x,z); first=0; }else{ cnt++; pre[cnt]=z; len[cnt]=w[i]; cross[cnt]=pos[x]; start[cnt]=cp+1; dfs(u,x,cnt); } } } inline void up(int x){ val[x]=val[x<<1]; val[x]+=val[x<<1|1]; } void build(int x,int a,int b){ if(a==b){ seg[a]=x; val[x].init(a,on[a]); return; } int mid=(a+b)>>1; build(x<<1,a,mid); build(x<<1|1,mid+1,b); up(x); } inline void change(int x){ int y=seg[x]; val[y].init(x,on[x]); for(y>>=1;y;y>>=1)up(y); } void ask(int x,int a,int b,int c,int d){ if(c<=a&&b<=d){ ans+=val[x]; return; } int mid=(a+b)>>1; if(c<=mid)ask(x<<1,a,mid,c,d); if(d>mid)ask(x<<1|1,mid+1,b,c,d); } int main(){ scanf("%d%d%s",&n,&m,on+1); for(i=1;i<=n;i++)on[i]-='0'; for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); cnt=1; dfs(1,0,1); build(1,1,n); while(m--){ scanf("%d%d",&op,&x); if(op==1){ on[x]^=1; change(x); }else{ scanf("%d",&y); ans.clr(); ask(1,1,n,x,y); printf("%lld\n",ans.cal()); } } }
D. Master of Both III
#include<bits/stdc++.h> using namespace std; const int N=22,P=998244353; int n,w[N]; long long f[1<<N]; void cmin(long long &a,long long b) { a=a<b?a:b; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&w[i]); reverse(w+1,w+n); for(int S=0;S<(1<<n);S++) f[S]=1e18; f[0]=f[1]=0; int A=(1<<n)-1; for(long long S=1;S<(1<<n);S++) for(int i=1;i<n;i++) cmin(f[S|((S<<i)&A)|((S<<i)>>n)],f[S]+w[i]); for(int S=A;S>=0;S--) for(int i=0;i<n;i++) if(!(S>>i&1)) cmin(f[S],f[S^(1<<i)]); long long ans=0; for(int S=0;S<(1<<n);S++) { ans+=f[S]*S; ans%=P; } printf("%lld\n",ans); }
E. Interval Sum
#include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int n; cin>>n; if(n%2==0) { cout<<n/2<<' '; } cout<<n<<' '; for(int i=1;i<=(n-1)/2;i++) cout<<i<<' '<<n-i<<' '; cout<<endl; return 0; }
F. Turn on the Light
#include<bits/stdc++.h> using namespace std; const int N=33; int n; void solve(int l,int r,int cl,int cr) { if(l==r) { printf("! %d\n",l); fflush(stdout); // exit(0); return; } if(r==l+1) { printf("? %d\n",l); fflush(stdout); int x; scanf("%d",&x); if(x==abs(cl-cr)) solve(l,l,cl,cr); else solve(r,r,cl+1,cr); return; } if(cl==cr) { printf("? %d\n",r); fflush(stdout); int x; scanf("%d",&x); if(x==abs(cl-cr)) solve(r,r,cl,cr); else solve(l,r-1,cl,cr+1); } else { int mid=(l+r)>>1; printf("? %d\n",mid); fflush(stdout); int x; scanf("%d",&x); if(x==abs(cl-cr)) solve(mid,mid,cl,cr); else if(x==abs(cl-(cr+1))) solve(l,mid-1,cl,cr+1); else solve(mid+1,r,cl+1,cr); } } int main() { scanf("%d",&n); solve(1,n,0,0 ); }
G. Puzzle: Kusabi
#include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int n; cin>>n; vector<int> pa(n+5),dep(n+5); vector<int> ty(n+5); dep[1]=1; for(int i=2;i<=n;i++) { int u,v; string s; cin>>u>>v>>s; if(s=="Chang")ty[i]=3; else if(s=="Tong")ty[i]=2; else if(s=="Duan")ty[i]=1; pa[i]=v; dep[i]=dep[v]+1; } vector<pair<int,int>> ans; vector<vector<tuple<int,int,int>>> rem(n+5); for(int u=n;u>=1;u--) { if(ty[u])rem[u].emplace_back(u,ty[u],dep[u]); vector<pair<int,int>> spl[5]; // cerr<<"merge "<<u<<endl; for(auto [id,t,d]:rem[u]) { // cerr<<id<<' '<<t<<' '<<d<<endl; spl[t].emplace_back(d,id); } for(int i=1;i<=3;i++)sort(spl[i].begin(),spl[i].end()); int fl=0; while(not spl[2].empty()) { auto [d1,x]=spl[2].back();spl[2].pop_back(); if(spl[2].empty()) { if(fl)return cout<<"NO"<<endl,0; rem[pa[u]].emplace_back(x,2,d1); fl=1; break; } auto [d2,y]=spl[2].back();spl[2].pop_back(); if(d1!=d2) { if(fl or spl[2].empty())return cout<<"NO"<<endl,0; rem[pa[u]].emplace_back(x,2,d1); fl=1; tie(d1,x)=spl[2].back();spl[2].pop_back(); } if(d1!=d2)return cout<<"NO"<<endl,0; ans.emplace_back(x,y); } if(spl[1].size()!=spl[3].size() and fl)return cout<<"NO"<<endl,0; if(spl[1].size()==spl[3].size()) { for(int i=0;i<(int)spl[1].size();i++) { if(spl[1][i].first<spl[3][i].first)ans.emplace_back(spl[1][i].second,spl[3][i].second); else return cout<<"NO"<<endl,0; } } else if(spl[1].size()>spl[3].size())//keep shortest in 1 { if((int)spl[1].size()>(int)spl[3].size()+1)return cout<<"NO"<<endl,0; for(int i=spl[3].size()-1,j=spl[1].size()-1;i>=0;i--,j--) { if(spl[1][j].first<spl[3][i].first)ans.emplace_back(spl[1][j].second,spl[3][i].second); else { if(fl)return cout<<"NO"<<endl,0; else rem[pa[u]].emplace_back(spl[1][j].second,1,spl[1][j].first),fl=1,i++; } } if(not fl)rem[pa[u]].emplace_back(spl[1][0].second,1,spl[1][0].first); } else //keep longest in 3 { if((int)spl[3].size()>(int)spl[1].size()+1)return cout<<"NO"<<endl,0; for(int i=0,j=0;i<(int)spl[1].size();i++,j++) { if(spl[1][i].first<spl[3][j].first)ans.emplace_back(spl[1][i].second,spl[3][j].second); else { if(fl)return cout<<"NO"<<endl,0; else rem[pa[u]].emplace_back(spl[3][j].second,3,spl[3][j].first),fl=1,i--; } } if(not fl)rem[pa[u]].emplace_back(spl[3][spl[3].size()-1].second,3,spl[3][spl[3].size()-1].first); } } if(not rem[0].empty())return cout<<"NO"<<endl,0; cout<<"YES"<<endl; for(auto [x,y]:ans)cout<<x<<' '<<y<<endl; return 0; }
H. Puzzle: Tapa
#include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int n,m; cin>>n>>m; vector<string> S(2*n+5); for(int i=1;i<=2*n-1;i++) { string s; cin>>s; S[i]=' '+s; for(int j=1;j<=2*m-1;j++) if(S[i][j]=='.') S[i][j]='#'; } vector<vector<int>> G(n*m+5); auto getty=[&](int x,int y){return (x==1 or x==n) or (y==1 or y==m);}; auto geths=[&](int x,int y){return (x-1)*m+y;}; auto addedge=[&](int u,int v){G[u].push_back(v);G[v].push_back(u);}; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(S[2*i-1][2*j-1]=='2' or S[2*i-1][2*j-1]=='4' or S[2*i-1][2*j-1]=='7') { if(j<m) { if(m==2 and i!=1 and i!=n){} else if(S[2*i-1][2*j+1]=='2' or S[2*i-1][2*j+1]=='4' or S[2*i-1][2*j+1]=='7') if(getty(i,j)==getty(i,j+1)) addedge(geths(i,j),geths(i,j+1)); } if(i<n) { if(n==2 and j!=1 and j!=m){} else if(S[2*i+1][2*j-1]=='2' or S[2*i+1][2*j-1]=='4' or S[2*i+1][2*j-1]=='7') if(getty(i,j)==getty(i+1,j)) addedge(geths(i,j),geths(i+1,j)); } } } vector<int> ma(n*m+5); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if((i+j)%2==0 and (S[2*i-1][2*j-1]=='2' or S[2*i-1][2*j-1]=='4' or S[2*i-1][2*j-1]=='7')) { int u=geths(i,j); for(auto v:G[u]) { if(!ma[v]) { // cerr<<"match "<<u<<' '<<v<<endl; ma[u]=v,ma[v]=u; break; } } } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if((i+j)%2==0 and (S[2*i-1][2*j-1]=='2' or S[2*i-1][2*j-1]=='4' or S[2*i-1][2*j-1]=='7')) { int u=geths(i,j); if(!ma[u]) { vector<int> vis(n*m+5); function<bool(int)> dfs=[&](int u) { // cerr<<"dfs "<<u<<endl; for(auto v:G[u]) { if(not vis[v]) { vis[v]=1; if(!ma[v] or dfs(ma[v])) { // cerr<<"match "<<u<<' '<<v<<endl; ma[u]=v,ma[v]=u; return true; } } } return false; }; if(not dfs(u)) { cout<<"NO"<<endl; return 0; } } } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if((S[2*i-1][2*j-1]=='2' or S[2*i-1][2*j-1]=='4' or S[2*i-1][2*j-1]=='7') and not ma[geths(i,j)]) { cout<<"NO"<<endl; return 0; } if(ma[geths(i,j)]) { int v=ma[geths(i,j)]; int x=(v-1)/m+1,y=(v-1)%m+1; if(x>i)S[2*i-1+1][2*j-1]='.'; else if(y>j)S[2*i-1][2*j-1+1]='.'; } } cout<<"YES"<<endl; for(int i=1;i<=2*n-1;i++) { for(int j=1;j<=2*m-1;j++) cout<<S[i][j]; cout<<endl; } return 0; }
I. Equation Discovering
#include <bits/stdc++.h> using namespace std; inline void TestComplexity() { int n = 11; int unary = 2; int binary = 4; int ter = 1; int f[20][20]; memset(f, 0, sizeof f); f[0][0] = 1; for (int i = 0; i < n; ++i) for (int j = 0; j <= i; ++j) { f[i + 1][j + 1] += f[i][j] * ter; if (j >= 1) f[i + 1][j] += f[i][j] * unary; if (j >= 2) f[i + 1][j - 1] += f[i][j] * binary; } printf("%d\n", f[n][1]); // 2240512 // time complexity = 2240512 * 20 = 4e7 } const int N = 20; int n; double dx[N], dy[N]; struct StackItem { int size; double a[N]; }; StackItem operator+(const StackItem &u, const StackItem &v) { StackItem ans; ans.size = u.size + v.size; for (int i = 0; i < n; ++i) ans.a[i] = u.a[i] + v.a[i]; return ans; } StackItem operator-(const StackItem &u, const StackItem &v) { StackItem ans; ans.size = u.size + v.size; for (int i = 0; i < n; ++i) ans.a[i] = u.a[i] - v.a[i]; return ans; } StackItem operator*(const StackItem &u, const StackItem &v) { StackItem ans; ans.size = u.size + v.size; for (int i = 0; i < n; ++i) ans.a[i] = u.a[i] * v.a[i]; return ans; } StackItem operator/(const StackItem &u, const StackItem &v) { StackItem ans; ans.size = u.size + v.size; for (int i = 0; i < n; ++i) ans.a[i] = u.a[i] / v.a[i]; return ans; } StackItem Sin(StackItem u) { for (int i = 0; i < n; ++i) u.a[i] = sin(u.a[i]); return u; } StackItem Cos(StackItem u) { for (int i = 0; i < n; ++i) u.a[i] = cos(u.a[i]); return u; } StackItem MakeX() { StackItem ans; ans.size = 1; for (int i = 0; i < n; ++i) ans.a[i] = dx[i]; return ans; } bool Test(const StackItem &u) { for (int i = 0; i < n; ++i) if (abs(u.a[i] - dy[i]) / max(1.0, abs(dy[i])) > 1e-3) return 0; return 1; } bool TestDiv(const StackItem &u) { for (int i = 0; i < n; ++i) if (abs(u.a[i]) < 0.02) return 0; return 1; } StackItem sta[N], backup[N][2]; char sol[N]; namespace PrintOut { int c[N][2], sta[N]; void Print(char *sol, int x) { if (sol[x] == 'x') { printf("x"); } else if (sol[x] == 'c') { printf("cos("); Print(sol, c[x][0]); printf(")"); } else if (sol[x] == 's') { printf("sin("); Print(sol, c[x][0]); printf(")"); } else if (sol[x] == '+' || sol[x] == '-' || sol[x] == '*' || sol[x] == '/') { printf("("); Print(sol, c[x][0]); printf("%c", sol[x]); Print(sol, c[x][1]); printf(")"); } } void Solve(char *sol) { int top = 0; for (int i = 0; sol[i]; ++i) { if (sol[i] == '+' || sol[i] == '-' || sol[i] == '*' || sol[i] == '/') { c[i][0] = sta[top - 2]; c[i][1] = sta[top - 1]; top -= 2; } else if (sol[i] == 'c' || sol[i] == 's') { c[i][0] = sta[top - 1]; top -= 1; } sta[top++] = i; } Print(sol, sta[top - 1]); puts(""); } } inline void Dfs(int ps, int top) { if (top == 1 && Test(sta[top - 1])) { sol[ps] = 0; PrintOut::Solve(sol); exit(0); } if (ps == 10) return; if (top + 1 - (10 - ps - 1) <= 1) { sol[ps] = 'x'; sta[top] = MakeX(); Dfs(ps + 1, top + 1); } if (top - (10 - ps - 1) <= 1 && top) { backup[ps][0] = sta[top - 1]; sol[ps] = 'c'; sta[top - 1] = Cos(backup[ps][0]); Dfs(ps + 1, top); sol[ps] = 's'; sta[top - 1] = Sin(backup[ps][0]); Dfs(ps + 1, top); sta[top - 1] = backup[ps][0]; } if (top >= 2) { backup[ps][0] = sta[top - 2]; backup[ps][1] = sta[top - 1]; if (backup[ps][0].size <= backup[ps][1].size) { sol[ps] = '+'; sta[top - 2] = backup[ps][0] + backup[ps][1]; Dfs(ps + 1, top - 1); sol[ps] = '*'; sta[top - 2] = backup[ps][0] * backup[ps][1]; Dfs(ps + 1, top - 1); } sol[ps] = '-'; sta[top - 2] = backup[ps][0] - backup[ps][1]; Dfs(ps + 1, top - 1); if (TestDiv(backup[ps][1])) { sol[ps] = '/'; sta[top - 2] = backup[ps][0] / backup[ps][1]; Dfs(ps + 1, top - 1); } sta[top - 2] = backup[ps][0]; sta[top - 1] = backup[ps][1]; } } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%lf%lf", dx + i, dy + i); } Dfs(0, 0); return 0; }
J. Stage Clear
#include<cstdio> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int N=47,LIM=26; const ll inf=1LL<<60; int n,m,i,x,y,deg[N],pre[N][N];ll ans=inf; struct P{ ll a,b; P(){} P(ll _a,ll _b){a=_a,b=_b;} bool operator<(const P&o)const{ int sgn1=a<b,sgn2=o.a<o.b; if(sgn1!=sgn2)return sgn1<sgn2; if(a<b)return a>o.a; return b<o.b; } void operator+=(const P&o){ ll na=max(a,a-b+o.a),nb=b+o.b-a-o.a+na; a=na,b=nb; } }a[N],init[N]; inline void up(ll&a,ll b){a>b?(a=b):0;} namespace SMALL{ int m,S,i,j,k,mask[N];ll va[N],vb[N],f[(1<<(LIM-1))+1]; void solve(){ for(i=2;i<=n;i++){ S=0; for(j=0;j<deg[i];j++){ k=pre[i][j]; if(k>1)S|=1<<(k-2);else S|=1<<n; } mask[i-2]=S; va[i-2]=a[i].a; vb[i-2]=a[i].b; } n--; m=1<<n; for(S=1;S<m;S++)f[S]=inf; for(S=0;S<m;S++){ ll tmp=f[S]; if(tmp>=inf)continue; for(i=0;i<n;i++)if(!(S>>i&1)){ if((mask[i]&S)==mask[i])continue; ll now=tmp; now-=vb[i]; if(now<0)now=0; now+=va[i]; up(f[S^(1<<i)],now); } } ans=f[m-1]; } } namespace BIG{ int fa[N],f[N],vis[N],del[N],pos; typedef pair<int,int>PI; typedef pair<P,PI>PII; priority_queue<PII>q; int F(int x){return del[f[x]]?f[x]=F(f[x]):f[x];} inline void solve_tree(){ int i,x,y; for(pos=i=0;i<=n;i++)vis[i]=del[i]=0; a[1]=P(0,0); for(i=2;i<=n;i++)a[i]=init[i],f[i]=fa[i]; for(i=2;i<=n;i++)q.push(PII(a[i],PI(0,i))); while(!q.empty()){ PII t=q.top(); q.pop(); x=t.second.second; if(del[x])continue; if(t.second.first!=vis[x])continue; del[x]=1; y=F(x); a[y]+=a[x]; if(y>1)q.push(PII(a[y],PI(vis[y]=++pos,y))); } up(ans,a[1].a); } void dfs(int x){ if(x>n){ solve_tree(); return; } for(int i=0;i<deg[x];i++){ fa[x]=pre[x][i]; dfs(x+1); } } void solve(){ for(i=1;i<=n;i++)init[i]=a[i]; dfs(2); } } int main(){ scanf("%d%d",&n,&m); for(i=2;i<=n;i++)scanf("%lld%lld",&a[i].a,&a[i].b); while(m--){ scanf("%d%d",&x,&y); pre[y][deg[y]++]=x; } if(n<=LIM)SMALL::solve();else BIG::solve(); printf("%lld",ans); }
K. Lazy but Diligent
#include<bits/stdc++.h> using namespace std; #define N 420 struct course{ int s,t,p; bool operator < (const course &c) const{ return s<c.s; } }a[N]; int n,m,q,s,t,f[N][N],dp[N][N]; void cmin(int &x,int y){x=min(x,y);} void cmax(int &x,int y){x=max(x,y);} int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>q>>t>>s; memset(f,0x3f,sizeof f); for (int i=1;i<=n;++i) f[i][i]=0; for (int i=1;i<=m;++i){ int x,y,z; cin>>x>>y>>z; cmin(f[x][y],z); cmin(f[y][x],z); } for (int k=1;k<=n;++k){ for (int i=1;i<=n;++i){ for (int j=1;j<=n;++j){ cmin(f[i][j],f[i][k]+f[k][j]); } } } for (int i=1;i<=q;++i){ cin>>a[i].s>>a[i].t>>a[i].p; } a[0].s=a[0].t=0; a[0].p=1; ++q; a[q].s=a[q].t=t; a[q].p=1; sort(a,a+q+1); memset(dp,0xcf,sizeof dp); dp[0][0]=0; for (int i=1;i<=q;++i){ for (int j=1;j<=i;++j){ for (int k=0;k<i;++k){ int ti=a[i].s-a[k].t; int x=a[i].p,y=a[k].p; if (f[x][y]<=ti) cmax(dp[i][j],dp[k][j-1]); if (int dlt=ti-f[1][x]-f[1][y];dlt>=0) cmax(dp[i][j],dp[k][j-1]+dlt); } } } int ans=0; for (int i=1;i<=q;++i) if (dp[q][i]>=s) ans=i; cout<<ans-1<<'\n'; }
L. Barkley
#include<bits/stdc++.h> using namespace std; using ll=long long; using pii=pair<ll,int>; #define fs first #define sd second #define mp make_pair const int N=1e5+1e3+7; int n,q; ll a[N]; vector<pii>g[N]; ll ans; void dfs(int x,ll G,int t,int k) { if(x<t) { ans=max(ans,G); return; } if(!k) { for(auto [w,p]:g[x]) if(p<=t) { ans=max(ans,__gcd(G,w)); break; } return; } dfs(x-1,G,t,k-1); for(auto [w,p]:g[x]) dfs(p-2,__gcd(G,w),t,k-1); } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) { vector<pii>ng=g[i-1]; for(auto &[x,y]:ng) x=__gcd(x,a[i]); ng.push_back({a[i],i}); for(auto [x,y]:ng) if(!g[i].size()||x!=g[i].back().fs) g[i].push_back({x,y}); } for(int i=1;i<=n;i++) reverse(g[i].begin(),g[i].end()); while(q--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); ans=0; dfs(r,0,l,k); printf("%lld\n",ans); } }
M. A Wine and Four Dishes
#include<bits/stdc++.h> using namespace std; const int N=33; int n,x,y; int a[N],b[N]; int main() { scanf("%d%d%d",&n,&x,&y); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); if(!x&&!y) { puts("0"); return 0; } int ans=0; if(x) { int mx=-1; for(int i=1;i<=n;i++) if(a[i]==1) mx=max(mx,b[i]); if(mx==-1) { puts("IMPOSSIBLE"); return 0; } for(int i=1;i<=n;i++) if(a[i]==1&&b[i]==mx) { y-=b[i]; b[i]=0; break; } ans++; } sort(b+1,b+n+1); for(int i=n;i>=1;i--) { if(y<=0) break; ans++; y-=b[i]; } if(y>0) puts("IMPOSSIBLE"); else printf("%d\n",ans); }
- Programming Provincial Collegiate Sponsored Zhejiangprogramming provincial collegiate sponsored programming collegiate provincial contest programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong programming provincial collegiate shandong programming collegiate provincial counting 2023 programming collegiate provincial 题解programming collegiate provincial heilongjiang programming collegiate provincial