Codeforces Round #760 (Div. 3)

本场div3还是延续老传统，全部思维题（但是G题还没开，未知，明天待补题），A-F全思维题，并没用到算法和数据结构。

A. Polycarp and Sums of Subsequences

水题，已知有三个数字x,y,z；告诉x,y,z,x+y,x+z,y+z,x+y+z这七个数，但是不知道谁是谁，让分离出x,y,z。

很容易知道最小的两个数一定是x,y,z中的两个小数，最大的肯定是x+y+z，这样就分离出来了。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
ll a[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        for (int i = 1; i <= 7; i++)
            cin >> a[i];
        sort(a + 1, a + 8);
        ll x = a[1], y = a[2], sum = a[7];
        cout << x << " " << y << " " << sum - x - y << endl;
    }
    return 0;
}

B. Missing Bigram

一个由a和b组成的n位字符串，两两按顺序排列有n-1组，输入n-2组（有一组未知），需要找出原来的n位字符串。

只要找两个相邻字符串，前一个的后一位和后一个的前一位如果不一致，就插入那个未知的在该位置；如果都一致，就可能遗失了相同字符组成的，没有影响其他组，直接把最后一个字符输出两遍即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
ll a[N];
string str[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n - 2; i++)
            cin >> str[i];
        int flag = 0;
        for (int i = 2; i <= n - 2; i++) {
            if (str[i][0] != str[i - 1][1]) {
                flag = i - 1;
                str[n - 1] = "";
                str[n - 1] += str[i - 1][1];
                str[n - 1] += str[i][0];
            }
        }
        if (flag == 0) {
            for (int i = 1; i <= n - 2; i++) {
                cout << str[i][0];
            }
            cout << str[n - 2][1] << str[n - 2][1] << endl;
        } else {
            for (int i = 1; i <= n - 2; i++) {
                cout << str[i][0];
                if (flag == i) {
                    cout << str[i][1];
                }
            }
            cout << str[n - 2][1] << endl;
        }
    }
    return 0;
}

C. Paint the Array

给定一个长度为n的数组，问能否找到一个d，使得奇数位和偶数位两种位置上，满足其中一种全部整除d，另一组全部无法整除d？

首先先分离成两个数组，当然可以不分离，就是枚举奇偶位。然后分别去求整体的gcd。分成两种情况，当两个gcd相等时，这意味着不可能存在d，直接输出0。这是因为如果存在d<=gcd，那么奇偶位均可以整除，如果存在d>gcd，一定奇偶位都不能整除。当两个gcd不等时，需要分别试探采用其中一个gcd，另一个数组是否可以成立（即没有数能够整除），哪个成立输出哪个，没有成立的就输出0。

容易错的思路是：解题者会不由自主地用大的gcd，而忽略了另一个较小的gcd，事实上两个都有可能成为d，都需要试探一下。此外，本题数据范围会爆int，要开ll。

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;

ll a[N], b[N], c[N];

ll gcd(ll x, ll y) {
    if (x < y) {
        ll tem = x;
        x = y;
        y = tem;
    }
    if (x % y == 0)
        return y;
    else
        return gcd(y, x % y);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int cnt = 0, cnt2 = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (i % 2)
                b[++cnt] = a[i];
            else
                c[++cnt2] = a[i];
        }
        ll x1 = b[1], x2 = c[1];
        for (int i = 1; i <= cnt; i++) {
            x1 = gcd(x1, b[i]);
        }
        for (int i = 1; i <= cnt2; i++) {
            x2 = gcd(x2, c[i]);
        }
        // cout << x1 << " " << x2 << endl;
        if (x1 != x2) {
            int flag1 = 1, flag2 = 1;
            for (int i = 1; i <= cnt; i++) {
                if (b[i] % x2 == 0) {
                    flag1 = 0;
                    break;
                }
            }
            for (int i = 1; i <= cnt2; i++) {
                if (c[i] % x1 == 0) {
                    flag2 = 0;
                    break;
                }
            }
            if (flag1)
                cout << x2 << endl;
            else if (flag2)
                cout << x1 << endl;
            else
                cout << 0 << endl;
        } else {
            cout << 0 << endl;
        }
    }
    return 0;
}

D. Array and Operations

在这里插入图片描述题目不太好译，直接截图放上来了。

本题其实是一个彻底的贪心，最初想过用dfs爆搜，但是必然会t。我最初的思路是计算贡献值
$b o n u s [x] [y] = x + y ? f l o o r (x / y)$
用一个二维数组存起来，每次弹出一个最大值，把x和y置为已用状态。但是过不了样例，第一组数据很明显是1和2、1和3分组，而不是2和3分组。

正解是先排序，先最大化需要被消灭的数（最大的前k个数），剩下的数直接计入score，然后再最小化前k个数里的商和。这里依然有几个方案，一个是首尾配对，一个是相邻配对，一个是等距配对。这里采用第三种方法，确保分到同一组里的两个数尽可能有差距。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x7fffffff;
const int N = 105;
ll a[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        int score = 0;
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n - 2 * k; i++) {
            score += a[i];
        }
        for (int i = 1; i <= k; i++) {
            score += (a[n - 2 * k + i] / a[n - k + i]);
        }
        cout << score << endl;
    }
    return 0;
}

E. Singers’ Tour

在这里插入图片描述

以6个音乐家为例，循环之后可以得到下面这个方程组，常规思路是求解线性方程组，但是可以发现各式加起来可以求得a1+···+a6的值，经过若干次等式加减可以直接得到a1–a6的式子。
$b_1=a_1+6a_2+5a_3+4a_4+3a_5+2a_6\\ b_2=2a_1+a_2+6a_3+5a_4+4a_5+3a_6\\ b_3=3a_1+2a_2+a_3+6a_4+5a_5+4a_6\\ b_4=4a_1+3a_2+2a_3+a_4+6a_5+5a_6\\ b_5=5a_1+4a_2+3a_3+2a_4+a_5+6a_6\\ b_6=6a_1+5a_2+4a_3+3a_4+2a_5+a_6$
需要特判不成立的情况，第一种是b的和不能整除(n+1)* n/2，正对应了把上面式子加起来除以(n+1)*n/2得到a1+···+an；第二种是在运算过程中发现ai的值为0或为负，或除不尽，都要输出NO。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e4 + 5;
ll a[N], b[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n;
        ll sum = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> b[i];
            sum += b[i];
        }
        if (sum % (n * (n + 1) / 2) != 0) {
            cout << "NO" << endl;
            continue;
        }
        sum /= (n * (n + 1) / 2);
        b[n + 1] = b[1];
        int flag = 1;
        for (int i = 2; i <= n + 1; i++) {
            a[i] = (sum - (b[i] - b[i - 1])) / n;
            if (a[i] <= 0 || (sum - (b[i] - b[i - 1])) % n != 0) {
                flag = 0;
                break;
            }
        }
        if (!flag) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        for (int i = 1; i <= n; i++) {
            if (i == 1)
                cout << a[n + 1] << " ";
            else
                cout << a[i] << " ";
        }
        cout << endl;
    }
    return 0;
}