Codeforces Round #748 (Div. 3) A - E

https://codeforces.com/contest/1593

A

问每个人能成为严格第一所需要的最少加分,三个人之间是独立的

  • 计算当前人需要超过其他人的最少加分,最后取最大值即可
#include <bits/stdc++.h>

using namespace std;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int a, b, c;
        cin >> a >> b >> c;
        cout << max({0, b - a + 1, c - a + 1}) << ' ';
        cout << max({0, a - b + 1, c - b + 1}) << ' ';
        cout << max({0, a - c + 1, b - c + 1}) << '\n';
    }
    return 0;
}

B

给出一个数 n n n,每一次可以删除这个数的一位,前导零自动删除,保证有解,问最少删除多少位能够保证剩下的数是 25 25 25的倍数

  • 我们能够发现,如果一个数是 25 25 25的倍数,那么它的结尾两个数必须是 25 , 50 , 75 , 00 25,50,75,00 25,50,75,00中的一个,所以可以从后往前分别找 0 0 0和 5 5 5这样两种情况,分别讨论即可
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    string s;
    while(t--){
        cin >> s;
        int len = s.length();
        int ans = INT_MAX;
        for(int i=len-1;i>=0;i--){
            if(s[i] == '0'){
                for(int j=i-1;j>=0;j--){
                    if(s[j] == '0' || s[j] == '5'){
                        ans = min(ans, len - 2 - j);
                        break;   
                    }
                }
            }
            if(s[i] == '5'){
                for(int j=i-1;j>=0;j--){
                    if(s[j] == '2' || s[j] == '7'){
                        ans = min(ans, len - 2 - j);
                        break;
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

C

一条数轴,猫在 0 0 0位置处,洞在 n n n位置处,这两者之间有许多老鼠,猫每个时间点只能往右走一个单位,每个时间点只能有一个老鼠往右走一个单位,老鼠先移动,现在问最多有多少老鼠能跑到洞里

  • 我们显然应该贪心的让最靠近洞口的老鼠先进去,如果让别的老鼠进去,就会连累其他老鼠,所以每次让最右侧的未进洞的老鼠进洞,同时记录猫的位置,比较一下就好了
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        vector<int> a(k);
        long long cat = 0;
        for(int i=0;i<k;i++){
            cin >> a[i];
        }sort(a.rbegin(), a.rend());
        int ans = 0;
        for(int i=0;i<k;i++){
            if(a[i] > cat){
                ans += 1;
            }
            cat += n - a[i];
        }
        cout << ans << '\n';
    }
    return 0;
}

D1

一共有 n n n个数,现在要找到一个最大的数 x x x,使得某些数通过加若干个 x x x让所有数字一样大,如果 x x x可以是无穷大,那么输出 − 1 -1 −1,否则输出 x x x

  • 显然如果现在所有 n n n个数已经一样大了,那么应该输出 − 1 -1 −1
  • 否则一定可以找到某个数达到目标,考虑 1 1 1,这是一个任何情况下都满足的特殊数字,所以我们开始找最大的可能数字,通过枚举每两个数字差之间的 g c d gcd gcd来记录所有可能的数字,然后暴力枚举,每一种情况都进行计算,如果能够让所有 n n n个数都相等,那么就更新答案
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n);
        bool f = false;
        unordered_map<int, int> mp;
        for(int i=0;i<n;i++){
            cin >> a[i];
            mp[a[i]] += 1;
            if(mp[a[i]] == n) f = true;
        }
        if(f){
            cout << -1 << '\n';
            continue;
        }
        set<int> gcds, st;
        for(auto i : a){
            for(auto j : a){
                if(i != j) st.insert(abs(i - j));
            }
        }
        for(auto i : st){
            for(auto j : st){
                gcds.insert(__gcd(i, j));
            }
        }
        int ans = INT_MIN;
        for(auto x : gcds){
            for(auto i : a){
                int nm = 0;
                for(auto j : a){
                    if((i - j) % x == 0){
                        nm += 1;
                    }
                }
                if(nm == n){
                    ans = max(ans, x);
                    break;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

D2

  • 思路同上,不过将 n n n换成 n 2 \frac n 2 2n​
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n);
        bool f = false;
        unordered_map<int, int> mp;
        for(int i=0;i<n;i++){
            cin >> a[i];
            mp[a[i]] += 1;
            if(mp[a[i]] >= n / 2) f = true;
        }
        if(f){
            cout << -1 << '\n';
            continue;
        }
        set<int> gcds, st;
        for(auto i : a){
            for(auto j : a){
                if(i != j) st.insert(abs(i - j));
            }
        }
        for(auto i : st){
            for(auto j : st){
                gcds.insert(__gcd(i, j));
            }
        }
        int ans = INT_MIN;
        for(auto x : gcds){
            for(auto i : a){
                int nm = 0;
                for(auto j : a){
                    if((i - j) % x == 0){
                        nm += 1;
                    }
                }
                if(nm >= n / 2){
                    ans = max(ans, x);
                    break;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

E

每次操作移除所有叶子节点,如果原本是空树,那么不用动;如果只有一个节点,那么要将它移除;如果有两个节点,它们之间相连,那么都要移除掉,问 k k k次操作之后还剩多少叶子节点

  • 显然是一个拓扑排序,一层一层往下拿就可以了
  • 注意特判只有一个节点的情况
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k, u, v;
        cin >> n >> k;
        vector<vector<int> > g(n);
        vector<int> degree(n);
        for(int i=1;i<n;i++){
            cin >> u >> v;
            u -= 1;
            v -= 1;
            g[u].push_back(v);
            g[v].push_back(u);
            degree[v] += 1;
            degree[u] += 1;
        }
        queue<int> q;
        for(int i=0;i<n;i++){
            if(degree[i] == 1){
                q.push(i);
            }
        }
        int ans = n;
        while(k-- && !q.empty()){
            ans -= q.size();
            queue<int> q2;
            while(!q.empty()){
                u = q.front();
                q.pop();
                degree[u] = 0;
                for(auto i : g[u]){
                    if(degree[i] == 0) continue;
                    degree[i] -= 1;
                    if(degree[i] == 1){
                        q2.push(i);
                    }
                }
            }
            q = q2;
        }
        cout << (n == 1 ? 0 : ans) << '\n';
    }
    return 0;
}
上一篇:C++——system“pause”


下一篇:浅显易懂的win批处理指令--for指令入门