Codeforces Round #764 (Div. 3)题解(A-D)

脑子是一团浆糊。

A.Plus One on the Subset

题意

给一个数组,我们每次操作可以把其中的任意个数+1,问最多进行多少次操作可以使数组中每个数都相等?

题解

签到题,数组的最大值-数组的最小值就是答案。

B. Make AP

题意

给三个数,问让其中的一个数乘以一个正整数是否能使得a,b,c构成等差数列?

题解

枚举每一种情况,我们可能会改a,可能改b,也可能改c,注意判断条件。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7fffffffffffff
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while (T--) {
        ll a, b, c;
        cin >> a >> b >> c;
        if (abs(a - c) % 2 == 0 && (a + (c - a) / 2) > 0 && (a + (c - a) / 2) % b == 0) {
            cout << "YES" << endl;
        }
        else if ((b - (c - b)) >0&&(b - (c - b)) % a == 0) {
            cout << "YES" << endl;
        }
        else if ((b + (b - a)) >0&&(b + (b - a)) % c == 0) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

C. Division by Two and Permutation

题意

给一个长度n的数组,我们可以进行任意次对数组中元素除以2的操作,问能否构成一个n的排列。

题解

小于等于n的放着,不符合条件的不停除以2,直到符合条件。每次n减1然后去掉堆顶的数。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7fffffffffffff
using namespace std;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while (T--) {
        int n,s;
        cin >> n;
        bool f = 1;
        priority_queue<int> pq;
        for (int i = 0; i < n; i++) {
            cin >> s;
            pq.push(s);
        }
        for (int i = n; i; i--) {
            while (pq.top() > i) {
                s = pq.top();
                pq.pop();
                pq.push(s / 2);
            }
            if (pq.top() != i) {
                cout << "NO" << endl;
                f = 0;
                break;
            }
            pq.pop();
        }

        if(f==1)cout << "YES" << endl;
    }
    return 0;
}

D. Palindromes Coloring

题意

给一个字符串,你需要涂k种颜色,你不必对每一个字符都进行涂色。
然后你可以任意调换相同颜色的字符的位置,最后把同种颜色的字符按顺序放在一起构成字符串,所有颜色的字符串都必须是回文,问最短的回文串长度。

题解

因为除了含有一个字符的回文串外,回文串必须含有若干对字符,所以我们先统计出字符对数,然后平均分配给所有颜色。然后我们再看分剩下的是否够分给每种颜色各一个,如果够就是(对数/颜色数+1),否则就是(对数/颜色数)。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7fffffffffffff
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while (T--) {
        int a, b;
        cin >> a >> b;
        string s;
        cin >> s;
        map<char, int> mp;
        for (int i = 0; i < s.size(); i++) {
            mp[s[i]]++;
        }
        int num1 = 0, num2 = 0;
        int l = 0;
        for (auto i : mp) {
            if (i.second % 2 == 1) num1++;
            else num2++;
            l += i.second / 2;
        }

        if ((s.size() - l / b * 2 * b) >= b)cout << max(1, l / b * 2 + 1) << endl;
        else cout << max(1, l / b * 2) << endl;

    }

    return 0;
}
知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
上一篇
下一篇