注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

HUST Warm up 2012-5-12 An easy Bangladeshi Contest  

2012-05-14 20:40:15|  分类: 比赛总结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     
       周六做的一场训练赛,有几道题蛮有意思,简单的记录一下吧。
       
       这题要用到数学分析的知识——拉格朗日乘数法。大一下的时候学过,不过早都忘光了,所以比赛的时候悲剧了,打死都想不到用这种东西,后来问别人才知道咋做。把每个区间前进的dx作为参数,一共n个,可以得到关于时间的函数f(x1,x2,……,xn)和约束方程g(x1,x2,……,xn)=0。然后设h(x1,x2,……,xn,t)=f(x1,x2,……,xn)-t*g(x1,x2,……xn)。用拉格朗日乘数法可以得到n+1个等式。最后化简为关于t的等式: sum{100/vi/(1-t*t*vi*vi)}=D,1<=i<=n。二分100次就可以得出正确的答案。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,d,s[100];
double cal(double p){
double t=0;
for(int i=0;i<n;i++) t+=100*p*s[i]/sqrt(1.0-p*p*s[i]*s[i]);
return t;
}
int main(){
int T,cas=0;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&d);
for(int i=0;i<n;i++) scanf("%d",s+i);
sort(s,s+n);
double l=0,r=1.0/s[n-1],mid;
for(int run=0;run<50;run++){
if(cal(mid=(l+r)/2)>d) r=mid;
else l=mid;
}
double ans=0;
for(int i=0;i<n;i++) ans+=100.0/s[i]/sqrt(1-mid*mid*s[i]*s[i]);
printf("Case %d: %.12lf\n",++cas,ans);
}
}



       其实这题不难,但由于题意太坑所以没几个人做出来。就是给一些关于x、y的线性限制,求满足条件的整点个数,如果是任意限制,那么就不好做了,但这题的限制区间是一个平行四边形,并且直线的方程很特殊,所以可以直接推公式。

#include<cstdio>
#define ll long long
int main(){
ll r,t,n,ans;
while(scanf("%lld%lld%lld",&r,&t,&n),r){
if(t<r||t>n*r) puts("0");
else{
ll x1=(t-r)/(n-1);
ll x2=(n*r-t)/(n-1);
printf("%lld\n",((n-1)*x1+2)*(x1+1)/2+((n-1)*(r-x2-1)+2)*(r-x2)/2+(x2-x1)*(t-r+1)-2);
}
}
}


       
       二维版的阶梯nim,但是我们连一维的都不会,所以跪了。知道一维的做法,二维的很快就推出来了,sg函数值为所有x、y异奇偶的位置的硬币数相异或的值,用归纳法可以证明。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(){
int T,cas=0,r,c,t,x;
cin>>T;
while(T--){
cin>>r>>c;
x=0;
for(int i=r-1;i>=0;i--)
for(int j=c-1;j>=0;j--){
cin>>t;
if((i&1)!=(j&1)) x^=t;
}
cout<<"Case "<<++cas<<": ";
x?puts("win"):puts("lose");
}
}



       数位DP,一直对数位DP无爱,写起来感觉各种不爽,比赛的时候硬着头皮写这题,期间又是各种脑残错误,还好最后AC了。要两个方程,一个记录个数,一个记录和。然后数位统计就行了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int dp[33][33][33][3][7];
long long sum[33][33][33][3][7];
void init_dp(int maxone,int ideal,int K){
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
dp[0][0][0][0][0]=1;
for(int i=0;i<31;i++)
for(int k=0;k<=K;k++)
for(int one=0;one<=maxone;one++)
for(int l3=0;l3<3;l3++)
for(int l7=0;l7<7;l7++){
int t=dp[i][k][one][l3][l7];
dp[i+1][k+((ideal&(1<<i))?1:0)
][one][l3][l7]+=t;
dp[i+1][k+((ideal&(1<<i))?0:1)
][one+1][(l3+(1<<i))%3][(l7+(1<<i))%7]+=t;

long long ts=sum[i][k][one][l3][l7];

sum[i+1][k+((ideal&(1<<i))?1:0)
][one][l3][l7]+=ts;

sum[i+1][k+((ideal&(1<<i))?0:1)
][one+1][(l3+(1<<i))%3][(l7+(1<<i))%7]+=ts+1ll*t*(1<<i);

}
for(int i=0;i<31;i++)
for(int k=0;k<=K;k++)
for(int one=0;one<=maxone;one++)
for(int l3=0;l3<3;l3++)
for(int l7=0;l7<7;l7++){

}
}
long long cal(int x,int maxone,int ideal,int K){
long long ret=0;
int t=0;
if(x<=0) return 0;
for(int i=30;i>=0;i--){
if(x&(1<<i)){
int tk=K,t3=(t<<(i+1))%3,t7=(t<<(i+1))%7;
if(ideal&(1<<i)) tk--;
for(int k=0;k<=tk;k++)
for(int j=0;j<=maxone;j++)
for(int l=0;l<7;l++)
if((l+t7)%7)
ret+=1ll*(t<<(i+1))*dp[i][k][j][(3-t3)%3][l]+sum[i][k][j][(3-t3)%3][l];
}
t=t<<1|((x&(1<<i))?1:0);
if(x&(1<<i)) maxone--;
if(maxone<0) break;
if((x&(1<<i))!=(ideal&(1<<i))) K--;
if(K<0) break;
}
if(maxone>=0&&K>=0&&x%3==0&&x%7) ret+=x;
return ret;
}

int main(){
// freopen("in.in","r",stdin);
int cas=0,T;
cin>>T;
while(T--){
int start,end,maxone,ideal,K;
cin>>start>>end>>maxone>>ideal>>K;
maxone=min(maxone,31);
K=min(K,31);
init_dp(maxone,ideal,K);
cout<<"Case "<<++cas<<": ";
cout<<cal(end,maxone,ideal,K)-cal(start-1,maxone,ideal,K)<<endl;
}
return 0;
}




很有意思的概率题,过的人很少,yh很犀利的AC了。我一开始看数据范围不大,所以老想DP,但没有什么好的想法,所以就先放着了。后来yh换一种思路做,推出了公式,但由于一点小Bug,直到4个小时的时候才AC。可以先考虑出去时贡献的罚时的期望=sum1/cnt1,其中sum1为所有能出去的门的罚时之和,cnt1为个数。再考虑第一次没有出去时所有罚时的期望=sum2/n,第二次没有出去时所有罚时的期望=sum2*(cnt2-1)/n/(n-1),第三次没有出去时所有罚时的期望=sum2*(cnt2-1)*(cnt2-2)/n/(n-1)/(n-2)……一直到第K次=sum2*(cnt2-1)*(cnt2-2)……*(cnt2-K+1)/n/(n-1)……/(n-K+1),再往后推,我们发现期望是一个等比数列。所有的期望相加取极限就是答案了。

#include<cstdio>
int main(){
int T,cas=0,n,K;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&K);
int c1=0,s1=0,c2=0,s2=0;
double ans;
for(int i=0;i<n;i++){
int t;
scanf("%d",&t);
if(t>0) c1++,s1+=t;
else c2++,s2+=-t;
}
if(!c1) ans=-1;
else
{
ans=1.0*s1/c1;
double t=1.0;
for(int i=0;i<K&&i<c2;i++) t*=1.0*(c2-i)/(n-i),ans+=t*s2/c2;
if(c2>K) ans+=t*s2*(c2-K)/(n-K)/c2/(1-1.0*(c2-K)/(n-K));
}
printf("Case %d: %.3lf\n",++cas,ans+1e-9);
}
}


  评论这张
 
阅读(129)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017