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

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;
}
上一篇:IIC驱动移植在linux3.14.78上的实现和在linux2.6.29上实现对比(deep dive)


下一篇:aiohttp简介与简单使用