牛牛寒假训练营1题解

该加训力！这场比赛鉴定为我的鸣潮练度提升200%导致的ACM水平下降了1e9+7倍，而其他人却稳定提升2e5+5倍

前言：

牛牛训练营1第一场只写出四道题，其中一些题的罚时因为一些浅显的错误WA了好几发实在是太可惜了。下面就从我做出的四题AC的顺序开始分析，然后再进行补题。

签到题：D G B A；

D题：

题面如下：

小红拿到了一个数组，她可以进行任意次以下操作：选择两个元素，使得其中一个加 1，另一个减 1。
小红希望最终数组变成一个排列，请你帮助他确定这能否实现。如果可以实现的话，还需要求出最小操作次数。

长度为 n 的排列是由 1∼n 这 n 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 和 {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

分析：

只需要开一个map统计出现的数组元素以及其个数，首先判断map中的数组元素是否是2然后判断着两个元素的cnt是否相等即可。

Code：

void solve(){
    map<int,int> ma;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ma[a[i]]++;
    }
    int ans=0;
    vector<int> a;
    for(auto [x,y]:ma){
        ans++;
        a.push_back(ma[x]);
    }
    if(ans==2&&a[0]==a[1]){
        cout<<"Yes"<<endl;
        return ;
    }
    cout<<"No"<<endl;
}

G题：

题面如下：

小红拿到了一个数组，她可以进行任意次以下操作：选择两个元素，使得其中一个加 1，另一个减 1。
小红希望最终数组变成一个排列，请你帮助他确定这能否实现。如果可以实现的话，还需要求出最小操作次数。

长度为 n 的排列是由 1∼n 这 n 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 和 {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

分析：

我们观察题目，发现小红的操作并不会使数组中数的总和改变，这意味着只有当原数组的总和等于1+2+…+n时才能进行下一步（否则直接输出-1）。然后我们对数组进行排序。我们知道这个数组修改后必定会包含{1，2，…，n}这些元素，我们不妨设我们的数组就是{1，2，…，n}。故我们排序后直接对排序后的数组减去i的绝对值进行++++++。输出cnt/2即可。（因为一加一减是一次操作，我们进行上述的操作时，对整体求的是两倍）

Code：

int main(){
    ll sum=0;
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    ll pd=n*(n+1)/2;//求等差数列公式
    if(sum!=pd){
        cout<<"-1"<<endl;
        return 0;
    }
    ll cnt=0;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        cnt+=abs(a[i]-i);
    }
    cout<<cnt/2;
    return 0;
}

切记切记要开龙龙！！不然会爆int！！！！

B题：

题面如下：

小红拿到了一棵树，她想请你寻找一条简单路径，使得这条路径不重不漏的经过所有节点。如果不存在这样的简单路径，则直接输出 −1。

简单路径是指这样一条路径，其经过的顶点和边互不相同。

分析：

看起来是图论，实际上是一道思维题啦！通过幻想就可以得知，要求一条的简单路径，其中的头节点和尾节点只会在输入中出现一次，而其他节点只能出现两次。，我们就可以判断只出现不是两次的节点，（开map记录一下），然后输出即可。

Code：

int main(){
    int n;
    cin>>n;
    bool vis[n];
    map<int,int> d;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        d[u]++;
        d[v]++;
    }
    vector<int> b;
    for(int i=1;i<=n;i++){
        if(d[i]==1){
            b.push_back(i);
        }
    }
    if(b.size()!=2){
        cout<<-1<<endl;
        return 0;
    }else{
        cout<<b[0]<<" "<<b[1]<<endl;
        return 0;
    }
}

A题：

小红拿到了一个由 n 个数字组成的数组 {a1​,a2​,⋯,an​}，她希望你找到一个不大于 10^18 的正整数 x，满足 x 和数组中任意一个元素都互不为倍数关系，即对于 i∈[1,n]，x 不是 ai​ 的倍数，且 ai​ 也不是 x 的倍数。

分析：

还是很简单的，ai的范围为1≤ai​≤10^9，我们只需要找一个大于1e9的质数（比如1e9+7）;

如果数组中含有1，设置ans=-1，否则输出1e9+7。（我是铸币，直接在输入循环中return 0，导致WA了5发。）

Code：

void solve(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];

    }
    for(int i=0;i<n;i++)
    if(a[i]==1){
            cout<<"-1"<<endl;
            return ;
        }
    cout<<mod<<endl;

好了！以上就是我会做的题目了。接下来就该开始补题目了。嘻嘻

接下来是进阶题目：E H J M

先来M题：

定义一个数组的极差为：数组的元素最大值减去最小值。
小红拿到了一个数组，她准备进行恰好一次操作：选择一个非空区间，将其中所有元素都乘以 2。
小红希望最小化数组的极差，你能帮帮她吗？

（准备抄题解了）

思路：

我们需要找到该数组中最小的数假设确定它及其位置，假设最小值点为序列为k，则我们要直接使用multiset中的迭代器.rbegin()与.begin()寻找其最大值与最小值，我们设其为l,r,初始化为l=r。然后从k开始向l—或者向r++一个个遍历，寻找极差的最小值。

Code：

int main(){
    int n;
    cin>>n;
    vector<int> a(n + 1);
    vector<pair<int,int>> b;
    multiset<int> mu;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b.push_back({a[i],i});
        mu.insert(a[i]);
    }
    ranges::sort(b);
    auto [l,r]=b[0];
    mu.extract(l);
    mu.insert(2*l);
    int ans=*mu.rbegin()-*mu.begin();
    l=r;
    for(auto [_,i]:b){
        if(i>=l&&i<=r) continue;
        for(int j=l-1;j>=i;j--){
            mu.extract(a[j]);
            mu.insert(a[j]*2);
            ans=min(ans,*mu.rbegin()-*mu.begin());
        }
        l=min(l,i);
        for(int j=r+1;j<=i;j++){
            mu.extract(a[j]);
            mu.insert(2*a[j]);
            ans=min(ans,*mu.rbegin()-*mu.begin());
        }
        r=max(r,i);
    }
    cout<<ans;
    return 0;
}

补充：

multiset是C++库中的一个类型，相当于一个集合，它支持插入一个数，和删除一个数，操作的时间复杂度均是O（log（n））。

multiset提供了.extract()与.insert()的操作,可以快速的进行删除和增添操作。

然后他的.rbegin()与.begin()两个操作能返回数组中的最大值和最小值

然后就是E题：

小红定义一个数组是“双生数组”，当且仅当该数组大小为偶数，数组的元素种类恰好为 2 种，且这两种元素的出现次数相同。例如 {1,1,4,4,1,4} 是双生数组。
现在小红拿到了一个长度为偶数的数组，她可以进行若干次操作，每次操作将选择一个元素，使其加 1 或者减 1。小红希望你计算将该数组变成双生数组的最小操作次数。

思路：

我们对这个数组进行排序，然后会发现就是求数组前面一半的中位数和数组后面一半的中位数，然后将数组分别加上中位数的相减的绝对值，再考虑一下特殊情况即可。

void solve(){
    cin>>n;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    ll cnt=0;
    auto sum=[&](int x,int y){
        ll res=0;
       for(int i=1;i<=n/2;i++){
            res+=abs(a[i]-x);
        }
        for(int i=n/2+1;i<=n;i++){
            res+=abs(a[i]-y);
        } 
        return res;
    };
    auto check = [&](int x, int y){
        auto t = 0ll;
        if(a[x] != a[y]) t = sum(a[x], a[y]);
        else t = min(sum(a[x] - 1, a[y]), sum(a[x], a[y] + 1));
        return t;
    };
    int t=n>>1;
    int x=0,y=0;
    if(t&1){
        x=t+1>>1;
        y=t+x;
    }else{
        x=t>>1;
        y=t+x+1;
    }

    cout<<check(x,y)<<endl;
    //cout<<cnt<<endl;
    return ;
}

补充：

这里采用了C++20新特性，可以通过上述代码方式在主函数中构建函数。