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

本场难度预估： 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}2^n$个字符串，任取两个字符有$C_n^{2}C\_n^2$种取法，最终除以2即可。答案是$2^{n-2}\ast n\ast (n-1)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种情况：

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

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

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

对于$n\le 4n\le 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.灰音

知识点：动态规划

我们定义$dp[i][j][k]dp[i][j][k]$代表：前$ii$个数，平滑值为$jj$，且最后一个数为$kk$的方案数，那么可以$O(n^4)O(n^4)$转移出所有情况。详细见参考代码。 看榜上有许多大佬用$O(n^3)O(n^3)$过的，吊打出题人系列。 实测$O(n^4)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\mathrm{/}ba/b$是无限循环小数（$aa$和$bb$互素）的充要条件是：$bb$包含了2和5以外的素因子。因此，本题可以先处理掉所有的2和5，然后直接在欧拉筛中筛出所有$a_{j}a\_j$是$a_{i}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的大家，可以在本场比赛中学到算法，卷死那些现充们！！！ #^#