解析试卷： 2020校招4399游戏开发岗笔试编程题

A 题意：

思路：

是简单模拟题，注意审题是说n次落地时共经过了多少米，所以要算上之前一次反弹的高度。

代码：

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n,i,j,t;
    cin>>n;
    double s1=100,s2=0,pre=0;
    while(n--)
    {
        s2+=s1;
        s2+=pre;
        s1/=2.0;
        pre=s1;
    }
    cout<<fixed<<setprecision(6)<<s2<<" "<<s1<<endl;
    return 0;
}

B
题意：
有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。
思路：
双端队列模拟操作，每次直接跳出一个，复杂度是O(n)
代码：

#include<bits/stdc++.h>

using namespace std;

int main()
{
    deque<int >name;
    int n,i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        name.push_back(i);
    }
    while(name.size()!=1)
    {
        if(name.size()>=3)
        {
            int d1=name.front();
            name.pop_front();
            int d2=name.front();
            name.pop_front();
            name.pop_front();
            name.push_back(d1);
            name.push_back(d2);
        }
        else
        {
            if(name.size()==2){
                name.pop_front();
                cout<<name.front()<<endl;
                name.pop_front();
                break;
            }
        }
    }
    if(name.size()==1){
        cout<<name.front()<<endl;
    }
    return 0;
}

C :小陆每天要写一份工作日报，日报标题含有日期。几年后，他翻开以前的日报，想知道两份日报的日期是否同为星期几，请编程帮助他判断。
思路：
可以模拟，也可以直接用基姆拉尔森计算公式

W = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) mod 7

D ：段誉身具凌波微波，动无常则，若危若安，一次能走一级台阶或者两级台阶，他要爬一段30级的山路，问有多少种走法？分析如何计算，然后编程解答。
进阶问题：当他轻功熟练度提升，一次最多可以走三级，那就结果有什么变化？后来走火入魔了，不能走一级，只能走二或三级，又有什么变化？

思路：
简单DP，for循环跑三次，第i级台阶只有可能来自于i-1,i-2,i-3，模拟即可

#include<bits/stdc++.h>

using namespace std;

const int mx=35;
int dp1[mx];
int dp2[mx];
int dp3[mx];
int main()
{
    int n,i,j,t,ans1,ans2,ans3;
    cin>>n;
    dp1[0]=1;
    for(i=1;i<=n;i++)
    {
        if(i-1>=0) dp1[i]+=dp1[i-1];
        if(i-2>=0) dp1[i]+=dp1[i-2];
    }
    dp2[0]=1;
    for(i=1;i<=n;i++)
    {
        if(i-1>=0) dp2[i]+=dp2[i-1];
        if(i-2>=0) dp2[i]+=dp2[i-2];
        if(i-3>=0) dp2[i]+=dp2[i-3];
    }
    dp3[0]=1;
    for(i=1;i<=n;i++)
    {
        if(i-2>=0) dp3[i]+=dp3[i-2];
        if(i-3>=0) dp3[i]+=dp3[i-3];
    }
    cout<<dp1[n]<<" "<<dp2[n]<<" "<<dp3[n]<<endl;
    return 0;
}