Educational Codeforces Round 171 (Rated for Div.2)【A-D题解】

A. Perpendicular Segments

数学

题意

构造两条线段，满足：

  1. 端点均在 和 范围内，且为整数；
  2. 线段长度大于等于 ；
  3. 两线段所在的直线垂直。

题解

观察 ，且保证有解。

越大越难构造出满足条件的两条线段。最坏情况是 ，。此时只有一种构造方法，就是两条对角线。

既然题目保证是有解的，那就按最坏的情况考虑，取 ，然后构造两条对角线即可。

参考代码

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
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

void solve() {
  int X, Y, K;a
  cin >> X >> Y >> K;
  int mn = min(X, Y);
  cout << 0 << ' ' << 0 << ' ' << mn << ' ' << mn << '\n';
  cout << 0 << ' ' << mn << ' ' << mn << ' ' << 0 << '\n';
}

int main(int argc, char * argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T;
  cin >> T;
  while (T--) {
    solve();
  }

  return 0;
}

复杂度分析

  • 时间复杂度：。
  • 空间复杂度：。

B. Black Cells

贪心

题意

初始状态所有格子都是白色，你可以执行如下操作：

  • 选择两个 不同的 位置，然后将它们改为黑色，并且这两个位置的距离不超过 。

你需要将 中的所有位置改为黑色。另外，你可以至多选择 个没有在 中出现过的位置改为黑色。

计算 的最小值。

题解

根据贪心思想，优先选择相邻的两个位置即可。

可按照 的奇偶性分类讨论：

  • 如果为偶数，则答案是
  • 如果为奇数，则需要选择在哪两个数字中间选择加入额外一次操作。即假设两个数是 和 ，在它们之间选择一个位置 改为黑色。这样做之后， 和 就不会对答案有所贡献。

偶数的情况比较好求，直接遍历求最大值即可。如何求奇数的情况呢？

可以 枚举 在哪个数字后做一次额外的操作。设枚举在 后做一次额外的操作，即如果 ，则，错位计算相邻位置的差值。然后取最小的插值即可。

参考代码

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
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
  int n;
  cin >> n;

  vector<i64> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  i64 ans = 1;
  if (n % 2 == 0) {
    for (int i = 0; i < n; i += 2) {
      ans = max(ans, a[i + 1] - a[i]);
    }
  } else {
    ans = 1E18;
    for (int i = 0; i < n; i += 2) {
      i64 res = 1;
      for (int j = 0; j < n; j += 2) {
        if (i == j) {
          j--;
          continue;
        }
        res = max(res, a[j + 1] - a[j]);
      }
      ans = min(ans, res);
    }
  }

  cout << ans << '\n';
}

int main(int argc, char * argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T;
  cin >> T;
  while (T--) {
    solve();
  }

  return 0;
}

复杂度分析

  • 时间复杂度：，其中 是数组 的大小。
  • 空间复杂度：。

C. Action Figures

贪心

题意

给你一个长度为 的字符串 ，字符串只包含字符 和 。

  • 若 s[i] = 1，表示可以购买 （包括 ) 之前的任意数字 ，数字 的价值就是 。
  • 若 s[i] = 0，则无法购买，需要在之后的时间购买，即 的位置。

另外，如果在 时购买数字的数量至少有 个，则最贵的那个数字直接免费（显然就是 ）。

每个数字需要且只能购买一次，求购买所有数字最小的花费。

题解

题目保证有解，也就是最后 。

最坏的情况就是没有享受任何“折扣”，即 。

可以从后往前枚举，如果当前数字可以免费，条件有两个：

  • 当前数字可以在此时购买，即 s[i] = 1；
  • 设需要的数字个数，记 。
    • 如果 ，表示可以在 之前选择一个数字与当前 一起购买，从而当前数字就 Free 了。更新 ；
    • 否则，就无法购买，。

在这种操作下，根据贪心思想，我们每次保证了当前折扣的是可以购买的最大值，从而使得最后的总花费最小。

参考代码

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

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  i64 ans = 1LL * n * (n + 1) / 2;
  int need = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == '1' && need + 1 <= i) {
      ans -= i + 1;
      need++;
    } else {
      need = max(0, need - 1);
    }
  }

  cout << ans << '\n';
}

int main(int argc, char * argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T;
  cin >> T;
  while (T--) {
    solve();
  }

  return 0;
}

复杂度分析

  • 时间复杂度：。
  • 空间复杂度：，其中 表示字符串 的长度。

D. Sums of Segments

前缀和

题意

给定数组 ，用数组 构造了一个区间和数组 （具体构造方法见题目）。

次询问，每次询问数组 区间 的区间和。

题解

我们知道可以用 前缀和 求区间和，显然 数组的区间和也可以用它来求得。

不妨先求 的前缀和，记 ，即

然后观察 数组，不难发现它可以根据 后缀 来划分成为 段。要求其前缀和，可以根据 后缀对答案的贡献 确定在哪一段，如下图所示。

例如求 ，当 越大，后缀也就越长，所包含的后缀个数也会越多。如下图所示，当 时，包含后缀的最多有 段，并且后缀长度是 。

也就是说具有单调性，因此可以用 二分 求得当前后缀的个数以及长度。

1
2
3
4
5
6
7
8
while (l < r) {
  int mid = (l + r + 1) / 2;
  if (x >= 1LL * mid * (n - mid + 1 + n) / 2) {
    l = mid;
  } else {
    r = mid - 1;
  }
}

确定后缀的长度以及个数，设为 ，它将 的前缀和分成两个部分：

  • ：前 段是完整的，因此这部分可根据 的构造方法求出前缀和。
  • ：剩下的元素因为确定了后缀的长度，进而确定了余下这段是从 开始的区间和。

即 的 区间和为

其中 是剩余的个数，即

根据上述分析，得到暴力做法：

1
2
3
4
5
6
7
8
9
for (int i = 0; i < u; i++) {
  for (int j = i; j <= n; j++) {
    res += pre[j] - pre[i];
  }
}
x -= 1LL * u * (n - u + 1 + n) / 2;
for (int j = u; j <= u + x; j++) {
  res += pre[j] - pre[u];
}

优化1

上述做法的时间复杂度为 。观察每一段是若干个后缀组成，每段之间的不同是前缀。

如 和 相差的是 ，也就是

所以我们可以先求出前缀和 的前缀和，记 ，即

然后可以 时间复杂度内求出当前段的和，从而把时间复杂度降为 。

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i<= n; i++) {
  ppre[i + 1] = ppre[i] + pre[i];
}
...
// 求b的前缀和
for (int i = 0; i < u; i++) {
  res += ppre[n + 1] - ppre[i];
  res -= pre[i] * (n - i + 1);
}
x -= u * (n - u + 1 + n) / 2;
res += ppre[n + x - 1] - ppre[u];
res -= pre[u] * (x + 1);

优化2

思考优化之前完整的段的做法，前缀和能快速求出区间和是基于元素的值都是固定不变的，因此用前缀和的思想来优化。

首先假设前 段都是完整的，即 。显然，这个值比预期的结果大，还需要减去某个部分。

之前我们求出了前缀和 ，通过这个前缀和可以快速求出一个段的区间和。类似的，我们可以继续求它的前缀和，记 spre，即

这样做的目的是为了 求出前 段的前缀和，显然我们还需要另外一个前缀和，也就是上面循环中减去的部分，记 dpre，即

然后就可以在 的时间复杂度内求出前 段的前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 0; i <= n; i++) {
  dpre[i + 1] = dpre[i] + pre[i] * i;
}
for (int i = 0; i <= n; i++) {
  spre[i + 1] = spre[i] + ppre[i];
}
...
// 求b的前缀和
res += ppre[n + 1] * u;
res -= spre[u];
res -= ppre[u] * (n + 1);
res += dpre[u];
x -= u * (n - u + 1 + n) / 2;
res += ppre[n + x - 1] - ppre[u];
res -= pre[u] * (x + 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
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
  int n;
  cin >> n;

  vector<i64> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  vector<i64> pre(n + 1);
  for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + a[i];
  }

  vector<i64> s0(n + 2), s1(n + 2), ss(n + 2);
  for (int i = 0; i <= n; i++) {
    s0[i + 1] = s0[i] + pre[i];
    s1[i + 1] = s1[i] + pre[i] * i;
  }

  for (int i = 0; i <= n; i++) {
    ss[i + 1] = ss[i] + s0[i];
  }

  auto query = [&](i64 x) {
    i64 l = 0, r = n;
    while (l < r) {
      int mid = (l + r + 1) / 2;
      if (x >= 1LL * mid * (n + n  - mid + 1) / 2) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }

    i64 res = 0;
    res += s0[n + 1] * l;
    res -= ss[l];
    res -= s0[l] * (n + 1);
    res += s1[l];
    x -= 1LL * l * (n + n - l + 1) / 2;
    res += s0[l + x + 1] - s0[l];
    res -= pre[l] * (x + 1);

    return res;
  };


  int q;
  cin >> q;
  while (q--) {
    i64 l, r;
    cin >> l >> r;
    cout << query(r) - query(l - 1) << '\n';
  }
}

int main(int argc, char * argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  while (T--) {
    solve();
  }

  return 0;
}

复杂度分析

  • 时间复杂度：

    预处理的时间复杂度是 ，用于求出上述分析中的前缀和；在 次查询中，用二分算法求得完整的段数，因此时间复杂度是 。

    最后时间复杂度为 ，其中 是数组 的长度， 是查询次数。

  • 空间复杂度：。