2021牛客OI赛前集训营-普及组（第一场）解析

2021牛客OI赛前集训营-J组-1 解析

A 优美的数

题干：

在BLUESKY007眼中，如果一个数包含7或这个数是7的倍数，这个数就是优美的。

BLUESKY007在纸上写下了所有大于0的优美的数，她想考考你，第k个数是多少？

解析： 这道题比较容易，直接递推计算。计算的结果存在一个数组内。

答案：

/*
 * @Description: https://ac.nowcoder.com/acm/contest/20038/A
 * @Date: 2021-10-04 18:34:04
 * @LastEditTime: 2021-10-04 18:44:24
 * @FilePath: \2021牛客OI赛前集训营-J\A 优美的数\beautiful_number.cpp
 * @Method: 暴力
 */
#include <iostream>
const int N = 100000;
int cnt, T, temp;
int rB[N];
bool isBeautifulNum(int x)
{
    if (x % 7 == 0) 
        return true;
    while (x)
    {
        if (x % 10 == 7) 
            return true;
        x /= 10;
    }
    return false;
}
void buildArr()
{
    for (int i = 1; i < N; i++)
    {
        if (isBeautifulNum(i))
            rB[++cnt] = i;
        if (cnt == 2021)
            break;
    }
}
int main()
{
    buildArr();
    scanf("%d", &T);
    for (int i = 1; i <= T; i++)
    {
        scanf("%d", &temp);
        printf("%d\n", rB[temp]);
    }
    return 0;
}

B 异或序列

题干：

Venn有一个数列 $a_{1}, a_{2}, . . ., a_{n}$ .有一天，BLUESKY007拿来了一个正整数 $X$ 。Venn是一个特别喜欢异或(xor)运算的孩子，她也很喜欢BLUESKY007。于是，Venn就想知道，自己能找到多少对数(i,j)能够满足 $a_i \ xor \ a_j = X$ . 两个数对 $(i_{1}, j_{1})$ 与 $(i_{2}, j_{2})$ 不同，当且仅当 $i_1 \neq i_2$ 或者 $j_1 \neq j_2$ 。

解析： 这题暴力肯定要超时（50分）。固要用二分查找。

答案：

这道题的题解同时收录在: CSDN

这道题除了用上面的算法外，还有一个比较容易理解的方法，详见代码。

这道题首先需要知道一个性质: 如果 a ^ b = c, 则 a ^ c = b, b ^ c = a.

不知道这个性质, 这道题西奈.

当你有一个有序数组, 应该怎样快速的判断这个数组里有多少个值等于 x 的数呢?

eg. a[] = {1, 2, 4, 5, 5, 6, 6, 10, 23, 74}; 且数组长度 n = 10, 你要查询这个数组里出现了多少次 x = 5.

先求出第一个大于 x 的数的地址, 再求出第一个大于等于 x 的数的地址, 两者相减就是答案. 即：

ans = std::upper_bound(a, a+n, x) - std::lower_bound(a, a+n, x);

那么有同学要问了: std::upper_bound 和 std::lower_bound 不是返回地址吗?

Answer:

 (std::upper_bound(a, a+n, x) - a) - (std::lower_bound(a, a+n, x) - a)
=std::upper_bound(a, a+n, x) - a - std::lower_bound(a, a+n, x) + a // 两个 a 抵消, 得
=std::upper_bound(a, a+n, x) - std::lower_bound(a, a+n, x)

时间复杂度为 $O(log n) \ll O(n)$ .

不知道这个性质, 这道题西奈.

这道题还有一个比较坑的, 就是时限太小. 所以你必须手写排序或者手写二分以提高效率.

不知道这一点, 这道题西奈.

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long LL;
const int N = 1e6 + 9;
int n, x, a[N];
int b[N], c[260];
void rsort() {
    for (int k = 0; k < 32; k += 8) {
        memset(c, 0, sizeof c);
        for (int i = 1; i <= n; ++i) ++c[a[i]>>k & 0xFF];
        for (int i = 1; i <= 0xFF; ++i) c[i] += c[i-1];
        for (int i = n; i; --i) {
            int t = a[i]>>k & 0xFF;
            b[c[t]--] = a[i];
        }
        memcpy(a+1, b+1, n*sizeof(int));
    }
}
int main() {
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    rsort();
    LL ans = 0, last = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == a[i-1]) {
            ans += last;
            continue;
        }
        int t = a[i] ^ x;
        last = std::upper_bound(a+1, a+n+1, t) - std::lower_bound(a+1, a+n+1, t);
        ans += last;
        // printf("when i=%d, last=%d\n", i, last);
    }
    printf("%lld", ans);
    return 0;
}

C 分身术

题干：

Venn和BLUESKY007正在写作业。今天的作业共有n道题，对于第i道题，Venn需要花费 $a_{i}$ 的时间才能做出，而BLUESKY007则需要花费 $b_{i}$ 的时间。因为作业实在是太多了，所以Venn决定今天只完成其中某一些，并且被完成的题目编号是连续的。

为了快速完成所有题目，Venn和BLUESKY007甚至学会了分身术，可以同时进行多道题目。

两人决定在写完作业后去吃水果。当BLUESKY007完成今天所有的计划题目后，才会前往吃水果，但Venn只要自己的任意一个分身完成了分配的题目，就会立刻前往吃水果。也就是说，如果决定今天完成的题目编号区间为[L,R]，那么Venn前往吃水果的时间为 $\min_{i=L}^Ra_i$ ,而BLUESKY007要在经过 $\max_{i=L}^Rb_i$ 时间后，才会去吃水果。

而Venn只需要花费K时间就能吃完所有的水果，Venn想通过决定题目区间的方法，来吃完所有水果，而不让BLUESKY007吃到水果。同时她还想要自己写的题目总数尽可能少。你能帮她算出最少要写几道题吗？

如果不存在这样一个规划方式，使得Venn独享所有水果，请输出So Sad!。

解析： 首先会想到用ST表。直接套用以下公式：

f[i][j]=min(f[i][j-1], f[i+2^{j-1}][j-1])

写出来的代码长这样：（要用到两个ST表）（懒得写了，直接抄dalao的）

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e7 + 3, LOG = 29, MAX = 0x3f3f3f3f;
int n, m, k, ans = MAX, a[N], b[N], f1[N][LOG], Log2[N], q[N], f2[N][LOG];
void init_log2() {
    Log2[1] = 0, Log2[2] = 1;

    for (int i = 3; i <= n; ++i)
        Log2[i] = Log2[i / 2] + 1;
}
void dp_len1() {
    for (int i = 1; i <= n; ++i)
        f1[i][0] = a[i];

    for (int j = 1; j <= Log2[n]; ++j) {
        int len = 1 << j;

        for (int i = 1; i <= n - len + 1; ++i)
            f1[i][j] = min(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
    }
}
void dp_len2() {
    for (int i = 1; i <= n; ++i)
        f2[i][0] = b[i];

    for (int j = 1; j <= Log2[n]; ++j) {
        int len = 1 << j;

        for (int i = 1; i <= n - len + 1; ++i)
            f2[i][j] = max(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
    }
}
int st_min1(int l, int r) {
    int len = r - l + 1;
    return min(f1[l][Log2[len]], f1[r - (1 << Log2[len]) + 1][Log2[len]]);
}
int st_max2(int l, int r) {
    int len = r - l + 1;
    return max(f2[l][Log2[len]], f2[r - (1 << Log2[len]) + 1][Log2[len]]);
}
int main() {
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++i)
        scanf("%d", &b[i]);

    init_log2();
    dp_len1();
    dp_len2();

    for (int l = 1; l <= n; ++l) {
        for (int r = l; r <= n; ++r) {
            int t1 = st_max2(l, r), t2 = st_min1(l, r), len = r - l + 1;

            if (t1 - t2 >= k)
                ans = min(ans, len);

            //          printf("%d %d:%d %d\n",l,r,t1,t2);
        }
    }

    if (ans == MAX)
        printf("So Sad!");
    else
        printf("%d", ans);

    return 0;
}

提交后发现只有60分。所以要想其它方法。

这里使用单调队列写了一个程序：

/*
 * @Description: https://ac.nowcoder.com/acm/contest/20038/C
 * @Date: 2021-10-04 19:32:19
 * @LastEditTime: 2021-10-05 11:12:11
 * @FilePath: \2021牛客OI赛前集训营-J\C 分身术\separation_AC.cpp
 * @Method: 单调队列
 */
#include <bits/stdc++.h>
const int N = 1e7 + 9, INF = 1e9;
int a[N], b[N], q1[N], f1, r1, q2[N], f2, r2;
int main()
{
    int n, k, ans = INF;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    for (int i = 1; i <= n; i++)
        scanf("%d", b + i);
    int lo = 1, hi = 0;
    while (hi < n)
    {
        ++hi;
        while (f1<r1 and a[q1[r1-1]]>=a[hi]) --r1;
        q1[r1++] = hi;
        while (f2<r2 and b[q2[r2-1]]<=b[hi]) --r2;
        q2[r2++] = hi;
        while (a[q1[f1]]+k<=b[q2[f2]] and lo<=hi)
        {
            ans = std::min(ans, hi-lo+1);
            ++lo;
            if (f1<r1 and q1[f1]<lo) ++f1;
            if (f2<r2 and q2[f2]<lo) ++f2;
        }
    }
    if (ans == INF) puts("So Sad!");
    else printf("%d", ans);
    return 0;
}

这道题算是这场比赛最难的一道题

D 种树

题干：

BLUESKY007喜欢种树。一天，她得到了一棵n个点的树，其中节点i重量为 $w_{i}$ 。在种树之前，BLUESKY007需要用起重机把树吊起。由于她只有一台起重机，所以她只能选择一个点作为受力点。根据BLUESKY007所在世界的物理知识，吊起一棵树需要做的功为 $\sum_{i=1}^{n}w_i\cdot dis_i$ 表示节点i与受力点之间的距离（边数）。

由于吊起这棵树的费用与所做的功正相关，所以BLUESKY007希望所做的功尽可能小。请你帮助她求出吊起这棵树所做的功的最小值。

解析： 第一眼看上去：最小生成树。可仔细一想，这题没法用最小生成树来做。我们用树形DP来做。

答案：

/*
 * @Description: https://ac.nowcoder.com/acm/contest/20038/D
 * @Date: 2021-10-04 20:18:09
 * @LastEditTime: 2021-10-05 11:56:12
 * @FilePath: \2021牛客OI赛前集训营-J\D 种树\plant_tree_AC.cpp
 * @Method:树形DP
 */
#include <iostream>
typedef long long LL;
const int N = 2e5 + 9;
struct Edge
{
    int to, nx;
} eg[N<<1];
int n, c, hd[N], dep[N];
LL w[N], tot, ans, sum[N];
inline void addE(int u, int v)
{
    eg[++c].nx = hd[u], hd[u] = c, eg[c].to = v;
}
inline void dfs(int u, int fa)
{
    for (int i = hd[u]; i; i = eg[i].nx)
    {
        int v = eg[i].to;
        if (v == fa)    
            continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        sum[u] += sum[v];
    }
    sum[u] += w[u];
    tot += w[u] * dep[u];
}
inline void solve(int u, int fa, LL w)
{
    ans = std::min(ans, w);
    for (int i = hd[u]; i; i = eg[i].nx)
    {
        int v = eg[i].to;
        if (v == fa) continue;
        solve(v, u, w+sum[1]-(sum[v]<<1));
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)    
        scanf("%lld", w + i);
    for (int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        addE(u, v), addE(v, u);
    }
    ans = 1LL<<60;
    dfs(1, 0);
    solve(1, 0, tot);
    printf("%lld", ans);
    return 0;
}

Update: