【M Contect-Div.3】#5 题解

mengnn · 2025-10-24 09:18:17 · 题解

本帖由 mengnn 编写，若有疏漏感谢指出。

本帖 2025.10.24 完工。

A. Wind-Money 题解

题面及思路

太简单了，这题没做对的不应该。

按照题面读入 a,b,c,d，然后直接计算即可（注意 a / b的格式），公式：

\frac{a}{b}+\frac{c}{d}=\frac{a\times d+b\times c}{b\times d}

最后化简，需要保分子和分母互质：

\frac{a\times d+b\times c}{b\times d}=\frac{g\times p}{g\times q}=\frac{p}{q}

我们用 g 表示原分子与原分母的最大公约数，p 和 q 表示最终最简分数的分子和分母。易知，此时 p 与 q 互质。

注意：十年 OI 一场空，不开____见祖宗。

观察到 1\le a,b,c,d\le10^9，所以我们在计算分子/母，的时候会爆 int，开 long long 可以解决此问题。

时间复杂度

因为我们要求 gcd，所以最终复杂度 O(\log_2 n)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d;
char ch;
int main(){
    cin>>a>>ch>>b>>c>>ch>>d;
    long long x=a*d+b*c;
    long long y=b*d;
    cout<<(x/__gcd(x,y))<<" / "<<(y/__gcd(x,y));//直接使用 C++ 内置 gcd 函数
    return 0;
}

代码来自 mengnn。

B. Wind-Baptism 题解

题面及思路

思路可太好想了，我们可以通过计算来直接求解。

首先，求 1 到 n 的和直接用等差数列求和公式：

\sum_{i=1}^{n}i=\frac{n\times(n+1)}{2}

接下来，我们再统计次幂和，根据次幂求和公式：

\sum_{i=1}^{n}2^i=2^{n+1}-1

变形得：

\sum_{i=1}^{\lfloor \log_2 n\rfloor}2^i=2^{\lfloor \log_2 n\rfloor+1}-1

所求的原式为：

\sum_{i=1}^{n}i-2\sum_{i=1}^{\lfloor \log_2 n\rfloor}2^i

将公式代入：

\sum_{i=1}^{n}i-2\sum_{i=1}^{\lfloor \log_2 n\rfloor}2^i=\frac{n\times(n+1)}{2}-2\times(2^{\lfloor \log_2 n\rfloor+1}-1)

其中的 \log_2 n 需要用 log2(n) 函数来求解

注意：十年 OI 一场空，不开____见祖宗。

观察到 1\le n\le10^9，所以我们在计算时会爆 int，开 long long 可以解决此问题。

时间复杂度

由于我们直接取的公式，单次计算复杂度均为 O(1)。

数据组数为 T，则总复杂度为 O(T)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
int T;
long long n;
int main(){
    cin>>T;
    while (T--){
        cin>>n;
        cout<<(n*(n+1)>>1)-(((1<<((long long)log2(n)+1))-1)<<1)<<'\n';
        //代码中我们用 <<1 和 >>1 作为 *2 和 /2
    }
    return 0;
}

代码来自 mengnn。

C. Wind-Trader 题解

题面及思路

题面写的很丑，zxz 改了之后也很难看。

第一眼看题，很像图论算法，但实则不然。

知道了我们只能将点 0 与其余两个点连接后，不难想到枚举这两个点。

首先对于 m 次寄存，我们可以统计一下每个点的贡献，分为 4 种情况（设寄存关系的两点为 a 与 b，其中 a\le b）。

旅行者 a 和 b 都认识，那答案加 1，贡献为 0；
旅行者只认识 a，则对于连接 b 的贡献加 1；
旅行者只认识 b，则对于连接 a 的贡献加 1；
旅行者对于 a 和 b 都不认识，则连接 a 和 b 的共同贡献加 1。

注意：a 与 b 可能相等，若 a>b 则直接交换即可。

部分代码：

if (a>b) swap(a,b);
if (f[a]&&f[b]) ++ans1,++ans2;
else if (f[a]) ++t[b];
else if (f[b]) ++t[a];
else if (a==b) ++t[a];
else ++mp[{a,b}];

最后统计答案也分类讨论：

连接的是两个有关联的点，直接计算两个单点贡献加上连边贡献：

for (auto i:mp){
    int x=i.first.first,y=i.first.second,z=i.second;
    ans2=max(ans2,ans1+t[x]+t[y]+z);
}

连接的是两个无关的点，直接计算两个单点的贡献（直接取最大值与次大值，贡献最大）：

sort(t+1,t+k+1,greater<int>());
ans2=max(ans2,ans1+t[1]+t[2]);

于是你就轻松通过了本题（简单）！

时间复杂度

我们需要进行 map<pair<int,int>,int> 来存储边，且统计时我们还需进行排序，所以单次复杂度 O(\log_2 n)。

因为我们的算法基底复杂度为 O(n)，故总时间复杂度为 O(n\log_2n)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,m,k,t[N];
bool f[N];
template<typename T>inline void rd(T &x){
    x=0;char ch;
    bool f=false;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
        if (ch=='-')
            f=true;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<3)+(x<<1)+(ch&15);
    if (f) x=-x;
}
template<typename T>inline void wr(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) wr(x/10);
    putchar(x%10+'0');
    return ;
}
int main(){
    rd(T);
    while (T--){
        rd(n),rd(m),rd(k);
        for (int i=1;i<=k;i++) t[i]=f[i]=0;
        for (int i=1,x;i<=n;i++) cin>>x,f[x]=true;
        int ans1=0,ans2=0;
        map<pair<int,int>,int> mp;
        for (int a,b,i=1;i<=m;i++){
            rd(a),rd(b);
            if (a>b) swap(a,b);
            if (f[a]&&f[b]) ++ans1,++ans2;
            else if (f[a]) ++t[b];
            else if (f[b]) ++t[a];
            else if (a==b) ++t[a];
            else ++mp[{a,b}];
        }
        for (auto i:mp){
            int x=i.first.first,y=i.first.second,z=i.second;
            ans2=max(ans2,ans1+t[x]+t[y]+z);
        }
        sort(t+1,t+k+1,greater<int>());
        ans2=max(ans2,ans1+t[1]+t[2]);
        wr(ans2),putchar('\n');
    }
    return 0;
}

代码来自 mengnn。

D. Wind-Ball 题解

题面及思路

我们设 k 为小球跳跃能力。若 k 无法完成任务则 k - 1 亦无法完成；若 k 可以完成任务则 k + 1 亦可以完成。故答案具有单调性，考虑二分答案。

小球做 x 组折返，所以一个点要经过 2x 次。而当跳跃能力为 k 时，我们一次最多跳 k 长度，所以可以发现每个长度为 k 的区间，浮冰承受力总和不得小于 2x。我们依据这点来写 check() 函数。

我们在读入之后，将能力进行排序，在排序后的数组中查找能满足条件的最小值，若能查到输出编号；当 l=n+1 时，则无解。

若仍不懂见 P8775 青蛙过河。

时间复杂度

二分答案和排序时间复杂度均为 O(n\log_2n)，很好理解，不做解释。

AC Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 20;
int n,k,a[N],s[N],m;
struct node{
    int w,id;
}p[N];
inline bool cmp(node a,node b){
    return a.w != b.w ? a.w < b.w : a.id < b.id;
}
inline bool check(int mid){
    for ( int i = mid; i <= m; i ++){
        if (s[i] - s[i - mid] < 2 * k) return false;
    }

    return true;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> k;
    for ( int i = 1; i <= n; i ++){
        cin >> p[i].w;
        p[i].id = i;
    }
    for ( int i = 1; i <= m; i ++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    int l = 1,r = 1e9,mid;
    while (l <= r){
        mid = (l + r) >> 1;
        if (check(mid)){
            r = mid - 1;
        } 
        else l = mid + 1;
    } 
    int ans = r + 1;
    sort(p + 1,p + n + 1,cmp);
    l = 1,r = n;
    while (l <= r){
        mid = l + r >> 1;
        if (p[mid].w >= ans){
            r = mid - 1;
        }else l = mid + 1;
    }
    if (l == n + 1) cout << "Sorry";
    else cout << p[r + 1].id;
    return 0;
}

代码来自 Realize_Goal。