noip2016
玩具谜题
模拟
int main(){
rd(n),rd(m);
for(int i=1;i<=n;i++) scanf("%d%s",&cx[i],name[i]);
int cur=1,x;
for(int i=1;i<=m;i++){
scanf("%d%d",&fx,&x);
if(fx^cx[cur]) cur=(cur+x)%n;
else cur=(cur+n-x)%n;
if(cur==0) cur=n;
}
printf("%s",name[cur]);
return 0;
}
换教室
void floyd(){
for(int i=1;i<=nn;++i) mp[i][i]=0;
for(int k=1;k<=nn;++k)
for(int i=1;i<=nn;++i)
for(int j=1;j<i;++j)
if(mp[i][j]>(ll)mp[i][k]+mp[k][j]) mp[i][j]=mp[j][i]=mp[i][k]+mp[k][j];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
rd(n),rd(m),rd(nn),rd(mm);
for(int i=1;i<=n;++i) rd(a[i]);
for(int i=1;i<=n;++i) rd(b[i]);
for(int i=1;i<=n;++i) scanf("%lf",&c[i]);
memset(mp,inf,sizeof(mp));
for(int i=1,u,v,w;i<=mm;++i) rd(u),rd(v),rd(w),mp[u][v]=mp[v][u]=Min(w,mp[u][v]);
floyd();
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;
for (int i=2;i<=n;i++)
for (int j=0;j<=m;j++){
double k1=c[i-1],k2=c[i];
int x=mp[b[i-1]][a[i]],y=mp[b[i-1]][b[i]],z=mp[a[i-1]][a[i]],w=mp[a[i-1]][b[i]];
f[i][j][0]=min(f[i-1][j][1]+k1*x+ (1-k1)*z, f[i-1][j][0] +z);
if(j) f[i][j][1]=min(f[i-1][j-1][0]+k2*w+(1-k2)*z,f[i-1][j-1][1]+k1*k2*y+k1*(1-k2)*x+(1-k1)*k2*w+(1-k1)*(1-k2)*z);
}
for(int i=0;i<=m;++i) ans=Min(ans,Min(f[n][i][0],f[n][i][1]));
printf("%.2lf",ans);
return 0;
}
天天爱跑步
再来一遍我也不太会QAQ 先咕
组合数问题
int t,k,a[2001][2001],ans[2001][2001],n[10001],m[10001];
int main(){
int x=0;
rd(t),rd(k);
for(int i=1;i<=t;++i) rd(n[i],rd(m[i]),x=(n[i]>x)?n[i]:x;
for(int i=1;i<=x;++i) a[1][i]=i%k,ans[1][i]+=(!a[1][i]);
for(int i=2;i<=x;++i)
for (int j=2;j<=i;++j) a[j][i]=(a[j-1][i-1]+a[j][i-1])%k,ans[j][i]+=(!a[j][i]);
for(int i=1;i<=x;++i)
for(int j=1;j<=x;++j) ans[j][i]+=ans[j-1][i]+ans[j][i-1]-ans[j-1][i-1];
for (int i=1;i<=t;i++) printf("%d\n",ans[Min(n[i],m[i])][n[i]]);
}
蚯蚓
首先可以堆实现\(O((n+m)log\ n)\)
注意到,如果不切,那么所有蚯蚓长度大小关系不会变
若在\(t_1\)时刻切下初始长度为\(x\)的蚯蚓,\(t_2\)时刻切下初始长度为\(y\)的蚯蚓,其中\(t_1<t_2,x>y\) 可以知道,\(x\)时刻切下来的蚯蚓初始长度长,增加长度还更多,所以\(x\)时刻切下来的一定比第\(y\)时刻切下来的长 即满足单调性
开三个队列 第一个储存原来的蚯蚓 第二个储存切下来的第一条 第三个储存切下来的第二条
int n,m,q,u,v,t,h1,h2,t2,h3,t3,h4,q1[N],q2[M],q3[M],q4[N+M];
double p;
bool cmp(int x,int y){return x>y;}
int calc(int nw){
int x=q1[h1]+q*nw,y=q2[h2]+q*(nw-h2),z=q3[h3]+q*(nw-h3);
if(n>=h1&&x>=y&&x>=z) return ++h1,x;
else if(h2<=t2&&y>=z) return ++h2,y;
else if(h3<=t3) return ++h3,z;
return -1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
rd(n),rd(m),rd(q),rd(u),rd(v),rd(t),p=1.0*u/(v*1.0);
for(int i=1;i<=n;++i) rd(q1[i]);
sort(q1+1,q1+n+1,cmp);
h1=h2=h3=h4=1,t2=t3=0;
for(int i=0,x,y,z;i<m;++i){
x=calc(i);
if(!((i+1)%t)) printf("%d ",x);
q2[++t2]=y=floor((double)x*p),q3[++t3]=x-y;
}puts("");
while(q4[h4]=calc(m),q4[h4]+1) ++h4;
for(int i=t;i<h4;i+=t) printf("%d ",q4[i]);puts("");
return 0;
}
愤怒的小鸟
状压dp 两个点确定一个过原点的抛物线 预处理出每两个点的抛物线一起可以搞定多少个猪
调试过程告诉我们 平平淡淡才是真 不要试图搞什么骚操作
void qab(double &a,double &b,double x1,double y1,double x2,double y2){
a=(x2*y1-x1*y2)/(x1*x2*(x1-x2)),b=(x1*x1*y2-x2*x2*y1)/(x1*x2*(x1-x2));
}
void pre(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(fabs(x[i]-x[j])<eps) continue;
double a,b;
qab(a,b,x[i],y[i],x[j],y[j]);
if(a>-eps) continue;
for(int k=1;k<=n;k++)
if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps) pw[i][j]|=(1<<(k-1));
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T;rd(T);
for(int i=0,j;i<(1<<18);i++){
for(j=1;j<=18&&(i&(1<<(j-1)));j++);c[i]=j;
}
while(T--){
memset(pw,0,sizeof(pw));
memset(f,inf,sizeof(f));f[0]=0;
rd(n),rd(m);
for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
pre();
for(int i=0,j;i<(1<<n);i++){
j=c[i],f[i|(1<<(j-1))]=min(f[i|1<<(j-1)],f[i]+1);
for(int k=1;k<=n;k++) f[i|pw[j][k]]=min(f[i|pw[j][k]],f[i]+1);
}
printf("%d\n",f[(1<<n)-1]);
}
return 0;
}