Alice and Bob

题目链接:

题意:

总共有两堆石头,每次可以从一堆中取走 $k$ $(k > 0)$ 块石头,从另一堆取走 $s ? k$ $(s > = 0)$ 块石头, 不能操作的人输

题解:

用一个二维数组 $f [i] [j]$ 储存状态, $f [i] [j]$ 为 $1$ 代表有两堆石头分别有 $i, j$ 块的时候先手必胜,为 $0$ 代表先手必败

可以发现一个状态 $(i, j)$ 如果为先手必败态, 则上一个状态 $(i + k, j + s ? k)$ 一定为先手必胜态, 则对于每一个必败状态,枚举寻找 $k, s$

码来!

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+10;
bool f[N][N];
void init()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(f[i][j]==0)
            {
                for(int k=1;k+i<N;k++)
                {
                    for(int s=0;s*k+j<N;s++)
                    {
                        int xx=k+i;
                        int yy=s*k+j;
                        if(xx<yy) swap(xx,yy);
                        f[xx][yy]=1;
                    }
                }
                for(int k=1;k+j<N;k++)
                {
                    for(int s=0;s*k+i<N;s++)
                    {
                        int xx=k+j;
                        int yy=s*k+i;
                        if(xx<yy) swap(xx,yy);
                        f[xx][yy]=1;
                    }
                }
            }
        }
    }
}
int main()
{
    init();
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        if(n<m) swap(n,m);
        if(f[n][m]) cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
 
    return 0;
}

Ball Dropping

题目链接:

题意:

一个球体在等腰梯形中,落下请确定球是否会卡在梯形中。如果答案是“卡住”，请同时计算卡住位置（球心与底面中点之间的高度）。

题解:

在这里插入图片描述
如图:

可知,绿色三角形的斜边可以计算, 同时绿色三角形与黄色三角形相似, 则黄色三角形的三边可以计算得到

得到黄色三角形的斜边 $y$ ,已知 $z$ 部分为 $b / 2$ , 则可计算 $x$ 部分的值

则以 $x$ 边和粉色边组成的三角形又与绿色三角形相似,可得到粉色边的值,即为答案

码来!

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int r,a,b,h;
    cin>>r>>a>>b>>h;
    if(2*r<b) cout<<"Drop"<<endl;
    else
    {
        double s=sqrt(h*h+((a-b)/2.0)*((a-b)/2.0));
        double y=r*s/h;
        double x=y-b/2.0;
        double ans=2.0*h*x/(a-b)*1.0;
        cout<<"Stuck"<<endl;
        printf("%.8f\n",ans);
    }
    return 0;
    
}