Codeforces Round 764 (Div. 3)(vp)

north_h / 2023-08-12 / 原文

Codeforces Round 764 (Div. 3)

A Plus One on the Subset

题意：判断最大和最小差多少即可

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)cin >> a[i];
    // for(auto i : a)cout << i << ' ';
    // cout << endl;
    sort(ALL(a));
    if(n == 1)cout << 0 << endl;
    else cout << a[n-1] - a[0] << endl;
}

B Make AP

题意：给\(a\) \(b\) \(c\)三个数，问其中的某一个数 \(\times\)\(m\)，最终的三个数是否能构成等差数列，最初的位置关系不能变

思路：就需要考虑三种情况即可：\(2\) \(\times\) \(b\) \(\times\) \(m\) \(=\) \(a\) \(+\) \(c\)，\(2\) \(\times\) \(b\) \(=\) \(a\) \(\times\) \(m\) \(+\) \(c\)，，\(2\) \(\times\) \(b\) \(=\) \(a\) \(+\) \(c\) \(\times\) \(m\)，求出对应\(m\)，在验证是否可行，注意题目要求\(m\)必须是正数

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int m1 = (a + c) / (b * 2);
    int m2 = (2 * b - c) / a ;
    int m3 = (2 * b - a) / c;
    // cout << m1 << ' ' << m2 << ' ' << m3 << endl;
    if(b * 2 * m1 == a + c&&m1>0)cout << "YES" << endl;
    else if(b * 2 == a * m2 + c&&m2>0)cout << "YES" << endl;
    else if(b * 2 == a  + c * m3&&m3>0)cout << "YES" << endl;
    else cout << "NO" << endl;
}

C Division by Two and Permutation

思路：因为这个题目输的个数很少，只有五十个，所以两层循环去找一下，不断除以二验证就行，时间复杂度\(O(\)\(n^{2}\)\(\log{a_i}\))，\(1 \le n \le 50\)，\(1 \le a_i \le 10^9\)

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int cnt = 0;
    sort(rALL(a));
    // for(auto i : a)cout << i << ' ';
    // cout << endl;
    for(int j = 0; j < n; j++) {
        int m = a[j];
        while(m && mp.count(m)||m>n) {
            m /= 2;
        }
        mp[m]=1;
    }
    for(int i = 1; i <= n; i++) {
        if(!mp.count(i)) {
            cout << "NO" << endl;
            return ;
        }
    }
    cout << "YES" << endl;
}

D Palindromes Coloring

题意：在目标字符串里找\(k\)个回文串，并且让这些回文串中最小的尽可能大

思路：一看见最小值最大，一眼二分，可惜我没看出来，这个题也可以用贪心去做，我们先把一对一对的统计下来有多少对，在平均分配给\(k\)个串，分配完了以后，如果还剩余加到只有一个字母的，再往\(k\)个回文穿里面加\(k\)个字符（如果有的前提下），就是答案

void solve() {
    int n, k;
    string s;
    cin >> n >> k  >> s;
    map<char, int> mp;
    for(auto i : s)mp[i]++;
    vector<int> a, b;
    int sl = 0, db = 0;
    for(auto [x, y] : mp) {
        if(y >= 2) {
            db += y / 2;
            if(y & 1)sl++;
        } else sl++;
    }
    // cout << sl << ' ' << db << endl;
    if(db%k!=0)sl+=db%k*2;
    cout<<db/k*2+(sl>=k)<<endl;
}