2025牛客寒假算法营1

题目地址：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A题

思路：如果数组中包含1，则不存在答案。否则输出任意一个比maxmax大的素数（比如1e9+7）即可。

#include<bits/stdc++.h>

using namespace std;

void solve(){
    int n;
    cin>>n;
    
    bool f=false;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a==1){
            f=true;
        }
    }
    if(f)cout<<-1<<endl;
    else cout<<int(1e9+7)<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B题

如果有节点度数大于3，则不存在正确的路径，输出-1

判断这棵树是不是一条链，如果是则输出链上最远的两个节点，否则输出-1。

判断链的方式可以通过度数来判定：恰好存在两个点度数为1，其余点度数为2。输出两个度数为1的节点即可。

#include<bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin>>n;
    vector<vector<int>> adj(n);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        u--;                 //要对应下标，所以先减去1
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<n;i++){
        if(adj[i].size()>2){
            cout<<-1<<endl;
            return 0;
        }
    }
    vector<int>ans;
    for(int i=0;i<n;i++){
        if(adj[i].size()==1){
            ans.push_back(i);
        }
    }
    cout<<ans[0]+1<<" "<<ans[1]+1<<endl; //加回1就是原节点
    return 0;
}

D题

思路：直接将所有元素扔进map即可。也可以通过排序，check前一半和后一半是否相同，中间两元素不同。

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int main() {
    // 读取测试用例的数量
    int t;
    cin >> t;
    while (t--) {
        // 读取数组的长度
        int n;
        cin >> n;
        // 创建一个长度为 n 的整数向量来存储数组元素
        vector<int> arr(n);
        // 循环读取数组元素
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        // 如果数组元素的数量是奇数，直接输出 No 并继续下一个测试用例
        if (n % 2!= 0) {
            cout << "No" << endl;
            continue;
        }
        // 创建一个无序映射，用于存储元素及其出现的次数
        unordered_map<int, int> mp;
        // 遍历数组元素，将元素作为键，元素出现的次数作为值存储在无序映射中
        for (int num : arr) {
            mp[num]++;
        }
        // 如果无序映射的大小为 2，意味着数组中只包含两种不同的元素
        if (mp.size() == 2) {
            // 获取无序映射的第一个元素的迭代器
            auto it = mp.begin();
            // 获取第一种元素出现的次数
            int c1 = it->second;
            // 迭代器指向下一个元素
            it++;
            // 获取第二种元素出现的次数
            int c2 = it->second;
            // 如果两种元素出现的次数相等，输出 Yes
            if (c1 == c2) {
                cout << "Yes" << endl;
            }
            // 否则输出 No
            else {
                cout << "No" << endl;
            }
        }
        // 如果无序映射的大小不为 2，输出 No
        else {
            cout << "No" << endl;
        }
    }
    return 0;
}

G题

思路：可以先将给定的数组排序，之后对应位置的元素变成1~n即可。我们需要分别统计加的总和以及减的总和，如果这两个相等则有解，否则无解。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    // 提高输入输出性能，解除 C++ 标准输入输出流 cin/cout 与 C 标准输入输出流 scanf/printf 的同步
    ios::sync_with_stdio(false); 
    // 解除 cin 和 cout 的绑定，避免 cin 操作时自动刷新 cout 的缓冲区
    cin.tie(0); 

    int n;
    // 输入元素的数量
    cin >> n; 

    // 创建一个长度为 n 的向量 a 用于存储输入元素
    vector<int> a(n); 
    for (int i = 0; i < n; i++) {
        // 输入元素并存入向量 a 中
        cin >> a[i]; 
    }

    // 对向量 a 中的元素进行排序
    sort(a.begin(), a.end()); 

    // 计算向量 a 中元素的总和
    ll sum = accumulate(a.begin(), a.end(), 0LL); 
    // 检查元素总和是否等于 1 到 n 的自然数之和
    if (sum!= 1LL * n * (n + 1) / 2) { 
        // 若不相等，输出 -1 并结束程序
        cout << -1 << endl; 
        return 0; 
    }

    ll ans = 0;
    // 计算排序后元素的位置偏移量
    for (int i = 0; i < n; i++) { 
        ans += abs(a[i] - i - 1); 
    }
    // 取位置偏移量总和的一半
    ans /= 2; 
    // 输出最终结果
    cout << ans << endl; 
    return 0; 
}

E题

题意：给定一个数组，每次操作可以使得一个元素加1或者减1，问最小操作几次可以变成双生数组，即元素种类数为2、且出现次数相同。

知识点：排序，中位数定理

难度：1300

首先大家需要了解中位数定理：给定一个数组，每次操作加1或者减1，将所有元素变成相同的最小操作次数则是将所有元素变成中位数即可。

对于这道题而言，我们可以先将数组排序，对于前半部分我们将这些元素变成前半部分的中位数，后半部分我们将这些元素变成后半部分的中位数。注意需要特判这两个中位数相等的情况，解决方案是要么将前半部分变成中位数减1，要么将后半部分变成中位数加1，枚举这两种方案分别统计取最优。.

#include <bits/stdc++.h>

using i64 = long long; // 定义长整型别名 i64

// 处理每一组测试数据的函数
void solve() {
    int n;
    std::cin >> n; // 读取数组的长度
    
    // 读取数组元素
    std::vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }
    
    // 将数组进行排序，以便后续处理
    std::sort(arr.begin(), arr.end());
    
    // 计算数组的中位数，数组已经排序了，所以直接取中位数即可
    int half = n / 2; // 数组分为前后两部分，half为前半部分的元素个数
    
    // 前半部分的中位数，取前半部分中间的元素
    int left_median = arr[half / 2];
    // 后半部分的中位数，取后半部分中间的元素
    int right_median = arr[half + half / 2];
    
    // 初始化最小操作次数为一个非常大的值
    i64 min_operations = LLONG_MAX;
    
    // 枚举前后两部分中位数的两种调整方案
    for (auto left_value : {left_median, left_median - 1}) {  // 前半部分的中位数可能是 left_median 或 left_median - 1
        for (auto right_value : {right_median, right_median + 1}) {  // 后半部分的中位数可能是 right_median 或 right_median + 1
            // 如果前后部分中位数相同，跳过该组合，因为这不符合题目要求
            if (left_value == right_value) {
                continue;
            }
            
            i64 total_operations = 0; // 当前组合的操作次数
            
            // 计算将前半部分元素变为 left_value，后半部分元素变为 right_value 的操作次数
            for (int i = 0; i < half; i++) {
                total_operations += std::abs(arr[i] - left_value);  // 前半部分元素变为 left_value 的操作次数
                total_operations += std::abs(arr[half + i] - right_value);  // 后半部分元素变为 right_value 的操作次数
            }
            
            // 更新最小操作次数
            min_operations = std::min(min_operations, total_operations);
        }
    }
    
    // 输出该测试用例的最小操作次数
    std::cout << min_operations << "\n";
}

int main() {
    std::ios::sync_with_stdio(false); // 加速输入输出
    std::cin.tie(nullptr);  // 解除cin和cout的绑定，进一步加速输入输出
    
    int test_cases;
    std::cin >> test_cases;  // 读取测试用例的数量
    
    // 处理每组测试数据
    while (test_cases--) {
        solve();  // 解决当前的测试用例
    }
    
    return 0;
}

M题

题意：给定一个数组，可以选择一个区间将所有元素乘2，问操作后的最小极差。

知识点：贪心，模拟

难度：1400

思路：显然我们优先将最小值翻倍。如果想要扩大区间，我们则选择“包含最小值和次小值”的最小区间，以此类推。

那么，模拟方式是，我们首先得到每个元素的下标，然后维护区间两个端点l和r，当我们需要翻倍的区间增大的时候（比如从最小值到次小值），只需要将l向左移动或者将r向右移动，直到包含当前需要选择的元素。举个例子，假设当前我们翻倍的区间是[6,8]，这时下一个待翻倍的最小值位置在11，这时我们需要将第9,10,11这三个数同时翻倍。

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

// 使用 long long 类型的别名来方便后续计算
#define int long long

// 定义一个结构体来保存数组元素的值和其下标
pair<int, int> a[202020];  // a[i].first 表示数组元素值，a[i].second 表示该元素的索引
int b[202020];  // 用于存储原数组元素的值

signed main() {
    int n;
    cin >> n;  // 读取数组长度 n

    // 读取数组元素并将其存储在 a 数组中，同时记录元素的原始索引
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;  // 读取元素值
        a[i].second = i;     // 记录原始索引
        b[i] = a[i].first;   // 存储原数组元素值
    }

    // 设置一个极大的值用于后续比较
    a[n].first = 2e9;  // 最后一项设置为一个大值，确保后续排序时最后一个元素被替换

    // 对 a 数组按值排序
    sort(a, a + n);  // 默认按照元素值升序排列

    // 初始化变量 l 和 r 为最小元素的原始位置
    int l = a[0].second, r = a[0].second;

    // 计算初始极差的最大值，ma 是最大值
    int ma = max(a[0].first * 2, a[n - 1].first);
    // 初始极差计算
    int res = ma - min(a[0].first * 2, a[1].first);

    // 遍历排序后的数组
    for (int i = 1; i < n; i++) {
        // 如果当前元素的索引小于 l，则扩大左边界，更新 ma 的值
        while (a[i].second < l) {
            l--;
            ma = max(ma, b[l] * 2);
        }
        // 如果当前元素的索引大于 r，则扩大右边界，更新 ma 的值
        while (a[i].second > r) {
            r++;
            ma = max(ma, b[r] * 2);
        }
        
        // 更新最小极差
        res = min(res, ma - min(a[0].first * 2, a[i + 1].first));
    }

    // 输出最小极差
    cout << res;
}

J题

因数分解、打表、质数筛

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

int main() {
    const int N = 2e5 + 1;  // 定义常量 N，表示数组的大小上限。最大元素值为 200,000。
    
    int n;
    cin >> n;  // 读取数组的大小 n
    
    vector<int> a(N * 2 + 1, 0);  // 定义大小为 2 * N + 1 的数组 a，用于记录每个数的出现次数
    
    // 读取 n 个整数，并统计它们在数组 a 中的出现次数
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a[x]++;  // 对数组 a 中索引为 x 的位置进行加 1 操作
    }

    auto ans = 0ll;  // 用来保存最终结果，初始化为 0，数据类型为 long long。

    // get 函数用于计算两个数 x 和 y 的异或值和它们的最大公约数是否相等
    auto get = [&](int x, int y) {
        y += x;  // 将 y 增加 x，得到新的 y
        if ((x ^ y) == gcd(x, y))  // 如果 x 与 y 的异或值等于它们的最大公约数
            ans += 1ll * a[x] * a[y];  // 统计符合条件的数对数量，并加到答案中
    };

    // 枚举每个偶数 i
    for (int i = 2; i <= N; i += 2) {
        // 枚举 i 的所有约数 j
        for (int j = 1; j * j <= i; j++) {
            if (i % j) continue;  // 如果 i 不能被 j 整除，跳过

            // 对每个 j，调用 get 函数，检查 x = i 和 y = j 的情况
            get(i, j);
            
            // 如果 j 和 i / j 不相等，检查 x = i 和 y = i / j 的情况
            if (j * j != i) get(i, i / j);
        }
    }

    // 输出最终结果
    cout << ans << endl;
}