Educational Codeforces Round 112

Posted on Edited on In Views:
Symbols count in article: 14k

（模拟赛）

题目 A B C D E F
通过情况 AC AC AC AC O O
难度 900 1300 1300 1600 2100 2700

A. PizzaForces

题面

略

解法

注意特判$n<6$的情况

代码

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
/*
 * @题目: A. PizzaForces
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-07 19:19:21
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-07 19:24:24
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
ll read()
{
    ll p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int main()
{
    int t = read();
    while (t--)
    {
        ll n = read();
        if (n <= 6)
        {
            puts("15");
        }
        else
        {
            printf("%lld\n", (n + 1) / 2 * 5);
        }
    }
    return 0;
}

B. Two Tables

题面

略

解法

不难想到要得到最近的距离，只需平移第一个矩形，注意边界条件的判断

代码

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
/*
 * @题目: B. Two Tables
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-07 19:19:27
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-07 19:50:51
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int main()
{
    int t = read();
    while (t--)
    {
        int w = read(), h = read();
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        int w2 = read(), h2 = read();
        int w1 = x2 - x1, h1 = y2 - y1;
        int dis = 0x7fffffff;
        if (w1 + w2 <= w)
        {
            dis = min(dis, max(0, w2 - x1));
            dis = min(dis, max(0, x2 - (w - w2)));
        }
        if (h1 + h2 <= h)
        {
            dis = min(dis, max(0, h2 - y1));
            dis = min(dis, max(0, y2 - (h - h2)));
        }
        if (dis == 0x7fffffff)
            puts("-1");
        else
            printf("%d\n", dis);
    }
    return 0;
}

C. Coin Rows

题面

略

解法

利用前缀和逐点判断，确定下移的位置

代码

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
/*
 * @题目: C. Coin Rows
 * @算法: 前缀和
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-07 19:19:31
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-07 20:03:47
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int a[maxn][2];
int sum[maxn][2];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        rep(i, 1, n) a[i][0] = read(), sum[i][0] = sum[i - 1][0] + a[i][0];
        rep(i, 1, n) a[i][1] = read(), sum[i][1] = sum[i - 1][1] + a[i][1];
        int ans = 0x7fffffff, pos = 0;
        rep(i, 1, n)
        {
            if (max(sum[n][0] - sum[i][0], sum[i - 1][1]) <= ans)
            {
                pos = i;
                ans = max(sum[n][0] - sum[pos][0], sum[pos - 1][1]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Say No to Palindromes

题面

给定长度为$n$且仅由$a,b,c$组成的字符串，询问$m$次，每次询问$\left[ l,r \right] $的子串中使该子串的回文子串数量为$0$的最小修改次数（只能修改为$a,b,c$）

解法

发现要使回文子串数量为$0$，原串必须为$a,b,c$的某种排列循环连接而成，枚举这六种情况即可。

注意使用前缀和来加速询问（$O\left( n \right)预处理 $$O\left( 1 \right) $询问）

代码

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
/*
 * @题目: D. Say No to Palindromes
 * @算法: 暴力、前缀和
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-07 19:19:34
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-07 20:18:37
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
char s[maxn];
int sum[6][maxn];
int pat[6][3] = {
    0, 1, 2,
    0, 2, 1,
    1, 0, 2,
    1, 2, 0,
    2, 0, 1,
    2, 1, 0};

int main()
{
    int n = read(), m = read();
    scanf("%s", s + 1);
    rep(i, 0, 5)
    {
        rep(j, 1, n)
        {
            sum[i][j] = sum[i][j - 1] + ((s[j] != ('a' + pat[i][j % 3])) ? 1 : 0);
        }
    }
    while (m--)
    {
        int l = read(), r = read();
        int ans = sum[0][r] - sum[0][l - 1];
        rep(i, 1, 5)
        {
            ans = min(ans, sum[i][r] - sum[i][l - 1]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

E. Boring Segments

题面

略

解法

题目名字就非常耿直地告诉我们要用线段树。本题解法类似于扫描线，先将所有线段按数值排序，之后使用双指针逐一枚举情况。这样做的正确性在于任意移除两个指针之间的线段，如果不影响连通性，则不影响结果。这样就可以枚举出所有上下权值不同但连通的情况。
（具体实现见代码）

模拟比赛时由于线段树运用不熟练，没想明白单点和线段的区别（点有$m$个但线段只有$m-1$条），导致WA

代码

以线段建树

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
/*
 * @题目: E. Boring Segments
 * @算法: 线段树、双指针
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-07 21:24:28
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-07 21:35:39
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 300010
#define maxm 1000010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, m;
struct LINE
{
    int l, r, w;
} line[maxn];
int st[maxm << 2], tag[maxm << 2];
void pushdown(int rt)
{
    if ((rt << 1 | 1) < (maxm << 2))
    {
        tag[rt << 1] += tag[rt];
        tag[rt << 1 | 1] += tag[rt];
    }
    st[rt] += tag[rt];
    tag[rt] = 0;
}
void pushup(int rt)
{
    st[rt] = min(st[rt << 1], st[rt << 1 | 1]);
}
void upd(int rt, int l, int r, int ql, int qr, int c)
{
    pushdown(rt);
    if (ql > r || qr < l)
        return;
    if (ql <= l && r <= qr)
    {
        tag[rt] += c;
        pushdown(rt);
        return;
    }
    int mid = (l + r) >> 1;
    upd(rt << 1, l, mid, ql, qr, c);
    upd(rt << 1 | 1, mid + 1, r, ql, qr, c);
    pushup(rt);
}
bool cmp(LINE x, LINE y)
{
    return x.w < y.w;
}
int main()
{
    n = read(), m = read() - 1;
    rep(i, 1, n)
    {
        line[i].l = read(), line[i].r = read(), line[i].w = read();
    }
    sort(line + 1, line + n + 1, cmp);
    int j = 1;
    int ans = 0x7fffffff;
    rep(i, 1, n)
    {
        while (j <= n && st[1] + tag[1] == 0)
        {
            upd(1, 1, m, line[j].l, line[j].r - 1, 1);
            j++;
        }
        if (st[1] + tag[1] == 0)
            break;
        ans = min(ans, line[j - 1].w - line[i].w);
        upd(1, 1, m, line[i].l, line[i].r - 1, -1);
    }
    printf("%d", ans);
    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
/*
 * @题目: E. Boring Segments
 * @算法: 线段树、双指针
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-07 21:24:28
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-07 21:31:03
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 300010
#define maxm 1000010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, m;
struct LINE
{
    int l, r, w;
} line[maxn];
int st[maxm << 2], tag[maxm << 2];
void pushdown(int rt)
{
    if ((rt << 1 | 1) < (maxm << 2))
    {
        tag[rt << 1] += tag[rt];
        tag[rt << 1 | 1] += tag[rt];
    }
    st[rt] += tag[rt];
    tag[rt] = 0;
}
void pushup(int rt)
{
    st[rt] = min(st[rt << 1], st[rt << 1 | 1]);
}
void upd(int rt, int l, int r, int ql, int qr, int c)
{
    pushdown(rt);
    if (ql >= qr)
        return;
    if (ql == l && r == qr)
    {
        tag[rt] += c;
        pushdown(rt);
        return;
    }
    int mid = (l + r) >> 1;
    upd(rt << 1, l, mid, ql, min(qr, mid), c);
    upd(rt << 1 | 1, mid, r, max(ql, mid), qr, c);
    pushup(rt);
}
bool cmp(LINE x, LINE y)
{
    return x.w < y.w;
}
int main()
{
    n = read(), m = read();
    rep(i, 1, n)
    {
        line[i].l = read(), line[i].r = read(), line[i].w = read();
    }
    sort(line + 1, line + n + 1, cmp);
    int j = 1;
    int ans = 0x7fffffff;
    rep(i, 1, n)
    {
        while (j <= n && st[1] + tag[1] == 0)
        {
            upd(1, 1, m, line[j].l, line[j].r, 1);
            j++;
        }
        if (st[1] + tag[1] == 0)
            break;
        ans = min(ans, line[j - 1].w - line[i].w);
        upd(1, 1, m, line[i].l, line[i].r, -1);
    }
    printf("%d", ans);
    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
/*
 * @题目: E. Boring Segments
 * @算法: 错误的线段树使用
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-07 19:19:38
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-07 21:19:29
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 300010
#define maxm 1000010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, m;
struct LINE
{
    int l, r, w;
} line[maxn];
int st[maxm << 2], tag[maxm << 2];
void pushdown(int rt)
{
    if ((rt << 1 | 1) < (maxm << 2))
    {
        tag[rt << 1] += tag[rt];
        tag[rt << 1 | 1] += tag[rt];
    }
    st[rt] += tag[rt];
    tag[rt] = 0;
}
void pushup(int rt)
{
    st[rt] = min(st[rt << 1], st[rt << 1 | 1]);
}
void upd(int rt, int l, int r, int ql, int qr, int c)
{
    pushdown(rt);
    if (ql > r || qr < l)
        return;
    if (ql <= l && r <= qr)
    {
        tag[rt] += c;
        pushdown(rt);
        return;
    }
    int mid = (l + r) >> 1;
    upd(rt << 1, l, mid, ql, qr, c);
    upd(rt << 1 | 1, mid + 1, r, ql, qr, c);
    pushup(rt);
}
bool cmp(LINE x, LINE y)
{
    return x.w < y.w;
}
int main()
{
    n = read(), m = read();
    rep(i, 1, n)
    {
        line[i].l = read(), line[i].r = read(), line[i].w = read();
    }
    sort(line + 1, line + n + 1, cmp);
    int j = 1;
    int ans = 0x7fffffff;
    rep(i, 1, n)
    {
        while (j <= n && st[1] + tag[1] == 0)
        {
            upd(1, 1, m, line[j].l, line[j].r, 1);
            j++;
        }
        if (st[1] + tag[1] == 0)
            break;
        ans = min(ans, line[j - 1].w - line[i].w);
        upd(1, 1, m, line[i].l, line[i].r, -1);
    }
    printf("%d", ans);
    return 0;
}

F. Good Graph

题面

向含有$n$个点的图中尝试加边权值为$0/1$的边，若图中所有的环边权值异或值为$1$，则加入图中，否则不加入

解法

首先要发现一个非常重要的性质：如果要满足条件，任意两个环不能有重合边。同时在接下来的操作中，将利用$k\oplus k=0$的异或性质。

将要加入的边分成两类：树边（加入后不产生新的环，即将不连通的块连在一起）和环边（加入后产生新的环）。显然在加入树边后对答案没有影响，所以先将所有树边加入（利用并查集判断）并预处理好$LCA$（倍增）以及从根节点到所有节点的边权异或结果（代码中的$xr$数组）

之后对环边的加入我们要处理两个问题：

①加入后的环边权异或值为1。求环的异或值我们利用xr数组就可以解决，即$xr\left[ u \right] \oplus xr\left[ v \right] \oplus w$

②加入后的环不与之前加入的环有重叠边。可以用树链剖分解决，不过这里标程很巧妙地用了$tin和tout$来计入dfs时每个点开始访问和结束访问的时间，一方面可以辅助$LCA$的求解，另一方面利用树状数组可以在$tin[lca]$到$tin[u/v]$的时间内是否有边加入（具体实现见代码）

代码

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
163
164
165
166
167
168
169
170
171
/*
 * @题目: F. Good Graph
 * @算法: 并查集、LCA、树状数组、dfs
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-07 19:19:41
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-11 12:12:53
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x & -x)
#define maxn 300010
#define maxm 500010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n, m;
int e[maxm][3];
int par[maxn];
void init()
{
    rep(i, 1, n) par[i] = i;
}
int find(int x)
{
    return x == par[x] ? x : par[x] = find(par[x]);
}
bool unite(int u, int v)
{
    u = find(u), v = find(v);
    if (u == v)
        return 0;
    par[v] = u;
    return 1;
}
vector<pair<int, int>> g[maxn];
const int LOG = 19;
int up[maxn][LOG], tin[maxn], tout[maxn], xr[maxn];
int T = 1;
void dfs(int u, int p, int curXor)
{
    tin[u] = T++;
    xr[u] = curXor;
    up[u][0] = p;
    rep(pw, 1, LOG - 1)
        up[u][pw] = up[up[u][pw - 1]][pw - 1];
    for (auto v : g[u])
    {
        if (v.first == p)
            continue;
        dfs(v.first, u, curXor ^ v.second);
    }
    tout[u] = T;
}
void buildLCA()
{
    rep(u, 1, n)
    {
        if (!tin[u])
            dfs(u, u, 0);
    }
}
int isPar(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
    if (isPar(u, v))
        return u;
    if (isPar(v, u))
        return v;
    per(pw, LOG - 1, 0)
    {
        if (!isPar(up[v][pw], u))
            v = up[v][pw];
    }
    return up[v][0];
}
int F[maxn << 1];
void insert(int pos, int val)
{
    while (pos <= T)
    {
        F[pos] += val;
        pos += lowbit(pos);
    }
}
int sum(int pos)
{
    int res = 0;

    while (pos > 0)
    {
        res += F[pos];
        pos -= lowbit(pos);
    }
    return res;
}
void addOnPath(int v, int l)
{
    while (v != l)
    {
        insert(tin[v], 1);
        insert(tout[v], -1);
        v = up[v][0];
    }
}
int ans[maxm];
int main()
{
    n = read(), m = read();
    init();
    rep(i, 1, m)
    {
        e[i][0] = read(), e[i][1] = read(), e[i][2] = read();
        int u = e[i][0], v = e[i][1], w = e[i][2];
        if (unite(u, v))
        {
            ans[i] = 1;
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
    }
    buildLCA();
    rep(i, 1, m)
    {
        if (ans[i] == 1)
            continue;
        int u = e[i][0], v = e[i][1], w = e[i][2];
        int xorPath = xr[u] ^ xr[v];
        if ((xorPath ^ w) != 1)
            continue;
        int l = lca(u, v);

        int uesdOnPath = sum(tin[u]) + sum(tin[v]) - 2 * sum(tin[l]);
        if (uesdOnPath > 0)
            continue;
        ans[i] = 1;
        addOnPath(u, l);
        addOnPath(v, l);
    }
    rep(i, 1, m)
    {
        if (ans[i] == 1)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}