【牛客训练记录】牛客周赛 Round 76

训练情况

赛后反思

D题被卡常了，我知道是优先队列的问题，但是一直有一个点过不去，E题疑似二分，但是我不会处理快速幂溢出的问题

A题

工作日每天 \(3\) 题，求 \(x\) 天一共有几周，一周有五个工作日，剩下不足 \(7\) 天的分类讨论。

#include <bits/stdc++.h>
// #define int long long
#define endl '\n'

using namespace std;

void solve(){
    int x; cin>>x;
    int ans = x/7*5;
    x -= x/7*7;
    if(x > 5) ans += 5;
    else ans += x;
    cout<<ans*3<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

B题

阅读理解题，子串的长度可以为 \(1\)，想要子串出现的次数尽可能多，子串的长度就需要尽可能小，所以这题在求哪一个字母出现的次数最多。

#include <bits/stdc++.h>
// #define int long long
#define endl '\n'

using namespace std;

void solve(){
    int n; cin>>n;
    string s; cin>>s;
    map<char,int> cnt;
    for(int i = 0;i<n;i++){
        cnt[s[i]]++;
    }
    char ans = 0;
    int now = 0;
    for(int i = 'a';i<='z';i++){
        if(cnt[i] > now){
            ans = i;
            now = cnt[i];
        }
    }
    cout<<ans<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

C题

gcd是最大公因数，我们想要答案和最小，我们要尽可能选择互质的两个数，因为互质两个数的 gcd = 1，我们可以发现 gcd 的次数越多，答案越小，所以我们把数列中所有的元素求一次最大公因数，所有的数都可以变成这个 gcd，然后答案就是 \(gcd \times n\)。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

void solve(){
    int n; cin>>n;
    vector<int> a(n + 1);
    for(int i = 1;i<=n;i++) cin>>a[i];
    int ans = a[1];
    for(int i = 2;i<=n;i++){
        ans = __gcd(ans,a[i]);
    }
    cout<<ans*n<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

D题

被玄学卡了一个测试点，但是这题应该是优先队列跑不了了，我们容易观察到贪心，我们有操作次数的时候，我们要优先选择对答案贡献大的，所以我们需要对数组进行从大到小排序，取最大的数进行操作，我们可以把对答案的贡献扔到优先队列里面，这样每次取出来的贡献就是最大的，每次取出优先队列的队头，如果能操作的话，操作之后再扔回去，奇数减一再除以二，偶数直接除以二，如果除以二的操作次数用完了，但是减一还有操作次数，就把所有的奇数取出来减一，直到不能操作为止。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 2e5 + 3;

int n,m,k;
int a[N];
priority_queue<int> q;

void solve(){
    cin>>n>>m>>k;
    for(int i = 1;i<=n;i++){
        int x; cin>>x;
        q.push(x);
    }
    while(q.size()&&m&&k){
        int x = q.top();
        q.pop();
        if(x&1){
            if(m&&k){
                m--,k--;
                q.push((x-1)/2);
            } else {
                q.push(x);
            }
        } else {
            if(m){
                m--;
                q.push(x/2);
            } else {
                q.push(x);
            }
        }
    }
    int ans = 0;
    while(q.size()){
        bool flag = true;
        if(k&&q.top()%2==1) k--,q.push(q.top()-1),q.pop(),flag=false;
        if(m&&q.top()%2==0) m--,q.push(q.top()/2),q.pop(),flag=false;
        if(flag) ans+=q.top(),q.pop();
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}