07-24 15:22 已编辑河南农业大学算法工程师发布于河南

关注

河南萌新联赛2025第（二）场：河南农业大学_题解

本场榜单歪了，F题定位最难的那档但是被很多大佬过掉了。

C、D题题面难以理解也给大家带来了不好的体验。

这场有太多数学题，预估难度较低，但是实际看下来难度高了。

抱歉给大家带来了不好的参赛体验。

预估难度：

简单：K I M D
中等：E C B A L
较难：H G
困难：J F

A 约数个数和

$\sum^n_{i=1}d(i)=\sum^n_{i=1}\lfloor\frac{n}{i}\rfloor$ 数论分块求和即可

#include "bits/stdc++.h"
#define endl '\n'
using ll=long long;
using namespace std;

int main(){
    int n;
    cin>>n;
    ll ans=0;
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans+=(j-i+1ll)*(n/i);
    }
    cout<<ans<<endl;
    return 0;
}

B 异或期望的秘密

定义函数 $\text{count}(k, X)$ 表示在区间 $[0, X]$ 中第 $k$ 位为 1 的数的个数。

\text{count}(k, X) = \left\lfloor \frac{X + 1}{2^{k+1}} \right\rfloor \cdot 2^k + \max\left(0, (X + 1) \mod 2^{k+1} - 2^k\right)

那么区间 $[l, r]$ 中第 $k$ 位为 1 的数目为： $\text{count}_1 = \text{count}(k, r) - \text{count}(k, l - 1)$

若 $y$ 的第 $k$ 位为 1，则贡献为区间中该位为 0 的数的比例： $\frac{(r - l + 1) - \text{count}_1}{r - l + 1}$

若 $y$ 的第 $k$ 位为 0，则贡献为区间中该位为 1 的数的比例： $\frac{\text{count}_1}{r - l + 1}$

将所有二进制位的贡献相加，得到期望值。

#include"bits/stdc++.h"
#define endl '\n'
using ll=long long;
using namespace std;

constexpr int N=1e5+10;

struct Mint{...};

int count(int k,int X){
    return (X+1)/(1<<k+1)*(1<<k)
        +max(0,(X+1)%(1<<k+1)-(1<<k));
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        int l,r,y;
        cin>>l>>r>>y;

        Mint ans;
        for(int k=30;k>=0;k--){
            if(y>>k&1)
                ans+=(Mint(r-l+1)-(count(k,r)-count(k,l-1)))/(r-l+1);
            else
                ans+=Mint(count(k,r)-count(k,l-1))/(r-l+1);
        }
        cout<<ans<<endl;

    }

    return 0;
}

C O神

先用背包处理花 $i$ 元最多能得到多少原石 $dp_i$ ，再计算出抽 $i$ 抽最少要充值多少钱 $c_i$ ，然后算出第 $i$ 抽抽出的概率 $P_i$ ，答案就是 $\sum^m_{i=1} c_i \times P_i$ 。

#include "bits/stdc++.h"
#define endl '\n'
using ll = long long;
using namespace std;
#define int long long
constexpr int mod = 1e9 + 7;
ll qpow(ll a, ll b, ll p)
{
    a %= p;
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int a[200];
int b[200];
int c[200];
void solve()
{
    int n, p, q, m, x;
    cin >> x >> p >> q >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    vector<int> dp(2001, 0);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 2000; j >= a[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
        }
    }
    int now = 0;
    for (int i = 1; i <= m; i++)
    {
        while (dp[now] < x * i)
            now++;
        c[i] = now;
    }
    int ans = 0;
    int p1 = p * qpow(q, mod - 2, mod) % mod;
    int q1 = ((1 - p1) % mod + mod) % mod;
    now = 1;
    for (int i = 1; i < m; i++)
    {
        ans += (c[i] * p1 % mod * now % mod);
        ans %= mod;
        now *= q1;
        now %= mod;
    }
    ans += (now * c[m] % mod);
    ans %= mod;
    cout << ans << endl;
}
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}

D 开罗尔网络的备用连接方案

以1为根节点dfs遍历这棵树每经过一个节点就记录其二进制1的个数

#include "bits/stdc++.h"
#define endl '\n'
using ll = long long;
using namespace std;

#define int long long
vector<int> arr[100001];
int a[100001];
int cnt[60];
void dfs(int u, int fa, int now)
{
    int cc = 0;
    for (int i = 0; i <= 32; i++)
    {
        if (now >> i & 1)
            cc++;
    }
    cnt[cc]++;
    for (auto v : arr[u])
    {
        if (v != fa)
        {
            dfs(v, u, now & a[v]);
        }
    }
}
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        arr[u].push_back(v);
        arr[v].push_back(u);
    }

    dfs(1, 0, a[1]);
    while (m--)
    {
        int x;
        cin >> x;
        cout << cnt[x] << endl;
    }
}
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}

E 咕咕嘎嘎!!!(easy)

本题数据较小，有多种解法。

说一个比较容易理解的dp做法设 $dp_{i,j}$ 为选了 $j$ 个数他们 $\gcd$ 为 $i$ 的方案数，那么我们就可以用类似背包的转移来解决这道题。

#include"bits/stdc++.h"
using namespace std;

constexpr int N=5e3+10,mod=1e9+7;

int dp[N][N];

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        (dp[i][1]+=1)%=mod;
        for(int g=1;g<i;g++){
            for(int j=m;j>=2;j--){
                (dp[gcd(g,i)][j]+=dp[g][j-1])%=mod;   
            }
        }
    }
    int ans=0;
    for(int g=2;g<=n;g++)
        (ans+=dp[g][m])%=mod;
    cout<<ans;

    return 0;
}

F 咕咕嘎嘎!!!(hard)

定义 $g(e)$ 为选定的 $m$ 个数的最大公因数恰好为 $e$ 的方案数， $f(e)$ 为选定的 $m$ 个数都是 $e$ 的倍数的方案数。

$f(e)$ 等价于选定的 $m$ 个数的最大公因数是 $e$ 的倍数的方案数。

由定义得：

f(e)=\dbinom{\lfloor n/e\rfloor}{m}

显然， $f(n)=\sum_{n|d}g(d)$ 。由莫比乌斯反演得： $g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)$ ，即 $g(e)=\sum^{\lfloor n/e\rfloor}_{d=1}\mu(d)f(ed)$ 。

那么

\begin{align*} ans&=\sum^{n}_{e=2}g(e)\\ &=\dbinom{n}{m}-g(1)\\ &=f(1)-\sum^{n}_{d=1}\mu(d)f(d)\\ &=f(1)-(\mu(1)f(1)+\sum^{n}_{d=2}\mu(d)f(d))\\ &=-\sum^{n}_{d=2}\mu(d)f(d)\\ &=-\sum^{n}_{d=2}\mu(d)\dbinom{\lfloor n/d\rfloor}{m} \end{align*}

预处理莫比乌斯函数和组合数后，即可 $O(n)$ 时间复杂度得到答案。

然而， $O(n)$ 可能会因为常数过大难以通过本题。充分发扬人类智慧，上界可以从 $n$ 变成 $\lfloor n/m\rfloor$ （大于此值的最大公约数不可能出现，因为这样的数不存在 $m$ 个），特判 $m=1$ 的情况，把莫比乌斯的求解常数降低至少一半。

#include"bits/stdc++.h"
#define endl '\n'
using ll=long long;
using namespace std;
constexpr int N=4e7+10,mod=1e9+7;

vector<int>p;
bool flg[N];
int mu[N],pmu[N];
void getmu(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!flg[i]){
            p.push_back(i);
            mu[i]=-1;
        }
        for(int pj:p){
            if(i*pj>n)
                break;
            flg[i*pj]=true;
            if(i%pj==0){
                mu[i*pj]=0;
                break;
            }
            mu[i*pj]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++)
        pmu[i]=pmu[i-1]+mu[i];
}

int fact[N],inv[N];
ll qpow(ll a,ll b,ll p){
    a%=p;
    ll ans=1%p;
    for(;b;b>>=1){
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}
void init(){
    fact[0]=1;
    inv[0]=1;
    for(int i=1;i<N;i++)
        fact[i]=(ll(i)*fact[i-1])%mod;
    inv[N-1]=qpow(fact[N-1],mod-2,mod);
    for(int i=N-2;i>=1;i--){
        inv[i]=inv[i+1]*(i+1ll)%mod;
    }
}
ll C(ll n,ll r){
    if(r>n||r<0)
        return 0;
    if(n==r||r==0)
        return 1;
    return (ll(fact[n])*inv[r]%mod*inv[n-r]%mod);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    init();
    int n,m;
    cin>>n>>m;
    if(m==1){
        cout<<n-1;
        return 0;
    }
    getmu(n/m);
    ll ans=0;
    for(int i=2;i<=n/m;i++)
        ans=(ans-(mu[i]*C(n/i,m)%mod)+mod)%mod;
    cout<<ans;

    return 0;
}

G yume的灵机一动

联想树形dp， $dp_{u,j}$ 表示第 $u$ 个节点选择 $j$ 个叶子节点的最大价值，枚举 $u$ 的子节点 $i$ ，设在 $i$ 节点中选取 $k$ 个叶子节点有转移方程：

dp_{u,j} = max(dp_{u,j} \, ,\,dp_{u,j - k} + dp_{i,k})

易知时间复杂度为 $O(n^3)$ ，发现可以使用树上背包优化，因此题目实际复杂度为 $O(nk)$ 。

#include"bits/stdc++.h"
#define endl '\n'
using ll=long long;
using namespace std;
constexpr int N=42000+4,M=5500+4;
constexpr int inf=0X3F3F3F3F;
constexpr ll INF=0X3F3F3F3F3F3F3F3F;

int n,k;
int dp[N][M],siz[N],a[N];
vector<int>g[N];
void dfs(int u,int p){
    if(u!=1&&g[u].size()==1){
        siz[u]++;
        dp[u][1]=a[u];
        return;
    }

    for(auto v:g[u]){
        if(v==p)
            continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
    
    if(siz[u]<=k){
        dp[u][siz[u]]+=a[u];
        for(auto v:g[u]){
            if(v==p)
                continue;
            dp[u][siz[u]]+=dp[v][siz[v]];
        }
    }

    int W=min(siz[u]-1,k);
    for(auto v:g[u]){
        if(v==p)
            continue;
        for(int i=W;i>=1;i--){
            for(int j=1;j<=min(siz[v],k);j++){
                if(i-j>=0)
                    dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v][j]);
            }
        }
    }
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    cout<<dp[1][k]<<endl;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    // int _=1;cin>>_;while(_--)
    solve();
    return 0;
}

H 被无尽数字1环绕

对于 “ $[0,n]$ 范围内二进制下 $1$ 的个数为 $m$ 的数有多少个 ” 这个问题，可以通过类似数位dp的思想来解决。那么找到最小的数 $x$ 使得 “ $[0,x]$ 范围内二进制下 $1$ 的个数为 $m$ 的数有 $k$ 个 ”，这个 $x$ 即为答案，可以使用二分查找求解。

“ $[0,n]$ 范围内二进制下 $1$ 的个数为 $m$ 的数有多少个 ”：在二进制下从高位到低位遍历： $i$ 位之前的位数的值跟 $n$ 保持一致， $n$ 的第 $i$ 位为 $1$ 时，可以将这一位设置为 $0$ ，那么后续的位数就可以随意设置，利用组合数求解贡献。假设后续有 $len$ 位， $i$ 之前的位数有 $cnt$ 个 $1$ ，那么当前造成的贡献就是 $\dbinom{len}{m-cnt}$ 。注意，这个方法算的是小于 $n$ 的贡献，需要把 $n$ 的贡献加上。

#include <bits/stdc++.h>
#define endl '\n'
using ll = long long;
using namespace std;

ll n,m,k;
ll C[61][61];
bool check(ll lim){
    int cnt=0;
    ll res=0;
    for(int i=60;i>=0;i--){
        if(lim>>i&1){
            if(cnt<=m)
                res+=C[i][m-cnt];
            cnt++;
        }
    }
    if(cnt==m)
        res++;
    return res>=k;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    for(int i=0;i<=60;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        ll l=0,r=n+1;
        while(l<r){
            ll mid=(l+r)/2;
            if(check(mid))
                r=mid;
            else
                l=mid+1;
        }
        cout<<(l==n+1?-1:l)<<endl;
    }
    return 0;
}

I 猜数游戏easy

通过每次猜数得到的大小关系我们可以不断二分去缩短区间，所以答案就是二分的次数

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ll n;
    cin >> n;
    for(int i=0;i<=64;i++)
    {
        if((1ll<<i)>=n)
        {
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

J 猜数游戏hard

假设我们猜测的数字是 $x$ ，那么答案数字 $ans$ 如果落入区间 $[x/k,k*x]$ 都算我们猜测成功。

这启发我们可以把值域划分成一段段区间，区间中心点掌管这个区间答案。

区间 $[1,k*k]$ 猜 $k$ ，区间 $[k*k+1,(k*k+1)*k*k]$ 猜 $(k*k+1)*k$

构造数组 $a$ ： $a_1=1\,\,,\,a_i=k*k*a_{i-1}+1$ ，其中 $a_i$ 是每个区间左端点，直到 $n < a_i$ ，构造完毕。

这样对于每个 $a_i$ 所对应区间，我们只需要猜 $k*a_i$ 即可，对数组二分即可达到最优猜测，答案就是二分次数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ll n, k;
    cin >> n >> k;
    // 【1，k*k】猜k
    // 【k*k+1,(k*k+1)*k*k】猜(k*k+1)*k
    // 【(k*k+1)*k*k+1】
    /*
        a1=1;
        ai=k*k*ai-1+1
        y=k*ai
    */
    ll cnt = 1;
    __int128_t res = 1;
    for (int i = 1; i <= 64; i++)
    {
        res = res*k * k+ 1;
        if (res > n)
            break;
        cnt++;
    }
    if(k==1)
        cnt=n;
    // cout<<cnt<<endl;
    for (int i = 0; i <= 64; i++)
    {
        if ((1ll << i) >= cnt)
        {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

K 打瓦

直接输出gugugaga即可

#include"bits/stdc++.h"
using namespace std;
int main(){
    cout<<"gugugaga";
    return 0;
}

L 分块高手彻底怒了

本题出题人初始的解法需要用到数论分块，后来发现不需要。如果不是忘记之前的解法，出题人可能不会发现简单做法，这也是题目标题的由来（笑）。

以下为简单做法题解

\begin{aligned} 原式 &= \sum^{n}_{i=1}\sum^{n}_{j=i}\sum^{n}_{k=j}(\frac{a_i}{b_j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{j}\rfloor\lfloor\frac{n}{k}\rfloor) \ +\ \sum^{n}_{k=1}\sum^{k}_{j=1}\sum^{j}_{i=1}c_k \\ &= \sum^{n}_{i=1}\sum^{n}_{j=i}\sum^{n}_{k=j}(\frac{a_i}{b_j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{j}\rfloor\lfloor\frac{n}{k}\rfloor) \ +\ \sum^{n}_{k=1}\sum^{k}_{j=1}j c_k \\ &= \sum^{n}_{i=1}\sum^{n}_{j=i}\sum^{n}_{k=j}(\frac{a_i}{b_j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{j}\rfloor\lfloor\frac{n}{k}\rfloor) \ +\ \sum^{n}_{k=1}\frac{k(k+1)}{2} c_k \\ &= \sum^{n}_{i=1}\sum^{n}_{j=i}\frac{a_i}{b_j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{j}\rfloor\sum^{n}_{k=j}\lfloor\frac{n}{k}\rfloor \ +\ \sum^{n}_{k=1}\frac{k(k+1)}{2} c_k \\ \end{aligned}

定义 $f(x)=\sum^{n}_{i=x}\lfloor\frac{n}{i}\rfloor$

则

\begin{aligned} 原式 &= \sum^{n}_{i=1}\sum^{n}_{j=i}\frac{a_i}{b_j}\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{j}\rfloor f(j) \ +\ \sum^{n}_{k=1}\frac{k(k+1)}{2} c_k \\ &= \sum^{n}_{i=1}a_i\lfloor\frac{n}{i}\rfloor\sum^{n}_{j=i}\frac{1}{b_j}\lfloor\frac{n}{j}\rfloor f(j) \ +\ \sum^{n}_{k=1}\frac{k(k+1)}{2} c_k \\ \end{aligned}

定义 $g(x)=\sum^{n}_{i=x}\frac{1}{b_i}\lfloor\frac{n}{i}\rfloor f(i)$

则

\begin{aligned} 原式 &= \sum^{n}_{i=1}a_i\lfloor\frac{n}{i}\rfloor g(i) \ +\ \sum^{n}_{k=1}\frac{k(k+1)}{2} c_k \\ \end{aligned}

在 $O(n \log b_i)$ 的时间复杂度内即可求出答案， $\log$ 是求模意义下乘法逆元的复杂度。

#include"bits/stdc++.h"
using ll=long long;
using namespace std;

constexpr int N=1e5+10;

struct Mint{...};

Mint a[N],b[N],c[N];
Mint f[N],g[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<=n;i++)
        cin>>c[i];

    Mint ans=0;
    for(int k=1;k<=n;k++){
        ans=(ans+k*(k+1ll)/2*c[k]);
    }

    for(int i=n;i>=1;i--){
        f[i]=f[i+1]+(n/i);
    }
    for(int i=n;i>=1;i--){
        g[i]=g[i+1]+(1/b[i])*(n/i)*f[i];
    }

    for(int i=1;i<=n;i++){
        ans=ans+g[i]*a[i]*(n/i);
    }

    cout<<ans<<'\n';

    return 0;
}

M 米娅逃离断头台

设大圆半径为 $a$ 小圆半径为 $b$ 从圆心连向切线要求的面积为 $\pi\times(a^2-b^2)/2$ ,又勾股定理可得 $a^2-b^2$ 等于 $x^2/4$ ，固答案为 $\pi\times x^2/8$ 。

#include"bits/stdc++.h"
using namespace std;
int main(){
    int x;
    scanf("%d",&x);
    double ans;
    ans=((x*x*1.0)/4.0)*acos(-1)/2.0;
    printf("%.2lf",ans);
    return 0;
}