2020 年暑期集训综合训练赛 8

2020 年暑期集训综合训练赛 8 题解。

题意简述摘自洛谷翻译。

A. Unusual Competitions

原题链接:Codeforces1323C

题意:有一个长度为 $n$ 的括号序列。 你可以进行若干次操作:花费 $m$ 的代价,将一个长度为 $m$ 的括号子串任意排列。 若能将括号序列排成合法的括号序,请求出最小花费的代价和。否则请输出 $-1$。

解法:首先把左右括号不等的情况判掉。判定合法括号序列,显然又是需要用到栈的。本题关键在如何找到那些原本不合法,但经过区间内部任意交换位置,可以变成合法的区间。这样的区间需要满足一个条件,也就是左括号数量等于右括号数量,开两个前缀和数组 l[],r[] 分别统计前缀中左右括号的数量。如何划分出需要调整的区间呢?可以给每一个 l[i] == r[i]i打个标记,这时候可以发现,这些被标记的点,将原序列划分成了若干区间,这些区间都是满足左括号等于右括号的。我们只需要检测这些区间的括号是否合法即可,经典的栈操作。如果不合法则表明这段需要调整,答案加上区间长度。

 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
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1000010;

int n;
int stk[N], tt;
char str[N];
int l[N], r[N];
bool st[N];

bool check(int left, int right) {
    tt = 0;
    for (int i = left; i <= right; i++) {
        if (str[i] == '(') stk[++tt] = ')';
        else if (!tt || stk[tt--] != ')') return false;
    }
    return true;
}

int main() {
    cin >> n;
    scanf("%s", str + 1);
    for (int i = 1; i <= n; i++) {
        if (str[i] == '(') l[i]++;
        else r[i]++;
    }
    for (int i = 1; i <= n; i++) {
        l[i] += l[i - 1];
        r[i] += r[i - 1];
        if (l[i] == r[i]) st[i] = true;
    }
    if (r[n] != l[n]) {
        puts("-1");
        return 0;
    }
    int res = 0, last = 0;
    for (int i = 1; i <= n; i++) {
        if (st[i]) {
            if (!check(last + 1, i)) res += i - last;
            last = i;
        }
    }
    printf("%d\n", res);
    return 0;
}

B. Uncle Bogdan and Country Happiness

原题链接:Codeforces1388C

题意:给一棵 $n$ 节点的树,每个节点有 $\mathrm{cnt}[i]$ 人住,他们从 $1$ 号节点回家,回家路上可能从开心的状态变成不开心的状态(但不可以由不开心变为开心),每个节点有个探测器,会探测经过该节点开心的人数减不开心的人数,而预期值为 $\mathrm{val}[i]$,问是否可能存在一种情况,使得所有节点的探测值等于真实值。

解法:DFS 求子树大小,以 $i$ 为根的子树大小为 $\mathrm{sz}[i]$,设 $i$ 号节点心情好的人数为 $\mathrm{good}[i]$,心情不好的人数为 $\mathrm{bad}[i]$,那么可以列式(解出来必须都是非负整数):

$$ \mathrm{good}[i] + \mathrm{bad}[i] = \mathrm{sz}[i] $$

$$ \mathrm{good}[i] - \mathrm{bad}[i] = \mathrm{val}[i] $$

可能无解,直接输出 NO。否则还需要 DFS 判断一遍,每个结点心情好的人数,必须大于等于他的所有子结点心情好的人数之和。

$$ \mathrm{good}[u] \ge \sum_{j\in \mathrm{son}[u]} \mathrm{good}[j] $$

 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
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 100010, M = N * 2;

int T, n, m;
int h[N], e[M], ne[M], idx;
int cnt[N], val[N], sz[N];
int good[N], bad[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa) {
    sz[u] = cnt[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        sz[u] += sz[j];
    }
}

bool judge(int u, int fa) {
    if (good[u] < 0 || bad[u] < 0) return false;
    int tot_good = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        if (!judge(j, u)) return false;
        tot_good += good[j];
    }
    if (tot_good > good[u]) return false;
    return true;
}

int main() {
    for (cin >> T; T--; ) {
        memset(h, -1, sizeof h); idx = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) scanf("%d", &cnt[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b), add(b, a);
        }
        dfs(1, -1);
        // good[i] + bad[i] = sz[i]
        // good[i] - bad[i] = val[i]
        bool flag = true;
        for (int i = 1; i <= n; i++) {
            good[i] = (sz[i] + val[i]) / 2;
            bad[i] = sz[i] - good[i];
            if ((sz[i] + val[i]) & 1) {
                flag = false;
                break;
            }
        }
        puts(flag && judge(1, -1) ? "YES" : "NO");
    }
    return 0;
}

C. Captain Flint and a Long Voyage

原题链接:Codeforces1388B

题解:给出正整数 $n$,求一个最小的 $n$ 位数字,要求这个数字转化成二进制并删掉最后 $n$ 位时,得到的二进制数最大。

解法:因为这个数字需要删掉最后的 $n$ 位后,还要让他最大,所以他应该尽可能的长一些,只有 $8$ 和 $9$ 是能转化为 $4$ 位二进制,$8=(1000)_2$,$9=(1001)_2$。那么很显然,答案只含 $8,9$。因为在剩下的数字最大的前提下答案还需要最小,那么很显然,如果最后一位会被删掉,选择 $8$ 即可,否则都选 $9$。也就是只有最后的 $\lceil \frac{n}{4} \rceil$ 位用 $8$,前面剩下的位都补 $9$ 即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
 
int T, n;
 
int main() {
    for (cin >> T; T--; ) {
        cin >> n;
        int a = (n + 3) / 4;
        int b = n - a;
        while (b--) printf("%d", 9);
        while (a--) printf("%d", 8);
        puts("");
    }
    return 0;
}

D. AND, OR and square sum

原题链接:Codeforces1368D

题意:给定 $n$ 个非负整数 $a_1$, $\cdots,a_n$。

你可以进行如下操作:选择两个不同的下标 $i,j$, 满足 $1\leq i,j\leq n,$并将 $a_i\gets a_i\ \mathsf{AND}\ a_j$,$\ a_j\gets a_i\ \mathsf{OR}\ a_j$,两个赋值同时进行。AND 是按位与,OR 是按位或。

你可以进行任意次操作。求操作后所有数的平方和的最大值,即 $\max \sum a_i^2$。

解法: $\max \sum a_i^2$,贪心希望让大的尽可能大。任取两个数字,我们可以发现对于这两个数字的某一位来说,可能是 $1,1$ 或 $1,0$ 或 $0, 1$ 或 $0,0$,这 $4$ 种组合,分别 $\mathsf{AND}$ 和 $\mathsf{OR}$ 操作后,仍然是原来的组合。也就是说,对于所有数,每一位上的 $1$ 的个数总数是不变的。

接下来,我们只需要统计每一位上 $1$ 的总数,贪心的分配每一位上的 $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
#include <bits/stdc++.h> 
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
 
const int N = 200010;
 
int n;
int a[N];
int c[30];
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        for (int j = 0; j < 20; j++) {
            if (a[i] >> j & 1) c[j]++;
        }
    }
    LL res = 0;
    for (int i = 0; i < n; i++) {
        int temp = 0;
        for (int j = 0; j < 20; j++) {
            if (c[j]) {
                temp += 1 << j;
                c[j]--;
            }
        }
        res += 1ll * temp * temp;
    }
    cout << res << endl;
    return 0;
}

E. Good String

原题链接:Codeforces1389C

题意:对于一个字符串 $t_1,t_2,\cdots,t_n$,

我们定义它的右移为 $t_n,t_1,\cdots,t_{n-1}$;

我们定义它的左移为 $t_2,t_3,\cdots,t_{1}$。

现在请问对于给出的一个字符串,最少删掉多少个字符才能是这个字符串的左移和右移完全相同?

解法:看下例子,只能是形如 $252525252525$ 这样交替出现且首尾不同,或者全是同一个数字(特殊考虑一下即可)。

接下来只需要考虑形如 $abababab$,直接暴力枚举 $a,b$ 的取值即可。然后在给定字符串中直接查找这个子串,求这个子串的最大长度 $len$,如果是偶数,那么肯定不合法,否则的话,除了这个子串,其他的字符位置都需要删掉。

 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
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 200010;

int T, n;
char str[N];
int cnt[10];

int main() {
    for (cin >> T; T--; ) {
        scanf("%s", str + 1);
        n = strlen(str + 1);
        memset(cnt, 0, sizeof cnt);
        for (int i = 1; i <= n; i++) cnt[str[i] - '0']++;
        int ans = 0;
        // 把字符串变成同一个数字
        for (int i = 0; i < 10; i++) ans = max(ans, cnt[i]);
        ans = n - ans;
        // 暴力枚举间隔出现的数字
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (i == j) continue;
                int len = 0;
                int flag = 1; // flag为1时候需要找数字i
                for (int k = 1; k <= n; k++) {
                    if (flag == 1) {
                        if (str[k] == i + '0') {
                            len++;
                            flag = 0;
                        }
                    } else {
                        if (str[k] == j + '0') {
                            len++;
                            flag = 1;
                        }
                    }
                }
                if (len & 1) continue;
                ans = min(ans, n - len);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

F. String Transformation 1

原题链接:Codeforces1383A

题意:有字符串 $A$,$B$,每次在 $A$ 中选取若干个相同的字母(设为 $x$ ),改成另一个字母(设为 $y$ ),需要满足 $x<y$,问将 $A$ 改成 $B$ 的最少操作。

解法:

首先,如果存在 $A_i > B_i$ 的情况,直接返回无解。

而后从 $a$ 到 $t$ 枚举每个字母,先遍历一遍,如果 $A$ 中所有的该字母都不需要修改,就进入下一轮枚举。

否则,找出该字母要修改的所有位置,求出 $B$ 的对应位置中字母序最小的字母,将所有位置都赋值为该字母即可。

 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
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 100010;

int T, n;
char a[N], b[N];

int main() {
    for (cin >> T; T--; ) {
        scanf("%d%s%s", &n, a, b);
        bool has_ans = true;
        for (int i = 0; i < n; i++) {
            if (a[i] > b[i]) {
                has_ans = false;
                break;
            }
        }
        if (!has_ans) {
            puts("-1");
        } else {
            int res = 0;
            for (char ch = 'a'; ch < 'a' + 20; ch++) {
                bool flag = true;
                char min_b = 'z';
                for (int i = 0; i < n; i++) {
                    if (a[i] == ch && a[i] != b[i]) {
                        flag = false; // 需要改
                        min_b = min(min_b, b[i]);
                    }
                }
                if (flag) continue;
                for (int i = 0; i < n; i++) {
                    if (a[i] == ch && b[i] != ch) {
                        a[i] = min_b;
                    }
                }
                res++;
            }
            cout << res << endl;
        }
    }
    return 0;
}

G. Filling Diamonds

原题链接:Codeforces1339A

解法:找规律(

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <bits/stdc++.h>

using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
 
LL T, n;
 
int main() {
    for (cin >> T; T--; ) {
        cin >> n;
        cout << n << endl;
    }
    return 0;
}

H. Celex Update

原题链接:Codeforces1358C

题意:

有 $T$ 组询问,每一组给出 $x_1,y_1,x_2,y_2$ ,要求你求出 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的所有路径中,不同的路径权值的个数。

解法:先右后下是最小值,先下后右得到了最大值,且这个最值区间是连续的。img

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

int a, b, c, d, T;

int main() {
    for (cin >> T; T--; ) {
        cin >> a >> b >> c >> d;
        cout << 1ll * (a - c) * (b - d) + 1 << endl;
    }
    return 0;
}

I. The Best Vacation

原题链接:Codeforces1358D

题意:这一年有 $n$ 个月,你将和某人一起待 $x$ 天( 连续 $x$ 天)。

第 $i$ 个月有 $d_i$天, 在一个月的第 $j$ 天,你将得到 $j$ 个拥抱。

求你最多能得到多少拥抱。

注意:一起待的 $x$ 天不必是同一年内的,也不必在一个月的第一天开始和某人一起待 $x$ 天。

解法:

贪心,前缀和,双指针

基于贪心,长度为 $x$ 的区间的右端点一定恰好是某一个月的结束的那天,否则,一定可以让这个区间向前平移,使得满足上述条件,从而使答案更优。首先 $d[\ ]$ 数组需要开两倍,复制一遍在后面,然后求 $d[i]$ 的前缀和 $sd[i]$,以及拥抱个数的前缀和 $s[i]$ 。然后我们枚举每一个月份 $i$ 作为结束月份(即 $x$ 区间的右端点),用 $j$ 指针表示 $x$ 区间左端点所在的月份,如果 $[j,i]$ 月份区间不够 $x$ 天,那么 $i$ 不断后移。然后更新对应的 $j$ 指针,如果 $[j+1,i]$ 月份区间的天数已经大于等于 $x$ 天了,那么 $j$ 后移动。通过这样双指针的移动,能保证 $x$ 区间的左端点一定在 $j$ 月份。因此计算这段区间的贡献就是:完整的 $[j+1,i]$ 月份的拥抱数量 + $j$ 月份月末连续的 $x−(sd[i]−sd[j])$ 天的拥抱数量。然后与答案取 $\max$ 即可。

 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
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 200010;

LL n, T, x;
LL d[N * 2];
LL s[N * 2];
LL sd[N * 2];

LL add(int i, LL cnt) {
    LL right = d[i], left = right - cnt + 1;
    return cnt * (left + right) / 2;
}

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        d[i + n] = d[i];
    }
    for (int i = 1; i <= 2 * n; i++) {
        s[i] = s[i - 1] + d[i] * (d[i] + 1) / 2;
        sd[i] = sd[i - 1] + d[i];
    }
    LL ans = 0;
    for (int i = 1, j = 1; i <= 2 * n; i++) {
        while (sd[i] - sd[j - 1] < x) i++;
        while (sd[i] - sd[j] >= x) j++;
        LL temp = s[i] - s[j] + add(j, x - (sd[i] - sd[j]));
        ans = max(ans, temp);
    }
    cout << ans << endl;
    return 0;
}

J. Captain Flint and Treasure

原题链接:Codeforces1388D

题意:这里有长度为 $n$ 的两个数组 $a$ 和 $b$ 。一开始,答案 $ans$ 等于 $0$ 。现在我们定义如下操作:

  • 选择一个位置 $i (1\leq i \leq n)$
  • 让 $ans$ 增大 $a_i$
  • 如果 $b_i \neq -1$ 就令 $a_{b_i} += a_i$

如果每一个 $i$ 只能选一次,请问 $ans$ 最大是多少? 并给出 $ans$ 最大时选择 $i$ 的顺序。

解法:

拓扑排序

当你选择某一个 $i$ 时,如果 $a_i > 0$ 且 $b_i \neq 1$ ,那么他会使得另一个数 $a_{b_i}$增大,因此,我们希望在选择 $b_i$ 之前先选择 $i$,因此存在拓扑关系。因此我们首先连边 $i\rightarrow b_i$,然后拓扑排序,每次从队头取出的 $t$ ,如果 $a_t > 0$,那么我们将它计入答案,并且把它的贡献累加到 $a_{b_t}$ 上,如果取出的 $a_t <=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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
 
const int N = 200010, M = N * 2;
 
int n;
LL a[N];
int b[N];
int h[N], e[M], ne[M], idx;
LL ans;
int d[N];
int q[N], hh, tt = -1;
int res[N], tot;
vector<int> t1, t2;
 
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
void toposort() {
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q[++tt] = i;
    }
    while (hh <= tt) {
        int t = q[hh++];
        if (a[t] > 0) {
            t1.push_back(t);
            if (b[t] != -1) {
                a[b[t]] += a[t];
            }
        } else {
            t2.push_back(t);
        }
        ans += a[t];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q[++tt] = j;
        }
    }
}
 
int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++) {
        if (b[i] == -1) continue;
        add(i, b[i]), d[b[i]]++;
    }
    toposort();
    printf("%lld\n", ans);
    for (auto x : t1) printf("%d ", x);
    for (int i = t2.size() - 1; i >= 0; i--) printf("%d ", t2[i]);
    puts("");
    return 0;
}
updatedupdated2020-11-232020-11-23
first commit