Codeforces Round #665 (Div. 2) A - D题题解

成功拼手速提前过了AC两题，估计因为这个原因排名挺高的，B题晚上做的时候没绕出来，wa4发。。。

1401A - Distance and Axis

如果 小 于 ，则必须将移至坐标，并将B的坐标设置为0或k。 因此答案是。
如果 不小于 ，则将B的坐标定义为。 根据问题中的条件，和之间的差应等于k。 即是k，并且总结公式 。 因为B的坐标是整数，所以如果n和k的奇偶性相同，则答案为0，否则答案为1（如果将A的坐标增加1，则m变为整数）。
时间复杂度：O（1）

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
int n, a[maxn], k;
void solve() {
    cin >> n >> k;
    if (n == k)cout << 0 << endl;
    else if (n < k)cout << k - n << endl;
    else cout << ((n - k) % 2 == 0 ? 0 : 1) << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
}

1401B - Ternary Sequence

我们可以找到ci值为3（−2,0,2）的种类。 并且只有当 为1且为2时才为−2，只有当为2且bi为1时才为2。否则为0。所以我们必须使（ai，bi）对（1,2） 尽可能少，并尽可能多地配对（2,1）。 为此，首先我们可以使（1,0）对，（0,2）对和（2,1）对尽可能多。 之后，将剩余值配对不会影响ci的总和。 （它的ai值为1，bi的值为2，尽管总和减少，我们必须将它们配对。）时间复杂度：O（1）

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;    cin >> t;
    while(t--){
        int m, sum = 0, x0, x1, x2, y0, y1, y2;
        cin >> x0 >> x1 >> x2 >> y0 >> y1 >> y2;
        m = min(x0, y2);
        x0 -= m;
        y2 -= m;
        m = min(x1, y0);
        x1 -= m;
        y0 -= m;
        m = min(x2, y1);
        x2 -= m;
        y1 -= m;
        sum += 2 * m;
        sum -= 2 * min(x1, y2);
        cout << sum << endl;
    }
}

1401C - Mere Array

让我们将a的最小元素定义为m。 我们发现不能被m整除的元素的位置无法更改，因为这些元素没有m作为因子。 但是我们可以通过以下方式任意重新排列可被m整除的元素：∙假设 ，并且有两个元素 和都不同。 交换 。 然后只有从初始状态交换。 重复此过程。
因此，我们可以按降序重新排列可被m整除的元素。 之后，如果整个数组不降序，则答案为是，否则为否。
时间复杂度：

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
int n, k;
ll a[maxn], b[maxn];
void solve() {
    cin >> n;
    ll minn = 1 << 30;
    bool flag = true;
    for (int i = 1; i <= n; ++i)cin >> a[i], minn = min(a[i], minn), b[i] = a[i];
    for (int i = 2; i <= n; ++i)if (a[i] < a[i - 1]) { flag = false; break; }
    if (flag) {
        cout << "YES" << endl;
        return;
    }
    sort(b + 1, b + 1 + n);
    flag = true;
    for (int i = 1; i <= n; ++i) {
        if (a[i] != b[i])
            if (gcd(a[i], minn) != minn) {
                flag = false;
                break;
            }
    }
    if (flag)cout << "YES" << endl;
    else cout << "NO" << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
}

1401D - Maximum Distributed Tree

让我们将定义为将第 个边缘从树中移除时属于两个分量中的每个分量的顶点数量的乘积，并将定义为第个边缘上的数量。 现在分布指数等于。 现在有两种情况：

在这种情况下，我们必须将标记为个不同的边缘，因为我们必须最小化的数量。 为了最大化分布指数，我们可以在较大的边缘标记一个较大的，因为以下条件成立：∙对于四个正整数。 然后可以将等式写成：（b + x）（d + y）+bd≥（b + x）d + b（d + y）

因为x，y≥0，所以证明了这一点。
并将标签1标记为其余边缘。
B：m> n-1在这种情况下，我们不能使n-1个整数中不存在1-s，并且n-1个数字中的一些将是复合的。 为了最大化分布指数，我们可以将的乘积标记到最大的边缘，并以与情况A相同的方式将剩余pi标记到其余边缘，因为以下条件成立：∙ 对于五个正整数代入上述方程式中的f = cd，我们发现方程式与之前相同。 因此，我们证明了这一点。
填充边缘后，计算并找到答案。
时间复杂度：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct H { int x, y; };
int ii, n;
const int q = 1e9 + 7;
LL p[100005], pv[100005], vi[100005], w[100005];
H e[200040];
int C(H a, H b) { return a.x < b.x; }
int G(LL a, LL b) { return a > b; }
LL dfs(int v){
    LL d = 1;
    vi[v] = 1;
    for (int i = pv[v]; i < pv[v + 1]; i++)
        if (!vi[e[i].y])
            d += dfs(e[i].y);
    w[ii] = d * (n - d);
    ii++;
    return d;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin >> t;
    while(t--){
        int k = 0, m;
        LL x = 1;
        cin >> n;
        for (int i = 0; i < n - 1; i++){
            cin >> e[i].x >> e[i].y;
            e[i + n - 1].x = e[i].y;
            e[i + n - 1].y = e[i].x;
        }
        int sz = 2 * n - 2;
        sort(e, e + sz, C);
        for (int i = 1; i < sz; i++)
            if (e[i].x > e[i - 1].x)
                for (int j = e[i - 1].x + 1; j <= e[i].x; j++)
                    pv[j] = i;
        for (int j = e[sz - 1].x + 1; j <= n + 2;)
            pv[j] = sz;
        ii = k = 0;
        dfs(1);
        cin >> m;
        for (int i = 0; i < m; i++)
            cin >> p[i];
        sort(p, p + m, G);
        sort(w, w + n - 1, G);
        if (m < n)
            for (int i = m; i < n - 1; i++)
                p[i] = 1;
        else{
            int i;
            for (i = m - 1; i > m - n; k = i, i--)
                w[i] = w[i - m + n - 1];
            for (; i; i--)
                w[i] = w[0];
        }
        int l = max(m, n - 1);
        int i;
        for (i = 0, x = w[0]; i <= k; i++)
            x = x * p[i] % q;
        for (; i < l; i++)
            x = (x + w[i] * p[i]) % q;
        cout << x << endl;
        for (int i = 1; i <= n;)
            vi[i] = 0;
    }
}