Codeforces Round #629 (Div. 3) A~D，F

A：Codeforces 1328A Divisibility Problem 整除+模

Input

5
10 4
13 9
100 13
123 456
92 46

Output

2
5
4
333
0

按需取余，和我之前发的文章一样的解法

ll a, b;
void solve() {
    cin >> a >> b;
    cout << (b - a % b) % b << "\n";
}

B：Codeforces 1328B K-th Beautiful String

Input

7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

Output

aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

就是找到第 个全排列的字符串

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n, k; cin >> n >> k;
        string s(n, 'a');
        for (int i = n - 2; i >= 0; i--) {
            if (k <= n - (i + 1)) {
                s[i] = 'b', s[n - k] = 'b';
                break;
            } else k -= n - (i + 1);
        }
        cout << s << "\n";
    }
}

C：Codeforces 1328C Ternary XOR 贪心

Input

4
5
22222
5
21211
1
2
9
220222021

Output

11111
11111
11000
10211
1
1
110111011
110111010

题意：

给出一个 的三进制数字， 的第一个数字必须是 ，求出两个数 和 ，使得 和 #card=math&code=max%28a%2Cb%29&id=yBplD) 最小。

贪心，要使得最小的话对于 就是两个位置都放置 ，对于 就是两个位置都放置 ，但是这样肯定不能保证 的最大值最小，所以只要保证第一次出现 的时候分配给第一个，然后后面的都设置为 。

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        ll n; string s, a, b;
        cin >> n >> s;
        bool f = 0;
        //让我们求最小的a，2需要ab平均均摊，但只要1出现了以后直接另所有的都赋给b即可
        for (int i = 0; i < s.length(); ++i) {
            if (f) a += '0', b += s[i]; //第一个1以后直接另b等于s[i]即可
            else if (s[i] == '2') a += '1', b += '1';
            else if (s[i] == '1') a += '1', b += '0', f = 1;
            else a += '0', b += '0';
        }
        cout << a << "\n" << b << "\n";
    }
}

1328D - Carousel

个木马围成圈，为每个属性为 的木马涂上一种颜色 ，要求任何相邻的属性不同的木马颜色不同，问最少需要多少种颜色，并输出涂色方案（tip：属性相同的木马颜色可以不同也可以相同）

1. 如果所有木马属性都相同，那么最少要涂一种颜色，需要特判
2. 属性相同的木马颜色可以不同也可以相同，那么我们可以交替涂1，2，1，2，…如果n为偶数，那么一定满足条件且只需要两种颜色
3. 如果n为奇数，那么我们希望最后一个数c[n]两边的颜色c[1]和c[n - 1]尽可能相同，这样我们就不用使用第三种颜色，使答案最佳
4. 我们只要找到第n个数之前的t[i] = t[i - 1] （2 <= i <= n - 1)，然后从i开始的每个数与1异或即可（写代码时需要从零开始，才能0，1异或，最后答案加1即可）
5. .经过步骤4后，如果c[1] == c[n - 1]，c[n] = c[1] ^ 1即可
6. 如果c[1] != c[n - 1]（也就是前n - 1个属性都不同，无法通过步骤4使得c[1] == c[n - 1]），且c[n]与相邻两个数c[1]和c[n - 1]都不相同，那么c[n] = 2（最后答案会加1），否则t[n] == t[n - 1] ->c[n] = c[n -1]或者 t[n] == t[1] -> c[n] = c[1]

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    bool same = 1;
    for (int i = 0; i < n && same; ++i) if (a[i] != a[0]) same = 0;
    if (same) {
        cout << "1\n";
        for (int i = 0; i < n; ++i) cout << 1 << " \n"[i == n - 1];
        return ;
    }
    if (n % 2 == 0) {
        cout << "2\n";
        for (int i = 0; i < n; ++i)
            cout << (1 + (i & 1)) << " \n"[i == n - 1];
        return ;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == a[(i + 1) % n]) {
            cout << 2 << '\n';
            for (int j = 0; j < n; j++) {
                cout << 1 + (1 & ((j - i - 1 + n) % n)) << " \n"[j == n - 1];
            }
            return;
        }
    }
    cout << "3\n3 ";
    for (int i = 1; i < n; i++)
        cout << 1 + (i & 1) << " \n"[i == n - 1];
}

1328F. Make k Equal

题意：把 个数变成 个相同的数，每次可以把 个数里最大的 或最小的 ，问最小改变次数

思路：

我们可以枚举，把 个数变成 个 （这个相同的数一定是数组里的数，因为如果不是，那么改变次数一定会比正常多）

如果相同的数大于 个，那么改变次数为 ，特判掉

有三种情况，一种是只动前面，一种只动后面，还有就是前后都动

因为是改变最大或最小的数，所以我们只有把所有小于 的数变成 （或者大于 的数变成 ）才能进行下一次的改变

然后接着考虑，在什么情况下可以动前面呢，当然是他前面的数大于#card=math&code=%28k-1%29&id=iDA9O)个，同理，在他后面的数大于 #card=math&code=%28k-1%29&id=dsnFH) 个时才可以动后面，然后在任何情况下都可以前后都动( 在$(i=1) $时就相当于是动后面结果不冲突）

以只动前面为例

%20-a%5Bj%5D)%20%2B%20k#card=math&code=tem1%20%3D%20%28%5Csum%5Climits_%7Bj%3D1%7D%5Ei%28%28a%5Bi%5D%20-%201%29%20-a%5Bj%5D%29%20%2B%20k&id=syvoU)

化简一下发现

%20-%5Csum%5Climits%7Bj%3D1%7D%5Eia%5Bj%5D%20%2B%20k#card=math&code=tem1%20%3D%20%5Csum%5Climits%7Bj%3D1%7D%5Ei%28a%5Bi%5D%20-%201%29%20-%5Csum%5Climits_%7Bj%3D1%7D%5Eia%5Bj%5D%20%2B%20k&id=WVVcS)

就是 -a%5Bi%5D#card=math&code=i%2A%28a%5Bi%5D-1%29-a%5Bi%5D&id=fh1yE) 的前缀和 ,提前搞一个前缀和可以降低时间复杂度

只动后面同理

%20%2B%20k#card=math&code=tmp2%20%3D%20%5Csum%5Climits%7Bj%3Di%7D%5Ena%5Bi%5D%20-%5Csum%5Climits%7Bj%3Di%7D%5En%28a%5Bj%5D%20%2B%201%29%20%2B%20k&id=iSFA1)

动两边，这时相等的数的个数恰好为 ，把他们都搞成 然后再减掉多余的

#card=math&code=tmp3%20%3D%20%5Csum%5Climits%7Bj%3Di%7D%5Ena%5Bj%5D%20-%20%5Csum%5Climits%7Bj%3D1%7D%5Eia%5Bj%5D%20%2B%20%5Csum%5Climits%7Bj%3D1%7D%5Eia%5Bi%5D%20-%20%5Csum%5Climits%7Bj%3Di%7D%5Ena%5Bi%5D%20-%20%28n%20-%20k%29&id=qswOc)

记录好前缀和 和（后缀和？）就可以用 #card=math&code=%5Cmathcal%7BO%7D%28n%29&id=wi7Mh) 的复杂度解决掉这个问题了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e17;
ll a[200009];
ll cnt[200009];
ll sumq[200009], sumh[200009];
int main() {
    int n, k;
    ll ans = inf;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) sumq[i] = sumq[i - 1] + a[i];
    for (int i = n; i >= 1; i--) sumh[i] = sumh[i + 1] + a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] == a[i - 1])cnt[i] = cnt[i - 1] + 1;
        else cnt[i] = 1;
        if (cnt[i] >= k) {
            puts("0");
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i >= k) {
            ll tem1 = i * (a[i] - 1) - sumq[i] + k;
            ans = min(tem1, ans);
        }
        if (n - i + 1 >= k) {
            ll tem2 = n - i + 1;
            tem2 = sumh[i] - tem2 * (a[i] + 1) + k;
            ans = min(tem2, ans);
        }
        if (i < k && (n - i + 1) < k) {
            ll tem3 = i * a[i] - sumq[i] + sumh[i] - (n - i + 1) * a[i] - (n - k);
            ans = min(tem3, ans);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

便捷写法

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;
    sort(a.begin(), a.end());
    for (int i = 0; i + k - 1 < n; ++i) {
        if (a[i] == a[i + k - 1])
            return printf("0\n"), 0;
    }
    ll lcost = 0;
    ll rcost = 0;
    for (int i = 0; i < k; ++i) {
        lcost += a[k - 1] - a[i];
        rcost += a[n - 1 - i] - a[n - k];
    }
    for (int j = k; j < n; ++j) {
        if (a[k - 1] == a[j]) lcost--;
        if (a[n - k] == a[n - 1 - j]) rcost--;
    }
    ll sum = 0;
    for (int i = 0; i < n - 1 - i; ++i) sum += a[n - 1 - i] - a[i];
    ll ans = min(sum - (n - k), min(lcost, rcost));
    cout << ans;
}

D: CodeForces 1324D - Pair of Topics

Input

5
4 8 2 6 2
4 5 4 1 3

Output

7

Input

4
1 3 2 4
1 3 2 4

Output

0

题意：

有 个主题，第 个主题有 个老师, 个学生。

需要选择两个主题，这两个主题的老师数大于学生数

也就是说选择两个下标保证

输出可行的选择种类数

思路：

思维转为一下，让我们比较 的，直接求 有几个。

当然直接对数组操作以后是无序的，两重for会超时，所以需要我们先进行一次sort，然后判断累加。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 50;
ll a[N], b[N];
int main() {
    //freopen("in.txt", "r", stdin);
    int n; cin >> n;
    ll cnt = 0;
    for (int i = 0; i < n; ++i)cin >> a[i];
    for (int i = 0; i < n; ++i)cin >> b[i];
    for (int i = 0; i < n; ++i)a[i] -= b[i];
    sort(a, a + n);
    int l = n - 1;
    for (int i = 0; i < n; i++){
        while (l >= 0 && a[i] + a[l] > 0)l--;
        cnt+= n - max(i, l) - 1;
    }
    cout << cnt << endl;
}