牛客2023情人节比赛题解

单身狗给单身狗出的比赛（划掉

本场难度预估： easy：A mid： BCDE hard: FG

A.回眸

知识点：数学

我们首先需要计算小红和小紫相遇所需的时间，然后计算小红剩余的路程，即可算出剩余的时间，把两部分时间加起来即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    double a,v1,v2,v;
    cin>>a>>v1>>v2>>v;
    double t1=a/(v1+v2);
    double d1=v1*t1;
    printf("%.7f",t1+(a-d1)/v);
}

B.暧昧

知识点：乘法原理

对于所有的字符串而言，我们任取两个字符，那么它们相等和不相等的频率一定是相同的。所以我们只需要算出总共 $2^{n}$ 个字符串，任取两个字符有 $C_{n}^{2}$ 种取法，最终除以2即可。答案是 $2^{n-2}*n*(n-1)$

请注意，计算幂的时候需要用快速幂（python语言自带快速幂）

参考代码（python）：

n=int(input())
mod=10**9+7
print(n*(n-1)*pow(2,n-2,mod)%mod)

C.悸动的距离

知识点：计算几何

我们分别统计线段和x轴、y轴是否有交点。当两点横坐标一正一负（或者有0）的时候，线段和x轴有交点。y轴则检验纵坐标。最后，我们需要特判线段是否经过原点。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,d;
    int cc=0;
    cin>>a>>b>>c>>d;
    if(a*c<=0)cc++;
    if(b*d<=0)cc++;
    if(cc==2){
        if(a*d==b*c)cc--;
    }
    cout<<cc;
}

D.光晕

知识点：概率论

由于是环形路，第一个路灯放置的位置没有任何影响。第二个路灯放置的位置有3种情况：

和第一个路灯相邻，那么共照亮了4个位置。共有2个区间满足这个情况。
和第一个路灯相隔1个区间，那么共照亮了5个位置。共有2个区间满足这个情况。
剩下的情况都是照亮6个位置。共有n-5个区间满足这个情况。

因此答案是 $4*\frac{2}{n-1}+5*\frac{2}{n-1}+6*\frac{n-5}{n-1}$

请注意，这里的除法需要用乘以逆元来代替。

对于 $n \leq 4 n≤4$ 的情况，我们理应进行特判，但实际套用公式后发现，计算的结果和预期是一样的。

参考代码：

n=int(input())
mod=10**9+7
print(((n-5)*6+2*4+2*5)*pow(n-1,mod-2,mod)%mod)

E 暖色记忆

知识点：贪心

本题容易想到的一个tip是：由于任何小于1e9的正整数除了32次2一定变成0，所以对于比较大的数组，最终一定绝大多数都是0，其余一些数是除了若干次2的。那么一个比较显然的贪心就是，让最大值除1次2，倒数第二大值除2次2，以此类推……直到除2的次数超过32次或者已经选了一半的数为止。

参考代码（stl写法，可以练习set的用法，本题也可以直接排序）：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[303030];
    int n;
    cin>>n;
    multiset<int>s;
    for(int i=0;i<n;i++)cin>>a[i],s.insert(a[i]);
    int res=0,cnt=1;
    while(s.size()&&cnt<=min(31,n/2)){
        res+=(*s.rbegin()/(1LL<<(cnt++)));
        s.erase(prev(s.end()));
    }
    cout<<res;
}

F.灰音

知识点：动态规划

我们定义 $d p [i] [j] [k]$ 代表：前 $i$ 个数，平滑值为 $j$ ，且最后一个数为 $k$ 的方案数，那么可以 $O (n^{4})$ 转移出所有情况。详细见参考代码。看榜上有许多大佬用 $O (n^{3})$ 过的，吊打出题人系列。实测 $O (n^{4})$ c++语言300ms~700ms左右，python语音1800ms左右，而本题开了2s/4s，理论上不会被卡常。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[3][3]={};
int dp[101][101][101];      //前i个 平滑值为j 最后一个为k
int mod=1e9+7;
int res[101];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _=1;
  //  cin>>_;
    while(_--){
        int n,i,j,k,t,x,z;
        cin>>n;
        for(i=1;i<=n;i++)dp[1][0][i]=1;
        for(i=2;i<=n;i++){
            for(j=0;j<n;j++){
                for(k=1;k<=n;k++){
                    for(z=1;z<=n;z++){
                        dp[i][max(j,abs(k-z))][k]+=dp[i-1][j][z];
                        dp[i][max(j,abs(k-z))][k]%=mod;
                    }
                    
                }
            }
        }
        for(i=1;i<=n;i++){
            for(j=0;j<n;j++){
                res[j]+=dp[n][j][i];
                res[j]%=mod;
            }
        }
        for(i=0;i<n;i++)cout<<res[i]<<"\n";
        
    }
}

G.难了

知识点：筛

首先我们需要知道一个性质， $a / b$ 是无限循环小数（ $a$ 和 $b$ 互素）的充要条件是： $b$ 包含了2和5以外的素因子。因此，本题可以先处理掉所有的2和5，然后直接在欧拉筛中筛出所有 $a_{j}$ 是 $a_{i}$ 倍数的情况，其余情况则一定会产生无限循环小数。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,x,i,j;
    long long m[202020]={};
    cin>>n;
    long long res=n*(n-1);
    while(n--){
        cin>>x;
        while(x%2==0)x/=2;
        while(x%5==0)x/=5;
        m[x]++;
    }
    
    for(i=1;i<=2e5;i++){
        for(j=i*2;j<=2e5;j+=i){
            res-=m[i]*m[j];
        }
    }
    for(i=1;i<=2e5;i++)res-=m[i]*(m[i]-1);
    cout<<res;
}

希望没有npy的大家，可以在本场比赛中学到算法，~~卷死那些现充们！！！~~ #^#