Luobuyu's Blog

0%

nowcoder多校(第八场)

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 12k 阅读时长 ≈ 11 分钟
2020年nowcoder暑期多校训练(第八场)，邝斌出题，题目还是比较难顶的。

A.

题目描述：

数据范围：

题解：

代码：

1
2


B.

题目描述：

数据范围：

题解：

代码：

1
2


C.

题目描述：

数据范围：

题解：

代码：

1
2


D.

题目描述：

数据范围：

题解：

代码：

1
2


E. Enigmatic Partition

题目描述：

把整数 $ n $ 拆分为 $ m $ 个整数之和，满足

  • 最大值和最小值相差为 $ 2 $
  • 相邻两数相差不超过 $ 1 $ ，且是升序

image-20200805161526404

$ f(n) $ 表示这种拆分的个数，求 $ \sum_{i=l}^r f(i) $

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

$ 1\le l \le r \le 100000 $

题解：

升序而且最大最小不能相差 $ 2 $ ，相邻不能相差 $ 1 $ ，所以一定是 $ l, l + 1, l + 2 $ 构成的。

假设三者的数量分别是 $ b_1, b_2, b_3 $ ，则

二阶差分：差分后再次差分。如果区间要加上一段有规律的数时，可以对差分数组进行再次差分。例如区间加上 $ 1,2,3,4,5 $ ，差分后 $ 1,1,1,1,1 $ ，变成了简单的区间加，再次差分就可以处理了。看来差分主要对待等差数列，或许还可以考虑一下等比数列之类的方法。

隔项差分：相隔一项再减，如加上 $ 1,2,1,2,1,2 $ ，隔项差分后 $ 1,2,0,0,0,0,-1,-2 $ 最后再隔项求一下前缀和即可

对于刚刚推出的公式来说， $ am $ 都是比较大的，难以考虑。因此不如确定 $ am $ ，然后枚举 $ b_2, b_3 $

假设 $ a=1, m = 6 $ ，每一行从前往后 $ b_2 $ 递增

n9101112131415161718
$ b_3 = 4 $123333
$ b_3 = 3 $112333122333
$ b_3 = 2 $111233112233122233
$ b_3 = 1 $111123111223112223122223
$ f(n) $1122211000
一阶差分10100-10-100
隔项差分1000-1-10001
对应位置am+3(a+1)m+1(a+1)m+2(a+2)m

所以我们只需要枚举 $ a, m $ ，然后对于每个 $ a, 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
ll f[maxn << 2];
void init(int n)
{
    // 隔项差分
    for(int m = 3; m <= n; m++)
    {
        for(int a = m; a <= n; a += m) // 直接枚举倍数
        {
            f[a+3]++;   // am
            f[a + m + 1]--; // (a+1)m+1
            f[a + m + 2]--; // (a+1)m+2
            f[a + m * 2]++; // (a+2)m
        }
    }
    // 差分
    for(int i = 3; i <= n; i++)
    {
        f[i] += f[i - 2]; 
    }
    // 原数组
    for(int i = 2; i <= n; i++)
    {
        f[i] += f[i - 1];
    }
    f[0] = 0;
    // 前缀和
    for(int i = 1; i <= n; i++)
    {
        f[i] += f[i - 1];
    }
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    scanf("%d", &t);
    init(maxn - 5);
    for (int tcase = 1; tcase <= t; tcase++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("Case #%d: %lld\n", tcase, f[r] - f[l-1]);
    }
    return 0;
}

F.

题目描述：

数据范围：

题解：

代码：

1
2


G. Game SET

题目描述：

每种牌有四种属性，number of shapes (one, two, or three) shape (diamond, squiggle, or oval), shading (solid, striped, or open), and color (red, green, or purple).

用 $ * $ 代表可以匹配任意属性值。

给出 $ n $ 张牌（包括存在 $ * $ ）的牌，问能否找到三张牌满足每一种属性，值要么相等要么全部不同

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

$ 1 \le N \le 256 $

时间： $ 1s $

题解：

看到数据感到不能暴力，没想到居然真的是暴力解决的。

image-20200804234858524

证明链接：https://web.archive.org/web/20130605073741/http:/www.math.rutgers.edu/~maclagan/papers/set.pdf (需要科学上网，太长了，看不懂)

所以直接暴力就行了， $ min(21, n) $

image-20200805000430001

实测，直接循环 $ n $ 也能过。为了不用 $ goto $ 需要根据标记跳出循环

代码：

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
117
118
119
120
121
122
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;

map<string, int> mp;
char str[maxn];

struct Card
{
    int a[5];
} card[maxn];

void init()
{
    mp["one"] = 1;
    mp["two"] = 2;
    mp["three"] = 3;

    mp["diamond"] = 1;
    mp["squiggle"] = 2;
    mp["oval"] = 3;

    mp["solid"] = 1;
    mp["striped"] = 2;
    mp["open"] = 3;

    mp["red"] = 1;
    mp["green"] = 2;
    mp["purple"] = 3;
}

bool check(int i, int j, int k)
{
    for (int p = 1; p <= 4; p++)
    {
        if (card[i].a[p] == -1 || card[j].a[p] == -1 || card[k].a[p] == -1)
            continue;
        if ((card[i].a[p] == card[j].a[p] && card[i].a[p] != card[k].a[p]) ||
            (card[i].a[p] == card[k].a[p] && card[i].a[p] != card[j].a[p]) ||
            (card[j].a[p] == card[k].a[p] && card[i].a[p] != card[j].a[p]))
        {
            return false;
        }
    }

    return true;
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    init();
    scanf("%d", &t);
    for (int tcase = 1; tcase <= t; tcase++)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", str);
            int start = 1;
            for (int j = 1; j <= 4; j++)
            {
                string tmp = "";
                while (str[start] != ']')
                {
                    tmp += str[start];
                    start++;
                }
                start++;
                if (str[start] == '[')
                    start++;
                if (tmp == "*")
                {
                    card[i].a[j] = -1;
                }
                else
                {
                    card[i].a[j] = mp[tmp];
                }
            }
        }
        bool flag = false;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                for (int k = j + 1; k <= n; k++)
                {
                    if (check(i, j, k))
                    {
                        printf("Case #%d: %d %d %d\n", tcase, i, j, k);
                        flag = true;
                        break;
                    }
                }
                if (flag)
                    break;
            }
            if (flag)
                break;
        }
        if(!flag)
            printf("Case #%d: -1\n", tcase);
    }

    return 0;
}

H.

题目描述：

数据范围：

题解：

代码：

1
2


I. Interesting Computer Game

题目描述：

给出两个数组 $ a_i, b_i $ ，每回合从 $ a_i, b_i $ 选出一个数或者啥都不做，选过的不能再选，最多能够选出多少

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

$ 1\le N \le 10^5 $

$ 1\le a_i\le 10^9, 1 \le b_i \le 10^9 $

题解：

将 $ a_i, b_i $ 看做点，连边。

发现如果可以组成一个环，那么环中的元素都可以选到，如果不能，那么只能选出连通分量 $ -1 $ 个。所以只需要把所有的点的数量减去非环连通分量的数量即可。

由于数比较大所以需要使用离散化

  • 使用一个新数组，使用 $ unique $ 排除重复元素，然后每个数对应一个下标

  • 使用 $ map $ ，如果不存在则插入，映射为 $ size $ ，如果存在直接取 $ id $

    1
    2
    3
    4
    5
    6
    int getId(int x)
    {
        if(mp.count(x)) return mp[x];
        else
            return mp[x] = mp.size() + 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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn], b[maxn];
int c[maxn << 1], tot = 0;

int fa[maxn << 1];
bool vis[maxn << 1];
int findFa(int u)
{
    return (u == fa[u] ? u : fa[u] = findFa(fa[u]));
}

void unite(int u, int v)
{
    int up = findFa(u);
    int vp = findFa(v);
    if(up == vp)
    {
        vis[up] = true;
    }
    else
    {
        fa[up] = vp;
        if(vis[up])
            vis[vp] = true;
    }
}

void init(int n)
{
    for(int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    memset(vis, false, sizeof(vis));
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    scanf("%d", &t);
    for(int tcase = 1; tcase <= t; tcase++)
    {
        scanf("%d", &n);
        tot = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d %d", &a[i], &b[i]);
            c[++tot] = a[i];
            c[++tot] = b[i];
        }
        sort(c+1, c+1+tot);
        tot = unique(c + 1, c + 1 + tot) - c - 1;
        init(tot);
        for (int i = 1; i <= n; i++)
        {
            int x = lower_bound(c + 1, c + tot + 1, a[i]) - c;
            int y = lower_bound(c + 1, c + tot + 1, b[i]) - c;
            unite(x, y);
        }

        int ans = tot;
        for (int i = 1; i <= tot; i++)
        {
            if(!vis[i] && fa[i] == i)
            {
                ans--;
            }
        }
        printf("Case #%d: %d\n", tcase, ans);
    }
    return 0;
}

J.

题目描述：

数据范围：

题解：

代码：

1
2


K. Kabaleo Lite

题目描述：

(艹皿艹 )没注意这题暴 $ long \ long $ 了，我之前写的 $ O(n) $ 的代码也没问题，我自己想错了以为有问题，使用了一波线段树改了下。晚上我把之前的代码改成 $ \_\_int128 $ 的然后就直接过了。然后我又试了试我的区间修改，最值查询线段树版本的，居然错了（板子是区间修改，区间和查询改过来的），刚好改了一下板子的错误

有 $ n $ 种菜，每种菜的数量为 $ b_i $ ，每个菜的盈利为 $ a_i $
每个顾客必须从第 $ 1 $ 种菜开始，连续地吃，每种吃一个。
保证顾客最多的情况下，盈利最大。

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

$ 1\le n \le 10^5 $

$ -10^9 \le a_i \le 10^9 $

$ 1\le b_i \le 10^5 $

题解：

最大顾客肯定是 $ b[1] $ ，后面就求一下 $ a[i] $ 的前缀和，找到从 $ 2 $ 号开始利润为正的，加入列表，排序，从利润最大开始取。维护一个 $ minb[i] $ 前缀最小值，这个是限制数量

遍历列表，枚举利润，得到该利润的终点（前缀和到第几号），记录数量，更新利润，然后继续枚举，得到最小值数量，减去前面已经消耗的，更新利润。

注意需要使用 $ \_\_int128 $ ，只能在 $ linux $ 中使用，且输入输出需要自己写。

也可以使用 $ O(n\log(n)) $ 的方法，使用线段树解决，直接查询最值，修改区间。

代码：

$ O(n) $ 版本

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
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m;

ll a[maxn];
int b[maxn]; // 数量
int minb[maxn];
struct Node
{
    __int128 sum;
    int id;
    bool operator<(const Node &x) const
    {
        return this->sum > x.sum;
    }
};

vector<Node> node;

inline void print128(__int128 x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print128(x / 10);
    putchar(x % 10 + '0');
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &t);
    for (int tcase = 1; tcase <= t; tcase++)
    {
        scanf("%d", &n);
        node.clear();
        a[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            a[i] += a[i - 1];
        }
        minb[0] = minb[1] = INF;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &b[i]);
            if (i > 1)
            {
                minb[i] = min(minb[i - 1], b[i]);
            }
        }
         __int128 ans = a[1] * b[1];
         int k = b[1];
         for (int i = 2; i <= n; i++)
         {
             ll p = a[i] - a[1];
             if (p > 0)
             {
                 node.push_back({p, i});
             }
        }
        sort(node.begin(), node.end());
        int tot = 0;
        for (int i = 0; i < node.size(); i++)
        {
            Node now = node[i];
            if (now.sum <= 0 || tot >= k)
                break;
            int mintot = minb[now.id] - tot;
            if (mintot <= 0)
                continue;
            if (mintot + tot >= k)
            {
                ans += (k - tot) * now.sum;
                tot = k;
                break;
            }
            else
            {
                ans += mintot * now.sum;
                tot += mintot;
            }
        }

        printf("Case #%d: %d ", tcase, k);
        print128(ans);
        printf("\n");
    }
    return 0;
}

线段树版本

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <bits/stdc++.h>
#define ll long long
#define ull long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m;

ll a[maxn];
int b[maxn]; // 数量
int minb[maxn];
struct Node
{
    __int128 sum;
    int id;
    bool operator<(const Node &x) const
    {
        return this->sum > x.sum;
    }
};

class SegTree
{
public:
    struct Node
    {
        int l, r;
        ll val, tag;
    } tree[maxn << 2];
    void build(int cur, int l, int r)
    {
        tree[cur].l = l, tree[cur].r = r, tree[cur].tag = 0;
        if (l == r)
        {
            tree[cur].val = b[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(cur << 1, l, mid);
        build(cur << 1 | 1, mid + 1, r);
        tree[cur].val = min(tree[cur << 1].val, tree[cur << 1 | 1].val);
    }
    void pushdown(int cur)
    {
        tree[cur << 1].val += tree[cur].tag;
        tree[cur << 1 | 1].val += tree[cur].tag;
        tree[cur << 1].tag += tree[cur].tag;
        tree[cur << 1 | 1].tag += tree[cur].tag;
        tree[cur].tag = 0;
    }
    void update(int cur, int l, int r, ll k)
    {
        if (l <= tree[cur].l && r >= tree[cur].r)
        {
            tree[cur].val += k;
            tree[cur].tag += k;
            return;
        }
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        if (tree[cur].tag)
            pushdown(cur);
        if (l <= mid)
            update(cur << 1, l, r, k);
        if (mid < r)
            update(cur << 1 | 1, l, r, k);
        tree[cur].val = min(tree[cur << 1].val, tree[cur << 1 | 1].val);
    }
    ll query(int cur, int l, int r)
    {
        if (l <= tree[cur].l && tree[cur].r <= r)
            return tree[cur].val;
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        ll a = INF_LL, b = INF_LL;
        if (tree[cur].tag)
            pushdown(cur);
        if (l <= mid)
            a = query(cur << 1, l, r);
        if (mid < r)
            b = query(cur << 1 | 1, l, r);
        return min(a, b);
    }
} segTree;

inline void print128(__int128 x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print128(x / 10);
    putchar(x % 10 + '0');
}

vector<Node> node;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &t);
    for (int tcase = 1; tcase <= t; tcase++)
    {
        scanf("%d", &n);
        node.clear();
        a[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            a[i] += a[i - 1];
        }
        minb[0] = minb[1] = INF;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &b[i]);
        }

        __int128 ans = a[1] * b[1];
        int k = b[1];
        for (int i = 2; i <= n; i++)
        {
            ll p = a[i] - a[1];
            if (p > 0)
            {
                node.push_back({p, i});
            }
        }
        sort(node.begin(), node.end());
        int tot = 0;
        segTree.build(1, 1, n);
        for (int i = 0; i < node.size(); i++)
        {
            Node now = node[i];
            if (now.sum <= 0 || tot >= k)
                break;
            ll mintot = segTree.query(1, 2, now.id);
            if (mintot <= 0)
                continue;
            if (mintot + tot >= k)
            {
                ans += (k - tot) * now.sum;
                tot = k;
                break;
            }
            else
            {
                ans += mintot * now.sum;
                tot += mintot;
                segTree.update(1, 2, now.id, -1ll * mintot);
            }
        }
        printf("Case #%d: %d ", tcase, k);
        print128(ans);
        printf("\n");
    }
    return 0;
}