首页 > 代码库 > 联赛订正
联赛订正
我知道我为什么会爆炸了,而且是每道题都爆炸的样子。
赛场上漏看好多题意,直到订正了才发现,简直可以拍死自己。
“用来反复读题的时间永远不算你浪费” 亲测有效。555555......
D1T1:小学以来第一次挂T1.里程碑式错误m打成n。本地没报错(其实文件读入少了应该报的)+两个样例给我开绿灯=rp--(我五年级比赛T1都比这难啊(′д` )…彡…彡)
#include<cstdio> #include<algorithm> #define N 101012 int n,m,a[N]; char s[N][20]; int main() { // freopen("toy5.in","r",stdin);freopen("toy.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]);scanf("%s",s[i]); } int now=1; for(int i=1;i<=m;i++){ int ff,x;scanf("%d%d",&ff,&x); if(ff==0){ if(a[now]==0)ff=1; }else{ if(a[now]==0)ff=0; } x=x%n; if(ff==0)now+=x;else now=now-x;now=(now+n)%n;if(now==0)now=n; } printf("%s",s[now]); return 0; // fclose(stdin);fclose(stdout); }
D1T2:因为之前被R老师的树形DP套题套住了,加之看起来T2不像树形DP就没冲着标算去。一堆部分分。。。敲敲敲。。。算是唯一一道写得比较满意的。。。但是暴力分少,不服。
#include<cstdio> #include<cstring> #include<algorithm> #define N 300010 #define M 600010 int edgenum,edge3,edgenew,tm,st[N],ed[N],cnt=0,n,m; int dfn[N],mx[N],dep[N],w[N],ans[N],fa[N][20],next[M],next3[M],head3[M],vet3[M],pri[M],rt[M],vet[M],nextnew[M],vetnew[M]; int head[N],headnew[M],id[M],tt[M]; inline void add(int u,int v){ edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum; } void addnew(int u,int v,int w){ if(u==0)return;//printf("%d %d %d\n",u,v,w); edgenew++;vetnew[edgenew]=v;nextnew[edgenew]=headnew[u];headnew[u]=edgenew; pri[edgenew]=w; } void add3(int u,int v,int t,int w){ //printf("%d %d %d %d\n",t,u,v,w); edge3++;vet3[edge3]=v;next3[edge3]=head3[u];head3[u]=edge3;id[edge3]=t;tt[edge3]=w; } void dfs(int u,int ff){ int e=head[u];tm++;dfn[u]=tm;mx[u]=tm; //printf("%d\n",u); while(e>0){ int v=vet[e];//printf("%d\n",v); if(v!=ff){ dep[v]=dep[u]+1;fa[v][0]=u; dfs(v,u); mx[u]=mx[v]; } e=next[e]; } } void search1(int u,int ff){ int e=headnew[u]; while(e>0){ int v=vetnew[e],w=pri[e]; rt[v]+=w; e=nextnew[e]; } e=head3[dfn[u]]; while(e>0){ int v=vet3[e]; ans[id[e]]+=rt[v]*tt[e]; e=next3[e]; } e=head[u]; while(e>0){ int v=vet[e]; if(v!=ff){search1(v,u);} e=next[e]; } } void search2(int u,int ff){ int e=headnew[u]; while(e>0){ int v=vetnew[e],w=pri[e]; rt[v]+=w; e=nextnew[e]; } //printf("======%d %d \n",u,ans[1]); e=head3[dfn[u]]; while(e>0){ int v=vet3[e]; ans[id[e]]+=rt[v]*tt[e]; e=next3[e]; } e=head[u]; while(e>0){ int v=vet[e]; if(v!=ff){search2(v,u);} e=next[e]; } } inline int lca(int x,int y){ if(dep[x]<dep[y])std::swap(x,y); for(int i=18;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i]; for(int i=18;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; if(x!=y)x=fa[x][0];return x; } void clear(){ edgenew=0;edge3=0;memset(headnew,0,sizeof(headnew)); memset(head3,0,sizeof(head3));memset(rt,0,sizeof(rt)); } int main() { //freopen("running.in","r",stdin);freopen("running.out","w",stdout); int size = 256 << 20; // 256MB char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p)); scanf("%d%d",&n,&m); for(int i=1;i<=n-1;i++){ int u,v;scanf("%d%d",&u,&v); add(u,v);add(v,u); } dep[1]=1,tm=0;dfs(1,0); for(int i=1;i<=18;i++)for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1]; for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=m;i++)scanf("%d%d",&st[i],&ed[i]); for(int i=1;i<=m;i++){ int ff=lca(st[i],ed[i]); int x=dep[st[i]]+300000; addnew(st[i],x,1);addnew(fa[ff][0],x,-1); } for(int i=1;i<=n;i++){ int L=dfn[i],R=mx[i],x=dep[i]+w[i]+300000; if(x>=0&&x<=600000)add3(R,x,i,1),add3(L-1,x,i,-1); } search1(1,0); //for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n"); clear(); for(int i=1;i<=m;i++){ int ff=lca(st[i],ed[i]); int x=dep[st[i]]-2*dep[ff]+300000; addnew(ed[i],x,1);addnew(ff,x,-1); } for(int i=1;i<=n;i++){ int L=dfn[i],R=mx[i],x=w[i]-dep[i]+300000; if(x>=0&&x<=600000)add3(R,x,i,1),add3(L-1,x,i,-1); } search2(1,0); for(int i=1;i<n;i++)printf("%d ",ans[i]);printf("%d",ans[n]); return 0; }
#include<cstdio> #include<cstring> #include<algorithm> #define N 300010 #define M 600010 int edgenum,edgenew,tm,st[N],ed[N],cnt=0,n,m,u,v; int dfn[N],mx[N],dep[N],w[N],ans[N],fa[N][20],next[M],pri[M],rt[M],vet[M],nextnew[M],vetnew[M]; int head[N],headnew[M]; struct node{int sum,l,r;}tree[M*20]; inline void add(int u,int v){ edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum; } void addnew(int u,int v,int w){ if(u==0)return;if(v<0||v>600000)v=0; edgenew++;vetnew[edgenew]=v;nextnew[edgenew]=headnew[u];headnew[u]=edgenew; pri[edgenew]=w; } void dfs(int u,int ff){ int e=head[u];tm++;dfn[u]=tm;mx[u]=tm; //printf("%d\n",u); while(e>0){ int v=vet[e];//printf("%d\n",v); if(v!=ff){ dep[v]=dep[u]+1;fa[v][0]=u; dfs(v,u); mx[u]=mx[v]; } e=next[e]; } } void insert(int &p,int x,int st,int ed,int v){ if(p==0)p=++cnt,tree[p].sum=0; tree[p].sum+=v;if(st==ed)return; int mid=(st+ed)/2; if(x<=mid)insert(tree[p].l,x,st,mid,v);else insert(tree[p].r,x,mid+1,ed,v); } inline int query(int p,int l,int r,int st,int ed){ if(p==0)return 0; if(l==st&&r==ed)return tree[p].sum; int mid=(st+ed)/2; if(r<=mid)return query(tree[p].l,l,r,st,mid);else if(l>mid)return query(tree[p].r,l,r,mid+1,ed);else return query(tree[p].l,l,mid,st,mid)+query(tree[p].r,mid+1,r,mid+1,ed); } void search1(int u,int ff){ int e=head[u]; while(e>0){ int v=vet[e]; if(v!=ff){search1(v,u);} e=next[e]; } e=headnew[u]; while(e>0){ int v=vetnew[e],w=pri[e]; insert(rt[v],dfn[u],1,n,w); e=nextnew[e]; } int tmp=dep[u]+w[u]+300000; if(tmp>0&&tmp<=600000)ans[u]+=query(rt[tmp],dfn[u],mx[u],1,n); } inline void search2(int u,int ff){ int e=head[u]; while(e>0){ int v=vet[e]; if(v!=ff)search2(v,u); e=next[e]; }e=headnew[u]; while(e>0){ int v=vetnew[e],w=pri[e]; insert(rt[v],dfn[u],1,n,w); e=nextnew[e]; } int tmp=w[u]-dep[u]+300000; if(tmp>0&&tmp<=600000)ans[u]+=query(rt[tmp],dfn[u],mx[u],1,n); } inline int lca(int x,int y){ if(dep[x]<dep[y])std::swap(x,y); for(int i=18;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i]; for(int i=18;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; if(x!=y)x=fa[x][0];return x; } int main() { int size = 256 << 20; // 256MB char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p)); scanf("%d%d",&n,&m); for(int i=1;i<=n-1;i++){ int u,v;scanf("%d%d",&u,&v); add(u,v);add(v,u); } dep[1]=1,tm=0;dfs(1,0); for(int i=1;i<=18;i++)for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1]; for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=m;i++)scanf("%d%d",&st[i],&ed[i]); for(int i=1;i<=m;i++){ int ff=lca(st[i],ed[i]); int x=dep[st[i]]+300000; addnew(st[i],x,1);addnew(fa[ff][0],x,-1); } search1(1,0); edgenew=0;memset(headnew,0,sizeof(headnew)); cnt=0;memset(rt,0,sizeof(rt)); memset(tree,0,sizeof(tree)); for(int i=1;i<=m;i++){ int ff=lca(st[i],ed[i]); int x=dep[st[i]]-2*dep[ff]+300000; addnew(ed[i],x,1);addnew(ff,x,-1); } search2(1,0); for(int i=1;i<n;i++)printf("%d ",ans[i]);printf("%d",ans[n]); return 0; }
#include<cstdio> #include<algorithm> #define N 300020 #define M 600020 int n,m,edgenum,uu,vv,t1,t2; struct node{ int d,l; }b[N],c[N]; int vet[M],st[N],ok[N],down[N],up[N],ed[N],w[N],head[N],next[M],dep[N],ans[N]; void add(int u,int v){ edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum; } void dfs(int u,int ff){ int e=head[u]; while(e>0){ int v=vet[e]; if(v!=ff){ dep[v]=dep[u]+1;//fa[v][0]=1;if(dep[v]==w[v])pre[v][0]=1; dfs(v,u); } e=next[e]; } } void pao(int u,int ff,int tm){ if(u==vv){ok[u]=1;} //printf("%d %d %d\n",u,ff,tm); int e=head[u]; while(e>0){ int v=vet[e]; if(v!=ff){ pao(v,u,tm+1); if(ok[v]==1){ ok[u]=1; } } e=next[e]; } //printf("%d %d %d\n",u,ok[u],tm); if(ok[u]==1)if(w[u]==tm)ans[u]++; } void work1(){ for(int i=1;i<=m;i++){ uu=st[i],vv=ed[i]; for(int i=1;i<=n;i++)ok[i]=0; pao(uu,0,0); } for(int i=1;i<=n;i++)printf("%d ",ans[i]); } void go(int u,int ff){ int e=head[u]; while(e>0){ int v=vet[e]; if(v!=ff){ go(v,u);ok[u]+=ok[v]; } e=next[e]; }if(dep[u]==w[u])ans[u]=ok[u]; } void work2(){ for(int i=1;i<=m;i++){ uu=st[i],vv=ed[i]; ok[vv]++; } go(1,0);for(int i=1;i<=n;i++)printf("%d ",ans[i]); } bool cmp2(node a,node b){ if(a.d==b.d)return a.l>b.l; return a.d<b.d; } int find1(int x,int y){ int l=1,r=t1; while(l<r){ int mid=(l+r)/2; if(b[mid].d<x)l=mid+1;else r=mid; }if(b[l].d!=x)return 0; r=t1;int now=l; while(l+1<r){ int mid=(l+r)/2; if(b[mid].d>x)r=mid-1;else{ if(b[mid].l<y)r=mid-1;else l=mid; } } //printf("<>==%d %d %d %d\n",x,y,now,l); if(b[r].l>=y&&b[r].d==x)l=r;if(b[l].l>=y&&b[l].d==x)return l-now+1;else return 0; } int find2(int x,int y){ int l=1,r=t2; while(l<r){ int mid=(l+r)/2; if(c[mid].d<x)l=mid+1;else r=mid; }if(c[l].d!=x)return 0; r=t2;int now=l; while(l+1<r){ int mid=(l+r)/2; if(c[mid].d>x)r=mid-1;else{ if(c[mid].l<y)r=mid-1;else l=mid; } } //printf("<>==%d %d %d %d\n",x,y,now,l); if(c[r].l>=y&&c[r].d==x)l=r;if(c[l].l>=y&&c[l].d==x)return l-now+1;else return 0; } void work3() { for(int i=1;i<=m;i++){ int uu=st[i],vv=ed[i]; if(dep[uu]>dep[vv]){ t1++;b[t1].d=dep[uu];b[t1].l=-dep[vv]+dep[uu]; }else{ t2++;c[t2].d=dep[uu];c[t2].l=-dep[uu]+dep[vv]; } } std::sort(b+1,b+t1+1,cmp2);std::sort(c+1,c+t2+1,cmp2); //for(int i=1;i<=t1;i++)printf("==%d %d\n",i,b[i].d,b[i].l); for(int i=1;i<=n;i++){ int x=dep[i]+w[i],y=dep[i]-w[i]; if(x>=0&&x<=n)ans[i]+=find1(x,w[i]); if(y>=0&&y<=n)ans[i]+=find2(y,w[i]); //printf("aaa==%d %d %d %d\n",ans[i],w[i],x,y); } for(int i=1;i<=n;i++)printf("%d ",ans[i]); } int main() { freopen("running.in","r",stdin);freopen("running.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n-1;i++){ int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u); }dep[1]=0;dfs(1,0); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=m;i++){scanf("%d%d",&st[i],&ed[i]);} //work3();return 0; if(n<1000){ work1();return 0; } if(n%10==5){work2();return 0;} work3(); return 0; fclose(stdin);fclose(stdout); }
P.S.
酒店的电梯里,某司机:链怎么搞啊?猪猪侠:链不是随便都可以搞啊?
我的内心OS:???确乎都可以搞,但确乎不是随便搞啊,最后快调吐血惹,果然人弱差太多。。哎。。。
D1T3:日。。。犯了一个毛主力“初三犯过的错误”,当时多想了一下+没有对拍=rp--,没有什么分。。。
#include<cstdio> #include<algorithm> #define N 2020 #define M 100010 #define inf 1000000000 int n,m,V,E; int dis[303][303],c[N],d[N]; double p[N]; double f[2020][2020],g[2020][2020]; double min(double a,double b){if(a<b)return a;else return b;} int main() { scanf("%d%d%d%d",&n,&m,&V,&E); for(int i=1;i<=n;i++)scanf("%d",&c[i]); for(int i=1;i<=n;i++)scanf("%d",&d[i]); for(int i=1;i<=n;i++)scanf("%lf",&p[i]); for(int i=1;i<=V;i++) for(int j=1;j<=V;j++)if(i!=j)dis[i][j]=inf; for(int i=1;i<=E;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); if(w<dis[u][v])dis[u][v]=w,dis[v][u]=w; } for(int k=1;k<=V;k++) for(int i=1;i<=V;i++) for(int j=1;j<=V;j++)if(i!=k&&i!=j&&k!=j){ if(dis[i][k]+dis[k][j]<dis[i][j])dis[i][j]=dis[i][k]+dis[k][j]; } double ans=1000000000.0; g[1][0]=ans; for(int i=2;i<=n;i++){ f[i][0]=f[i-1][0]+dis[c[i-1]][c[i]]; g[i][0]=1000000000.0; for(int j=1;j<=m;j++){ f[i][j]=ans,g[i][j]=ans; f[i][j]=min(f[i][j],f[i-1][j]+dis[c[i]][c[i-1]]); f[i][j]=min(f[i][j],g[i-1][j]+(1.0-p[i-1])*dis[c[i]][c[i-1]]+p[i-1]*dis[d[i-1]][c[i]]); g[i][j]=min(g[i][j],f[i-1][j-1]+p[i]*dis[c[i-1]][d[i]]+(1.0-p[i])*dis[c[i-1]][c[i]]); g[i][j]=min(g[i][j],g[i-1][j-1]+p[i]*p[i-1]*dis[d[i-1]][d[i]]+p[i]*(1.0-p[i-1])*dis[d[i]][c[i-1]]+ (1.0-p[i])*(1.0-p[i-1])*dis[c[i]][c[i-1]]+p[i-1]*(1.0-p[i])*dis[c[i]][d[i-1]]); } } for(int j=0;j<=m;j++){ if(f[n][j]<ans)ans=f[n][j];if(g[n][j]<ans)ans=g[n][j]; } printf("%.2lf",ans); return 0; }
D2T1:对拍了所以没有挂T1??
#include<cstdio> #include<algorithm> int n,m,cas,k; int f[2020][2020],sum[2020][2020]; int main() { freopen("problem.in","r",stdin);freopen("problem.out","w",stdout); scanf("%d%d",&cas,&k);f[0][0]=1; for(int i=1;i<=2000;i++){ f[i][0]=1; for(int j=1;j<=i;j++){ f[i][j]=(f[i-1][j-1]+f[i-1][j])%k; } } for(int i=0;i<=2000;i++)for(int j=0;j<=i;j++)if(f[i][j]==0)sum[i][j]=1; for(int i=0;i<=2000;i++){ for(int j=1;j<=2000;j++){ sum[i][j]=sum[i][j]+sum[i][j-1]; } } while(cas--){ scanf("%d%d",&n,&m);int ans=0; for(int i=0;i<=n;i++) { int k=i;if(k>m)k=m;ans+=sum[i][k]; } printf("%d\n",ans); } return 0; fclose(stdin);fclose(stdout); }
D2T2:这么多部分分?我没有看见啊////第一天T2写得好辛苦导致第二天敲完堆逃,听到大家用链表之类怎么骗得开心,论心里阴影面积有多大。
#include<cstdio> #include<algorithm> #define N 8000000 #define ll long long using namespace std; int n,m,q,U,V,t,tot; int a[N],b[N],c[N],d[N]; int main() { scanf("%d%d%d%d%d%d",&n,&m,&q,&U,&V,&t); for(int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1);reverse(a+1,a+n+1); int t1=1,w1=n,t2=1,w2=0,t3=1,w3=0; for(int cas=1;cas<=m;cas++){ int x=-1000000000,ff=-1; if(t1<=w1){if(a[t1]>x)x=a[t1],ff=1;} if(t2<=w2){if(b[t2]>x)x=b[t2],ff=2;} if(t3<=w3){if(c[t3]>x)x=c[t3],ff=3;} if(ff==1)t1++;if(ff==2)t2++;if(ff==3)t3++; x=x+(cas-1)*q; if(cas%t==0){if(cas+t>m)printf("%d",x);else printf("%d ",x);} int L=(ll)x*U/V; w2++;b[w2]=L-q*cas;w3++;c[w3]=x-L-q*cas; } printf("\n"); for(int i=t1;i<=w1;i++){tot++;d[tot]=a[i]+m*q;} for(int i=t2;i<=w2;i++){tot++;d[tot]=b[i]+m*q;} for(int i=t3;i<=w3;i++){tot++;d[tot]=c[i]+m*q;} sort(d+1,d+tot+1); reverse(d+1,d+tot+1); for(int i=1;i<=tot;i++)if(i%t==0){ if(i+t>tot)printf("%d",d[i]);else printf("%d ",d[i]); } return 0; }
D2T3:还分上取整下取整?我没有看见啊////考场上爽快地用给的m剪枝,一眼看过去全部都是高斯记号嘛,又想当然了,原来我还是适合一个字一个字手指着电脑读题目。。QAQ
#include<cstdio> #include<algorithm> #include<cmath> #define ll long long using namespace std; int n,m,ans,tot,cas; int ok[30];ll dp[30][30];int f[500000]; double eps=0.00000001; struct node{ double x,y; }a[30]; struct wxx{ double a,b; }b[30]; double aabs(double x){ if(x<-eps)return -x;else return x; } int main() { scanf("%d",&cas); while(cas--){ scanf("%d%d",&n,&m);ans=n; if (m == 1) ans = ceil((double) n / 3 + 1.0); for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y); for(int k=1;k<n;k++){ for(int i=k+1;i<=n;i++){ dp[k][i]=0; if(aabs(a[i].x*a[i].x-a[i].x*a[k].x)<eps)continue; double aa,bb; aa=(a[i].y-a[k].y*(a[i].x/a[k].x))/(a[i].x*a[i].x-a[i].x*a[k].x); bb=(a[k].y-aa*a[k].x*a[k].x)/a[k].x; if(aa>=-eps)continue; for(int j=1;j<=n;j++) if(aabs(aa*a[j].x*a[j].x+bb*a[j].x-a[j].y)<eps){dp[k][i]+=1ll<<(j-1);} } }int all=(1<<n)-1; f[all]=0; for(int sta=all-1;sta>=0;sta--){ int k=0; for(int i=1;i<=n;i++)if((sta&(1<<(i-1)))==0){ k=i;break; } f[sta]=f[sta|(1<<(k-1))]+1; for(int j=k+1;j<=n;j++)if(dp[k][j]>0){ if(f[sta|dp[k][j]]+1<f[sta])f[sta]=f[sta|dp[k][j]]+1; } } printf("%d\n",f[0]); } }
联赛前一礼拜真的感觉自己快死了,never experienced feelings,mentally and physically,整个人的正气一直没有恢复,当时想的是:
考前这么虚,rp会转移到考试时吗,发现是我想多了。
至于题解和一些过程……
(未完待续)
联赛订正