NOIP2016滚粗记
考完...身败名裂QAQ
(题目太长了...敲不动)
day1
T1
Description
顺时针逆时针数小人(迷之mengbier,mogician).
Solution
模拟.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define M 15 #define N 100005 using namespace std; struct toy{ int t;char c[M]; }a[N]; int n,m,t,s,u=1; inline void init(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d%s",&a[i].t,a[i].c+1); while(m--){ scanf("%d%d",&t,&s); if(t){//right if(a[u].t) u=(u-s+n)%n; else u=(u+s)%n; if(!u) u=n; } else{ if(a[u].t) u=(u+s)%n; else u=(u-s+n)%n; if(!u) u=n; } } printf("%s ",a[u].c+1); } int main(){ freopen("toy.in","r",stdin); freopen("toy.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
T2
Description
m个人同时从$s_i$到$t_i$(第0时刻开始),每个点有个人蹲在那sleep,第$w_i$秒的时候睁眼看看,然后他近视(只能看到当前点).求每个人能看到多少人.
Solution
在t时从x出发,
从下往上走:在$i$点能看到需满足$w_i=t+dep[x]-dep[i]$, 即 $w_i+dep[i]=t+dep[x]$;
从上往下走:在$i$点能看到需满足$w_i=t-dep[x]+
dep[i]$, 即 $w_i-dep[i]=t-dep[x]$.
然后只讨论从下往上走怎么处理(因为从上往下走处理方式同理):
对树上$w_i+dep[i]$的值相同的点进行差分,进出的时候+1,-1即可.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define K 20 #define N 300000 #define M 900000 using namespace std; typedef long long ll; stack<int> s; struct graph{ int nxt,to,ty; }e[N<<1],e2[M]; int f[N][K],px[N<<1],py[N<<1],t1[N],t2[N],w[N],g[N],g2[N],dep[N],ans[N],n,m,cnt; //px[x]:w[i]+dep[i]=x最近的点 //t1[i]:从下往上时,i能看到的人数 inline int read(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1)+(ret<<3)+c-'0'; c=getchar(); } return ret; } inline void adde(int x,int y){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y; } inline void adde2(int x,int y,int ty){ e2[++cnt].nxt=g2[x];g2[x]=cnt;e2[cnt].to=y;e2[cnt].ty=ty; } inline void dfs(int u){ dep[u]=1;s.push(u); while(!s.empty()){ u=s.top();s.pop(); if(u==1) for(int i=0;i<K;++i) f[u][i]=1; else for(int i=1;i<K;++i) f[u][i]=f[f[u][i-1]][i-1]; for(int i=g[u],c;i;i=e[i].nxt) if(!dep[c=e[i].to]){ dep[c]=dep[u]+1; f[c][0]=u;s.push(c); } } } inline int swim(int u,int h){ for(int i=0;h;++i,h>>=1) if(h&1) u=f[u][i]; return u; } inline int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); x=swim(x,dep[x]-dep[y]); if(x==y) return x; int i; while(true){ for(i=0;f[x][i]!=f[y][i];++i); if(!i) return f[x][0]; x=f[x][i-1];y=f[y][i-1]; } } inline void change(int u){ for(int i=g2[u];i;i=e2[i].nxt) if(!e2[i].ty){ --t1[px[e2[i].to+N]]; --t2[py[e2[i].to-(dep[u]<<1)+N]]; } else if(e2[i].ty&1) ++t1[px[e2[i].to+N]]/*,printf("+1:%d %d ",u,e2[i].to)*/; else ++t2[py[e2[i].to+N]]/*,printf("+2:%d %d ",u,e2[i].to)*/; } inline void dfs2(int u){ int wx=w[u]+dep[u]+N,wy=w[u]-dep[u]+N; int x=px[wx],y=py[wy]; px[wx]=py[wy]=u; for(int i=g[u],c;i;i=e[i].nxt) if(dep[c=e[i].to]>dep[u]) dfs2(c); change(u); ans[u]+=t1[u]+t2[u]; t1[x]+=t1[u];t2[y]+=t2[u]; px[wx]=x;py[wy]=y; } inline void Aireen(){ n=read();m=read(); for(int i=1,x,y;i<n;++i){ x=read();y=read(); adde(x,y);adde(y,x); } dfs(1); for(int i=1;i<=n;++i) w[i]=read(); cnt=0; int x,y,z; while(m--){ x=read();y=read(); z=lca(x,y); if(dep[x]-dep[z]==w[z]) ++ans[z]; adde2(x,dep[x],1); adde2(y,dep[x]-(dep[z]<<1),2); adde2(z,dep[x],0); } dfs2(1); for(int i=1;i<=n;++i) printf("%d ",ans[i]); puts(""); } int main(){ freopen("running.in","r",stdin); freopen("running.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0; }
T3
Description
一个人为了少走路可以选择去另一个教室上课,换课需申请,申请有概率不通过.求上课需要行走的路程和的期望.
Solution
floyd+数学期望+01背包.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define M 305 #define N 2005 #define INF 1e9 using namespace std; int c[N],d[N],n,m,v,e; double f[N][N][2],dis[M][M],g[N],ans; //x:走到d[i-1]的概率; y:走到d[i]的概率 inline double p(int i,double x,double y){ return dis[c[i-1]][c[i]]*(1.0-x)*(1.0-y)+dis[c[i-1]][d[i]]*(1.0-x)*y+dis[d[i-1]][c[i]]*x*(1.0-y)+dis[d[i-1]][d[i]]*x*y; } inline void init(){ 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",&g[i]); for(int i=1;i<v;++i) for(int j=i+1;j<=v;++j) dis[i][j]=dis[j][i]=INF; for(int i=1,j,k,w;i<=e;++i){ scanf("%d%d%d",&j,&k,&w); dis[j][k]=dis[k][j]=min(dis[j][k],(double)(w)); } for(int k=1;k<=v;++k) for(int i=1;i<=v;++i) for(int j=1;j<=v;++j) dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]); for(int i=1;i<=n;++i) for(int j=0;j<=m;++j) f[i][j][0]=f[i][j][1]=INF; f[1][0][0]=f[1][1][1]=0.0; for(int i=2;i<=n;++i){ f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]]; for(int j=1,k=min(i,m);j<=k;++j){ f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]],f[i-1][j][1]+p(i,g[i-1],0.0)); f[i][j][1]=min(f[i-1][j-1][0]+p(i,0.0,g[i]),f[i-1][j-1][1]+p(i,g[i-1],g[i])); } } ans=INF; for(int i=0;i<=m;++i) ans=min(ans,min(f[n][i][0],f[n][i][1])); printf("%.2lf",ans); } int main(){ freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
day2
T1
Description
给定n,m,求的对数.
Solution
质因数分解,递推,前缀和维护.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define M 8 #define N 2001 using namespace std; bool flag; int p[M]={2,3,5,7,11,13,17,19}; int tot[N][M],f[N][N],sum[N][N],a[M],n,m,t,k; inline void init(){ scanf("%d%d",&t,&k); for(int i=2,l;i<N;++i){ l=i; for(int j=0;j<M;++j) while(!(l%p[j])){ ++tot[i][j];l/=p[j]; } } for(int j=0;j<M;++j) a[j]=tot[k][j]; for(int i=1;i<N;++i) for(int j=0;j<M;++j) tot[i][j]+=tot[i-1][j]; for(int i=1;i<N;++i) for(int j=1;j<=i;++j){ flag=true; for(int l=0;l<M;++l) if(tot[i][l]-tot[j][l]-tot[i-j][l]<a[l]){ flag=false;break; } if(flag) f[i][j]=1; } sum[0][0]=f[0][0]; for(int i=1;i<N;++i) for(int j=0;j<N;++j) sum[i][j]=sum[i-1][j]+f[i][j]; for(int i=0;i<N;++i) for(int j=1;j<N;++j) sum[i][j]=sum[i][j-1]+sum[i][j]; while(t--){ scanf("%d%d",&n,&m); printf("%d ",sum[n][m]); } } int main(){ freopen("problem.in","r",stdin); freopen("problem.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
T2
Description
蚯蚓切呀切,某次打ACM的时候遇到过.
Solution
满足单调性,三个数组维护.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 7100005 using namespace std; typedef long long ll; typedef long double ld; struct worm{ ll x,s; }q1[N],q2[N],q3[N]; ld p; ll len[N],q,sum; int n,m,t,h1,h2,h3,t1,t2,t3,ty,cnt; inline int read(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1)+(ret<<3)+c-'0'; c=getchar(); } return ret; } inline ld rd(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1)+(ret<<3)+c-'0'; c=getchar(); } return (ld)(ret); } inline ll rd_ll(){ ll ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1LL)+(ret<<3LL)+c-'0'; c=getchar(); } return ret; } inline ll f(ll sum){ ld k=(ld)(sum)*p; return (ll)(k); } inline ll tot(worm x){ return x.x-x.s+sum; } inline bool cmp(worm x,worm y){ return x.x>y.x; } inline void init(){ n=read();m=read();q=rd_ll(); p=rd();p/=rd();t=read(); for(int i=1;i<=n;++i) q1[i].x=(ll)(read()); h1=h2=h3=1;t1=n; sort(q1+1,q1+1+t1,cmp); n+=m; while(m--){ ++cnt; if(h1<=t1){ len[cnt]=tot(q1[h1]);ty=1; } if(h2<=t2&&tot(q2[h2])>=len[cnt]){ len[cnt]=tot(q2[h2]);ty=2; } if(h3<=t3&&tot(q3[h3])>=len[cnt]){ len[cnt]=tot(q3[h3]);ty=3; } q2[++t2].x=f(len[cnt]); q3[++t3].x=len[cnt]-q2[t2].x; sum+=q;q2[t2].s=q3[t3].s=sum; if(ty==1) ++h1; else if(ty==2) ++h2; else ++h3; } for(int i=t;i<=cnt;i+=t) printf("%lld ",len[i]); printf(" "); for(int i=1;i<=n;++i){ len[0]=0LL; if(h1<=t1){ len[0]=tot(q1[h1]);ty=1; } if(h2<=t2&&tot(q2[h2])>=len[0]){ len[0]=tot(q2[h2]);ty=2; } if(h3<=t3&&tot(q3[h3])>=len[0]){ len[0]=tot(q3[h3]);ty=3; } if(ty==1) ++h1; else if(ty==2) ++h2; else ++h3; if(!(i%t)) printf("%lld ",len[0]); } printf(" "); } int main(){ freopen("earthworm.in","r",stdin); freopen("earthworm.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
T3
Description
求至少需要多少条抛物线可以过所有的点.
Solution
状压DP.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 20 #define M 160 #define K 262145 #define eps 1e-13 using namespace std; struct line{ double a,b; }a[M]; double x[N],y[N]; int f[K],g[M],n,m,k,l,t,cnt; inline double sqr(double k){ return k*k; } inline bool cmp(line x,line y){ if(fabs(x.a-y.a)<eps) return x.b<y.b; return x.a<y.a; } inline double func(double a,double b,double x){ return a*sqr(x)+b*x; } inline bool chk(int i,int j){ return fabs(y[j]-func(a[i].a,a[i].b,x[j]))<eps; } inline bool ask(int i,int j){ a[++cnt].a=(x[i]/x[j]*y[j]-y[i])/(x[i]*x[j]-sqr(x[i])); a[cnt].b=(y[i]-sqr(x[i])*a[cnt].a)/x[i]; return a[cnt].a<-eps; } inline void init(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%lf%lf",&x[i],&y[i]); cnt=0;k=1; for(int i=1;i<n;++i) for(int j=i+1;j<=n;++j) if(!ask(i,j)) --cnt; if(!cnt) printf("%d ",n); else{ sort(a+1,a+1+cnt,cmp); for(int i=2;i<=cnt;++i) if(fabs(a[i].a-a[i-1].a)>eps||fabs(a[i].b-a[i-1].b)>eps) a[++k]=a[i]; memset(g,0,sizeof(g)); for(int i=1;i<=k;++i) for(int j=1;j<=n;++j) if(chk(i,j)) g[i]|=(1<<j-1); for(int i=1;i<=n;++i) g[i+k]=1<<i-1; l=(1<<n)-1;k+=n; for(int i=1;i<=l;++i) f[i]=n; for(int i=1;i<=k;++i) for(int j=l;j>=0;--j) f[j|g[i]]=min(f[j|g[i]],f[j]+1); printf("%d ",f[l]); } } } int main(){ freopen("angrybirds.in","r",stdin); freopen("angrybirds.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }