Codeforces Global Round 5

A - Balanced Rating Changes

偶数直接除。奇数的话只要上取整的数目等于下取整的数目就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*

val s = Scanner(System.`in`)

fun main() {
val n = s.nextInt()
val a = Array(n) { s.nextInt() }

var zheng = 1
var fu = 1
a.forEach {
if (it % 2 == 0)
println(it / 2)
else {
if (it > 0) {
println(it / 2 + zheng)
zheng = 1 - zheng
} else {
println(it / 2 - fu)
fu = 1 - fu
}
}
}
}

B - Balanced Tunnel

如果一辆车$i$超车了,那么就会存在至少一辆车$j$,使得进来的序列中$j$在$i$前面,但出来的序列中$j$在$i$后面。

那么可以将出去的序列的每一项替换成它进去时的位次。然后从后往前扫一遍出去的序列。若扫到车$i$时,已经扫过的车里面有位次小于车$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
51
52
53
import java.util.*

val s = Scanner(System.`in`)

class TreeArray(val size: Int) {
val array = Array<Int>(size + 1) { 0 }
private fun lowbit(x: Int) = x and (-x)
fun add(pos: Int, value: Int) {
if (pos !in 1..size)
throw IndexOutOfBoundsException()
var i = pos
while (i <= size) {
array[i] += value
i += lowbit(i)
}
}

fun perfixSum(pos: Int): Int {
if (pos !in 1..size)
throw IndexOutOfBoundsException()
var i = pos
var ans = 0
while (i > 0) {
ans += array[i]
i -= lowbit(i)
}
return ans
}
}

fun main() {
val n = s.nextInt()

val mapping = Array(n + 1) { 0 }
for (i in 1..n) {
mapping[s.nextInt()] = i
}

val b = Array(n + 1) { 0 }
for (i in 1..n) {
b[i] = mapping[s.nextInt()]
}

val ta = TreeArray(n)
var cnt = 0;
for (i in n downTo 1) {
val it = b[i]
if (ta.perfixSum(it) != 0)
cnt++
ta.add(it, 1)
}
print(cnt)
}

C2 - Balanced Removals (Harder)

x坐标相同的点组成了一个平面,如果一个平面内的点的数量是偶数那么直接删光,如果是奇数就只剩下一个点。每个平面都删一遍后,剩下的点都在不同的平面,那么相邻两个平面的点配对删掉就可以了。

至于删平面内的点,就是上述算法的二维情形。

至于删直线内的点,就直接相邻两个配对删掉就好了。

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
import java.util.*

val s = Scanner(System.`in`)

data class Point(val x: Int, val y: Int, val z: Int, val no: Int) : Comparable<Point> {
override fun compareTo(other: Point): Int {
return compareValuesBy(this, other, Point::x, Point::y, Point::z)
}
}

var p = ArrayList<Point>()

fun main() {
val n = s.nextInt()
repeat(n) {
val x = s.nextInt()
val y = s.nextInt()
val z = s.nextInt()
p.add(Point(x, y, z, it + 1))
}
p.sort()
remove3D(0 until n)
}

fun remove1D(range: IntRange): Int? {
var prev: Int? = null
for (i in range) {
prev = if (prev == null)
i
else {
println("${p[prev].no} ${p[i].no}")
null
}
}
return prev
}

fun remove2D(range: IntRange): Int? {
var prev: Int? = null
var l = range.first
while (l in range) {
var r = l
while (r + 1 in range && p[r + 1].y == p[l].y)
r++
val ret = remove1D(l..r)
if (ret != null) {
prev = if (prev == null)
ret
else {
println("${p[prev].no} ${p[ret].no}")
null
}
}
l = r + 1
}
return prev
}

fun remove3D(range: IntRange): Int? {
var prev: Int? = null
var l = range.first
while (l in range) {
var r = l
while (r + 1 in range && p[r + 1].x == p[l].x)
r++
val ret = remove2D(l..r)
if (ret != null) {
prev = if (prev == null)
ret
else {
println("${p[prev].no} ${p[ret].no}")
null
}
}
l = r + 1
}
return prev
}

D - Balanced Playlist

首先,停不下来意味着最小值要大于最大值的一半。特判一下就好。

之后,考虑到这是个会循环播放的歌单。从$i$开始播放,可能会停在第一周目,也可能会停在第二周目。因为第一周目能否停下取决于之前播放过的曲目的最大值,第二周目能否停下则取决于全部曲目的最大值。但是如果可以停下来就不会超过两周目。所以简单把歌单复制成三倍长度的就好。

记$i$后面第一个比$i$大的数所在位置为$x_i$,第一个比$i$的一半小的数所在位置为$y_i$. 那么$c_i$可以表示为:

问题就在于如何快速找到$x_i$和$y_i$. 一个比较优秀的做法是在ST表上二分查找,一次查找的时间复杂度是$O(\log n)$,则总的时间复杂度是$O(n\log 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
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
#include <iostream>
#include <cmath>
using namespace std;
constexpr int MAXN = 100005;
int n, a[MAXN * 3], x[MAXN * 3], y[MAXN * 3], c[MAXN * 3];
int log2s[MAXN * 3];
void init_log2s()
{
for (int i = 1; i <= n * 3; i++)
log2s[i] = log2(i);
}
namespace st1
{
int st[MAXN * 3][20];
void init()
{
for (int i = 1; i <= 3 * n; i++)
st[i][0] = a[i];
for (int j = 1; (1 << j) <= 3 * n; j++)
{
for (int i = 1; i <= 3 * n; i++)
{
if (i + (1 << (j - 1)) <= 3 * n)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
else
st[i][j] = st[i][j - 1];
}
}
}
int get(int l, int r)
{
int k = log2s[r - l + 1];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
} // namespace st1

namespace st2
{
int st[MAXN * 3][20];
void init()
{
for (int i = 1; i <= 3 * n; i++)
st[i][0] = a[i];
for (int j = 1; (1 << j) <= 3 * n; j++)
{
for (int i = 1; i <= 3 * n; i++)
{
if (i + (1 << (j - 1)) <= 3 * n)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
else
st[i][j] = st[i][j - 1];
}
}
}
int get(int l, int r)
{
int k = log2s[r - l + 1];
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
} // namespace st2

int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i + n] = a[i + 2 * n] = a[i];
}

init_log2s();
st1::init();
st2::init();

for (int i = 1; i <= 3 * n; i++)
{
int val = st1::get(i + 1, n * 3);
if (i == n * 3 || val <= a[i])
x[i] = -1;
else
{
int l = i + 1, r = n * 3;
while (l < r && l <= n * 3)
{
int mid = (l + r) / 2;
int val = st1::get(l, mid);
if (val > a[i])
r = mid;
else
l = mid + 1;
}
x[i] = l;
}
}

for (int i = 1; i <= 3 * n; i++)
{
if (i == n * 3 || 2 * st2::get(i + 1, n * 3) >= a[i])
y[i] = -1;
else
{
int l = i + 1, r = n * 3;
while (l < r && l <= n * 3)
{
int mid = (l + r) / 2;
int val = st2::get(l, mid);
if (2 * val < a[i])
r = mid;
else
l = mid + 1;
}
y[i] = l;
}
}

for (int i = 3 * n; i >= 1; i--)
{
if (i <= n && 2 * st2::get(i, i + 2 * n - 1) >= st1::get(i, i + 2 * n - 1))
c[i] = -1;
else if (x[i] == -1 && y[i] == -1)
c[i] = 1;
else if (x[i] == -1)
c[i] = y[i] - i;
else if (y[i] == -1)
c[i] = x[i] - i + c[x[i]];
else if (x[i] < y[i])
c[i] = x[i] - i + c[x[i]];
else
c[i] = y[i] - i;
}

for (int i = 1; i <= n; i++)
cout << c[i] << ' ';

return 0;
}
Author: ssttkkl
Link: https://ssttkkl.github.io/Codeforces/2019/10/Codeforces-Global-Round-5/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.