Luobuyu's Blog

0%

nowcoder多校(第五场)

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 7k 阅读时长 ≈ 6 分钟
2020年nowcoder暑期多校训练(第五场)，本场最起码应该可以做四个题，可是只搞了两个，要掉分了。忘了使用python了，LIS手误也写错了，手太不稳了

A.

题目描述：

数据范围：

题解：

代码：

1
2


B. Graph

题目描述：

给一棵树，每条边有边权。可以任意加边和删边，但要满足任何时刻图连通，而且任何一个环的边权异或和为 0 。求操作后最小权值和。

数据范围：
$ N(2\le N\le100000) $

$ U,V,W(0\le U,V\lt N,0\le W\lt 230) $

题解：

参考链接：最小生成树 异或 Trie树

边权可以进行转化。任意两点之间的权值都是固定的，由于环路异或和为零，所以如果存在多条路径的情况，这多条路径的异或值也应该是一样的。所以可以给每个点一个权值，两点间的边的权值就是两点点权的异或。

转化为了最小异或生成树问题。对于最小异或生成树可以使用字典树 $ 0-1 trie $ 进行维护，同时使用 $ boruvka $ 算法进行求解。

对于每个点权，使用 $ trie $ 从高位到低位存储（因为查异或值的时候高位异或对答案贡献比较大）。假设建立 $ trie $ 之后如下图所示。

image-20200726213801846

按照 $ boruvka $ 算法思想，需要划分为两个集合，然后在两个集合之间选择一条权值最小的边相连。

image-20200726213933958

如上图所示，左右两个集合 $ \{5,4\}\{3,2,1\} $ ，具体如何选择的可以看代码，找到最高位非零的位置 $ mid $ ，由于树是排好序的，所以小于该数的是右侧，大于的是左侧的。

分支之后，枚举一侧集合中的元素，通过 $ trie $ 查询到另一侧集合中元素异或值的最小值，得到两个集合联通的最小花费。依次分治，每次合并得到一条边，合并完毕后得到 $ n-1 $ 条边得到异或最小生成树。

可以进行优化，合并查询的时候，可以把元素较小的一遍进行枚举，去查询较大的另一侧的元素。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 100 + 10;
int a[maxn], n;

struct Edge
{
    int v, w;
};
vector<Edge> g[maxn];

// 循环非递归版
struct Trie
{
    static const int M = 2;          // 字符集大小
    static const int LEN = 31;
    int nex[maxn * 30][M], cnt = 0, val[maxn]; // cnt记录点号
    int xorv[maxn];

    void ins(ll x)
    {
        int now = 0;
        for (int i = LEN; i >= 0; i--)
        {
            int c = (x >> i) & 1;
            if(!nex[now][c])
            {
                nex[now][c] = ++cnt;
                nex[cnt][0] = nex[cnt][1] = 0;
            }
            now = nex[now][c];
        }
    }

    void init()
    {
        nex[0][0] = nex[0][1] = cnt = 0;
    }

    ll find(ll x) 
    {
        ll now = 0, ret = 0;
        for (int i = LEN; i >= 0; i--)
        {
            int c = (x >> i) & 1;
            if(nex[now][c])
                now = nex[now][c];
            else
            {
                now = nex[now][c ^ 1];
                ret |= (1 << i);
            }
        }
        return ret;
    }
}trie;

ll merge(int m, int l, int r)
{
    if (l == m || m == r)
        return 0;
    trie.init();
    ll ret = 0x3f3f3f3f3f3f3f3f;
    for (int i = m; i < r; i++)
        trie.ins(a[i]);
    for (int i = l; i < m; i++)
        ret = min(ret, trie.find(a[i]));
    return ret;
}

void dfs(int u, int fa)
{
    for (int i = 0; i < g[u].size(); i++)
    {
        auto e = g[u][i];
        if(e.v == fa)
            continue;
        a[e.v] = a[u] ^ e.w; // 边权转化为点权
        dfs(e.v, u);
    }
}

ll solve(int dep, int l, int r)
{
    if(dep == -1 || l == r)
        return 0;
    int mid = l;
    // 找到分叉点，从最高位开始
    while(mid < r && ((a[mid] >> dep) & 1) == 0)
        ++mid;
    // 找到了最高位为 1 的
    ll ret = solve(dep - 1, l, mid) + solve(dep - 1, mid, r);
    return ret + merge(mid, l, r);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &n);
    int u, v, w;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        u++, v++;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, -1);
    sort(a + 1, a + 1 + n);

    printf("%lld\n", solve(31, 1, n + 1));
    return 0;
}

C. Easy

题目描述：

两个序列 $ A,B $ 长度都为 $ K $ ，满足 $ \sum_{i=1}^{K}a_i = N $ ， $ \sum_{i=1}^{K} b_i = M $ ，就是把 $ N,M $ 划分为长度为 $ K $ 的 正整数 序列，然后计算 $ P = \prod_{i = 1}^{K}\min(a_i, b_i) $ ，计算各种可能情况的 $ P $ ，求和输出。

数据范围：
$ 1\le T \le 100 $

$ 1\le N,m\le 10^6 $

$ 1\le K \le \min(N,M) $

$ \mod(998244353) $

题解：

居然是生成函数。

img

img

取其中的 $ x^n \times y^m $ 就可以得到答案

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 998244353;
const int N = 1e6 + 10;
ll inv[N], f[N];
void get_inv(int n, int p)
{
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = inv[p % i] * (p - p / i) % p;
}
ll C(int x, int y)
{
    return f[x] * inv[x - y] % mod * inv[y] % mod;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    // ios::sync_with_stdio(0);
    // cin.tie(0), cout.tie(0);

    int T, n, m, k;
    get_inv(N - 1, mod);
    for (int i = 1; i < N; i++)
        inv[i] = inv[i] * inv[i - 1] % mod;
    f[0] = 1;
    for (int i = 1; i < N; i++)
        f[i] = f[i - 1] * i % mod;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &m, &k);
        ll ans = 0;
        for (int i = 0; i <= min(n, m) - k; i++)
        {
            ans = (ans + C(k + i - 1, k - 1) * C(n - i - 1, k - 1) % mod * C(m - i - 1, k - 1) % mod) % mod; //xy个数x个数y个数
        }
        printf("%lld\n", ans);
    }
}

D. Drop Voicing

题目描述：

给出一个字符串，可以进行两种操作

  • $ drop-2 $ ：将下标第二大的元素移到下标最小的位置
  • $ invert $ ：将最小位置的元素移到最大位置

执行若干次 $ invert $ 和若干次 $ drop-2 $ 为一组操作。问最少经过多少组操作可以使得给定的无序序列变成有序的。

数据范围：
$ 2\le n \le 500 $

题解：

观察后发现好像就是需要求 $ LIS $ ，然后 $ n - LIS $ 就是答案。每次一组操作都可以使得原来的 $ LIS $ 增长一个单位。后来手模了几个确实是这样，开始搞 $ LIS $ ，刚开始写了个 $ O(n^3) $ 的担心过不了，于是改了个 $ O(n^2log(n)) $ 的。注意不能直接长度变成 $ 2 * n - 1 $ ，求一次。我手模的数据发现这样的是错误的，得到的 $ LIS $ 既拥有第一段的元素也拥有第二段的元素。

$ LIS $ 问题 $ O(nlogn) $ 的忘了咋求的了，找了个模板结果不小心有处写错了。需要开辟一个新数组，装入已经搞到的 $ LIS $ ，方便进行修改，使用 $ lower\_bound $ 查找。

$ lower\_ bound(begin, end, target) $

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>

using namespace std;
const int maxn = 500 + 10;

int n;
int a[maxn];
int dp[maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    for (int i = n + 1; i < 2 * n; i++)
        a[i] = a[i - n];

    int ans = 0;
    for (int k = 1; k <= n; k++)
    {
        int end = k + n - 1;
        int top = 0;
        dp[++top] = a[k];
        for (int i = k + 1; i <= end; i++)
        {
            if(a[i] > dp[top])
                dp[++top] = a[i];
            else
            {
                int pos = lower_bound(dp + 1, dp + top, a[i]) - dp;
                dp[pos] = a[i];
            }
        }
        ans = max(ans, top); // pos刚好为个数
    }
    printf("%d\n", n - ans);
    return 0;
}

E. Bogo Sort

题目描述：

一个排序算法，根据一个给出的 $ 1-n $ 排列进行排序

1
2
3
4
5
6
7
8
9
10
int p[N] = {....}; // Tonnnny's favorite permutation of n
void shuffle(int a[], int n) {
    int b[n];
    for (int i = 0; i < n; i++) {
        b[i] = a[i]
    }
    for (int i = 0; i < n; i++) {
        a[i] = b[p[i]];
    }
}

答案需要 $ mod (10^n) $

数据范围：
$ 1 \le N \le 10^5 $

输入一个排列

题解：

需要保证在一定次数之内可以正确排序，也就是有一定数量的序列可以通过调整顺序变成排好序的。所以需要求每一位的环的长度，求出环的 $ lcm $ ，这样的话 $ lcm $ 之内的序列都可以排出来， $ n! - lcm $ 排不出来

模数就是离谱，居然是 $ 10^n $ ， $ cpp $ 需要使用大整数，我还没有准备模板，从网上抄了一个模板但是炸了（不知道怎么回事，应该是栈溢出了）。

后来发现还可以使用 $ python $ 编写，虽然数据有点大，但是 $ O(n) $ 可以过。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from math import *
n = int(input())
nums = [0] + list(map(int, input().split()))

vis = [0] * (n + 1)

plcm = 1

for i in range(1, n + 1):
    if vis[i] == 0:
        j = i
        cnt = 0
        while vis[j] == 0:
            cnt += 1
            vis[j] = 1
            j = nums[j]
        plcm = plcm * cnt // gcd(plcm, cnt) # 整除
print(plcm % (10**n)) # 要不要 10**n 都行

一些 $ python $ 技巧

1
2
3
import sys
sys.stdin=open("in.txt", "r") # 可以使用重定向输入
# 对一些list使用乘法可以直接初始化操作

F. DPS

题目描述：

略

数据范围：
$ 1\le n \le 100 $

题解：

属实沙雕，日了七发，这签到题一直 $ wa $ ，最后发现还要向上取整。真的应该使用 $ nowcoder $ 提交代码时的自测测一下，没有测以为结果是一样的，但是差别很小，肉眼不容易看

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100 + 10;
const int maxm = 20 + 10;
const int inf = 1e9;
int t;
int n;
int a[maxn];
bool flag[maxn];
int num[maxn];

void printb(int u)
{
    int t = num[u];
    printf("+");
    for(int i = 1; i <= t; i++)
    {
        printf("-");
    }
    printf("+\n");
    printf("|");
    for(int i = 1; i <= t; i++)
    {
        if(i == t)
        {
            if(flag[u])
            {
                printf("*");
            }
            else
            {
                printf(" ");
            }
        }
        else
        {
            printf(" ");
        }

    }
    printf("|");
    printf("%d\n", a[u]);

    printf("+");
    for(int i = 1; i <= t; i++)
    {
        printf("-");
    }
    printf("+");
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        flag[i] = 0;
    }
    int maxx = 0;
    for(int i = 1; i <= n; i++)
    {
        maxx = max(maxx, a[i]);
    }
    for(int i = 1; i <= n; i++)
    {
        if(a[i] == maxx) flag[i] = 1;
        num[i] = ceil((50.0 * a[i]) / maxx);
    }
    for(int i = 1; i <= n; i++)
    {
        printb(i);
        if(i < n)
        {
            printf("\n");
        }
    }
    return 0;
}

G.

题目描述：

数据范围：

题解：

代码：

1
2


H.

题目描述：

数据范围：

题解：

代码：

1
2


I. Hard Math Problem

题目描述：

有一个无穷大的二维网格，每个格子可以是 1 、 2 或者 3 ，每个 1 旁边要有一个 2 和 3 ，要使机器的占比最大。

数据范围：

题解：

略，直接 $ \frac{2}{3} $ ，惊了 $ php $ 直接写一个数就可以

代码：

1
0.666667

J.

题目描述：

数据范围：

题解：

代码：

1
2