A-D题的题解。

比赛链接

A. Distance and Axis

题意：

给定一条数轴\(OX\)，只有正半轴，原点是\(0\)。给定点\(A\)的坐标\(n\)和目标\(k\)，我们每次可以对点\(A\)执行以下两种操作之一：

• 使点\(A\)的位置\(+1\)；
• 使点\(A\)的位置\(-1\)。

问如果要使得数轴上存在一个点\(B\)，使得点\(B\)到\(O\)和\(A\)的距离之差的绝对值\(dis\)恰好为\(k\)，至少要执行多少次操作？

思路：

考虑\(k \geqslant n\)，让点\(B\)和原点重合，此时应执行\(k - n\)次操作；

当\(k < n\)时，我们每一次改变点\(B\)的位置，\(dis\)都会变化\(2\)。所以，当\(n\)和\(k\)奇偶性不同时，需要执行一次操作，否则是\(0\)次。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
int T, n, k;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        if (k >= n) {
            printf("%d\n", k - n);
        }
        else if ((n + k) & 1) printf("%d\n", 1);
        else printf("0\n");
    }
    return 0;
}

B. Ternary Sequence

题意：

给定两个序列\(a,b\)，序列中只包含\(0,1,2\)。告诉我们\(a\)和\(b\)中分别有几个\(0,1,2\)，问如果我们按照如下条件构造序列\(c\)，\(\sum\limits_{i=1}^{n}c_i\)最大是多少？

其中：

\[c_i = \begin{cases} a_ib_i &a_i > b_i \\ 0 & a_i = b_i \\ -a_ib_i & a_i < b_i \end{cases} \]

思路：

容易发现，要使\(sum\)增大，只有\(a_i = 2\)且\(b_i = 1\)的情况。要使\(sum\)减小，只有\(a_i = 1, b_i = 2\)的情况。所以我们尽可能使前一种情况增多，后一种情况减少。所以我们先用\(a_i = 0\)去对应\(b_i = 2\)的情况，然后用\(a_i = 2\)去对应\(b_i = 1\)的情况，再用\(b_i = 2\)去对应\(a_i = 2\)的情况，最后用\(b_i = 2\)去对应\(a_i = 1\)的情况即可。

代码：

比赛的时候写的，可能比较乱。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
int T, a[3], b[3], ans, tmp;

int main() {
    scanf("%d", &T);
    while (T--) {
        ans = 0;
        for (int i = 0; i < 3; i++)
            scanf("%d", a + i);
        for (int i = 0; i < 3; i++)
            scanf("%d", b + i);

        tmp = min(a[0], b[2]);
        a[0] -= tmp;
        b[2] -= tmp;

        tmp = min(a[2], b[1]);
        ans += (tmp << 1);
        a[2] -= tmp;
        b[1] -= tmp;

        tmp = min(a[1], b[1]);
        a[1] -= tmp;
        b[1] -= tmp;

        tmp = min(a[1], b[0]);
        a[1] -= tmp;
        b[0] -= tmp;

        tmp = min(a[1], b[2]);
        ans -= (tmp << 1);
        a[1] -= tmp;
        b[2] -= tmp;
        
        printf("%d\n", ans);
    }
    return 0;
}

C. Mere Array

题意：

给定一个包含\(n\)个数的序列\(a\)，当\(a\)中的两个数满足\(gcd(a_i, a_j)\)恰好是\(a\)中最小的数的时候，我们就可以交换\(a\)中的这两个数。问我们能否将其变成一个非降序列？

思路：

我们将\(a\)中每一个数与最小的数求\(gcd\)，如果\(a_i\)与最小的数的\(gcd\)不是最小的数，那么这个数的位置就不可能变化。对于其他的数，我们总是能够借助最小的数来交换他们的位置。所以我们就只需要copy一个\(a\)数组（假设它叫\(b\)），然后对\(b\)排序。对于\(a_i \neq b_i\)，如果\(gcd(a_i, min) \neq min\)，则不可能构成非降序列，否则能构成非降序列。

代码：

比赛的时候写的代码思路比较清奇QwQ，不过能过

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + 5;
int n, a[maxn], b[maxn], small, T, flag;
bool abl[maxn];

inline void init() {
    small = INF;
    flag = 0;
    for (int i = 0; i <= n; i++) {
        abl[i] = false;
    }
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        for (int i = 0; i < n; i++) {
            scanf("%d", a + i);
            b[i] = a[i];
            small = min(small, a[i]);
        }
        sort(b, b + n);
        for (int i = 0; i < n; i++) {
            if (gcd(a[i], small) != small) {
                int l = lower_bound(b, b + n, a[i]) - b;
                int r = upper_bound(b, b + n, a[i]) - b;
                if (i < l || i >= r) flag = 1;
            }
        }

        if (flag)
            printf("NO\n");
        else 
            printf("YES\n");
    }
    return 0;
}

D. Maximum Distributed Tree

题意：

给定一个\(n\)个点\(n-1\)条边的连通图（其实就是树），我们要给它的边赋值，必须满足如下条件：

• 边权必须大于\(0\)；
• 所有边权的乘积必须等于\(k\)（输入直接给出\(k\)分解质因数后的质因数）；
• 边权为\(1\)的边必须尽可能少

定义\(f(u,v)\)为从\(u\)点到\(v\)点路径的边权和，问\(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}f(i,j)\)最大是多少？答案对\(10^9+7\)取模。

思路：

假定数的根为\(1\)，点的点权等于连向它父结点的边的边权。我们对所有的子树求出子树大小\(siz\)，则对于每一条边（每一个结点连向父结点的边，\(siz\)是这个结点所在子树的大小），它在求和中出现的次数就是\(siz \times(n-siz)\)。把每一条边的\(siz \times (n - siz)\)求出来，从大到小排序，因为要使得求和尽量大，所以我们尽可能把质数中最大的给\(siz \times (n - siz)\)最大的边。但是注意质数的数量可能多于\(n - 1\)，这个时候我们就把最大的那些质数乘起来，变成一个质数，把它赋给\(siz \times (n - siz)\)最大的边即可。若质数少于\(n - 1\)，则不够的部分补\(1\)。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
const int maxn = 1e5 + 5;
const ll MOD = 1e9 + 7;
using namespace std;

struct Edge {
    int to, nxt;
}e[maxn << 1];
int head[maxn], numedge, n, m, T, cur, siz[maxn];
ll res[maxn], prime[maxn], ans;

inline void AddEdge(int from, int to) {
    e[numedge].to = to;
    e[numedge].nxt = head[from];
    head[from] = numedge;
    numedge++;
}

inline void init() {
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        res[i] = 0;
    }
    numedge = 0;
    cur = 0;
    ans = 0;
}

bool cmp(const ll &a, const ll &b) {
    return a > b;
}

void dfs(int u, int fa) {
    siz[u] = 1;
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (to == fa) continue;
        dfs(to, u);
        res[cur++] = 1LL * siz[to] * (n - siz[to]);
        siz[u] += siz[to];
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        for (int i = 1; i < n; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            AddEdge(x, y);
            AddEdge(y, x);
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
            scanf("%lld", prime + i);
        
        dfs(1, 0);

        // for (int i = 1; i <= n; i++) {
        //     printf("%d ", siz[i]);
        // }
        // putchar('\n');
        for (int i = m; i < n - 1; i++)
            prime[i] = 1;

        sort(res, res + cur);
        sort(prime, prime + max(m, n - 1));
        while (m > n - 1) {
            prime[m - 2] = (prime[m - 2] * prime[m - 1]) % MOD;
            m--;
        }
        
        for (int i = 0; i < cur; i++) {
            ans = (ans + res[i] % MOD * prime[i] % MOD) % MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}