2018-ccpc-吉林

第二场被爆锤

D - The Moon

题意：

现有一游戏，他的胜率为$p$，抽到奖品的概率为$q$初始为$2\%$。若获得游戏胜利，抽到奖品则结束游戏，没抽到则$q$变为$min(100\%,q+2\%)$，然后继续游戏；若游戏失败，则$q$变为$min(100\%,q+1.5\%)$，然后继续游戏。求需要玩的游戏场数的期望。

题解：

很容易想到的就是概率$dp$和记忆化$dfs$，以下我用概率$dp$阐述。

由于数组的下标不能是小数，则我们需要把$q$变成两倍进行计算。

那么这就是一个几何概型的概率，则初始的$dp[200]=\frac{1}p$，当前局的期望为$1$（当前局）$+p\star(1-\frac{1.0\star i}{200})\star dp[min(200,i+4)]$（赢了但是没拿到）$+(1-p)\star dp[min(200,i+3)]$（没赢）。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define endl '\n'
using namespace std;
typedef long long ll;

double dp[205];
signed main() {
  int T;cin>>T;
  _for(_,1,T+1){
    double p;cin>>p;p/=100;
    memset(dp,0,sizeof(dp));
    dp[200]=1/p;
    _rfor(i,199,3){
      dp[i]=1,
      dp[i]+=p*(1-1.0*i/200)*dp[min(i+4,200)],
      dp[i]+=(1-p)*dp[min(i+3,200)];
    }
    printf("Case %d: %.10lf\n",_,dp[4]);
  }
  return 0;
}

E - The Tower

题意：

有一三维直角坐标系，现在有一个底部圆心在$(0,0,0)$的圆锥高为$h$，底部半径为$R$，和一个在$(x_0,y_0,z_0)$的点，以$(v_x,v_y,v_z)$的速度运动，问这个点什么时候会撞上圆锥。

题解：

设表面到底部圆心的距离为$r$,

圆锥的表面曲线公式有

$$\left\{\begin{array}{} \frac{h-z}{h}=\frac{R}{r}\\ x^2+y^2=R^2 \end{array} \right.$$

点随时间$t$的运动公式

$$\left\{\begin{array}{} x=x_0+v_x*t\\ y=y_0+v_y*t\\ z=z_0+v_z*t \end{array} \right.$$

联立两者可得

$$(v_x^2+v_y^2-\frac{r^2v_z^2}{h^2})t^2+2(v_xv_0+v_yv_0-\frac{z_0v_zr^2}{h^2}+\frac{v_zr^2}{h})t+x_0^2+y_0^2-\frac{r^2}{h^2}(h-z_0)^2=0$$

把除法部分化简可得

$$(v_x^2h^2+v_y^2h^2-r^2v_z^2)t^2+2(v_xv_0h^2+v_yv_0h^2-z_0v_zr^2+v_zr^2h)t+x_0^2h^2+y_0^2h^2-r^2(h-z_0)^2=0$$

最后用求根公式得出两个解，判断一下是否成立即可。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
double r,h,x,y,z,vx,vy,vz;
int check(double t){
  double xx=x+vx*t,
  yy=y+vy*t,
  zz=z+vz*t;
  if(zz>=0&&zz<=h&&(xx*xx+yy*yy)<=r*r)return 1;
  return 0;
}
signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    cin>>r>>h;
    cin>>x>>y>>z;
    cin>>vx>>vy>>vz;
    double a=vx*vx*h*h+vy*vy*h*h-r*r*vz*vz,
    b=2*(vx*x*h*h+vy*y*h*h-z*vz*r*r+vz*r*r*h),
    c=x*x*h*h+y*y*h*h-r*r*((h-z)*(h-z));
    double ans=LLONG_MAX;
    double t1=(-b+sqrt(b*b-4*a*c))/(2*a),
    t2=(-b-sqrt(b*b-4*a*c))/(2*a);
    if(check(t1))ans=min(ans,t1);
    if(check(t2))ans=min(ans,t2);
    cout<<"Case "<<_<<": ";
    cout<<fixed<<setprecision(10)<<ans<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/16/2018-ccpc-吉林/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！