4.16 360 笔试编程题 技术B卷

第一题

给定n个人，每个人有能力值，是一个排列，每次第一个人和第二个人比赛，
输的一方会放在最后面，当有一个人连续赢了m场比赛结束，
问总共经过几场比赛。 。
按题意deque 模拟。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
int n,m;
int a[N]={0};
deque<int>q;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int u;sc("%d",&u);
        q.push_back(u);
        a[u]=0;
    }
    if(n==1)return O(m);
    int ans=0;
    while(true){
        int t=q.front();
        if(t==n)break;
        q.pop_front();
        int k=q.front();
        q.pop_front();
        ans++;
        if(t<k){
            a[t]=0;
            a[k]++;
            if(a[k]==m){
                return O(ans);
            }
            q.push_back(t);
            q.push_front(k);
        }else {
            a[k]=0;
            a[t]++;
            if(a[t]==m){
                return O(ans);
            }
            q.push_back(k);
            q.push_front(t);
        }
    }
    return O(ans+m-a[n]);   
}

第二题
给你一个,一个。

,

问你的概率是多少。
简单概率dp,设 表示 的区间是的概率，按照题目意思转移就行。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
double dp[105][105]={0};
int main(){
    int n,a0;
    sc("%d%d",&n,&a0);
    for(int i=0;i<=a0;i++)dp[1][a0-i]=1.0/(1+a0);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=a0;j++){
            for(int k=0;k<=j;k++){
                dp[i+1][j-k]+=dp[i][j]*(1.0/(1+j));
            }
        }
    }
    pr("%.5f\n",dp[n][0]);
}