Codeforces Round 979 (Div.2)【A-E题解】

A. A Gift From Orangutan

贪心

题意

构造一个 数组，记前缀最大值和前缀最小值分别为 和 ，求最大值 。

题解

把最大值和最小值放在最前面，因此答案为 。

参考代码

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

void solve() {
  int n;
  cin >> n;
  int mx = 0, mn = 1001;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    mx = max(mx, x);
    mn = min(mn, x);
  }
  cout << (n - 1) * (mx - mn) << '\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. Minimise Oneness

组合数学 思维

题意

构造一个长度为 的 01 序列 ，定义 为 的所有非空且仅包含 的子序列个数， 为 的所有非空且至少包含一个 的个数，所构造的 要满足 最小。

题解

设 的个数为 ，则 。

对于 ，只要有一个 ，其他位任意，所以 。

因此要使 和 接近，只要 尽可能大，即 。

综上，只要构造一个 1000...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
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  int n;
  cin >> n;
  cout << string(1, '1') + string(n - 1, '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;
}

复杂度分析

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

C. A TRUE Battle

位运算 博弈

题意

给定长度为 的 01 序列，可以在两个字符间添加 or 或 and 运算符。Alice 先手且想到使得最后序列的值为 true，Bob 反之，判断 Alice 是否能获胜。

如 1 0 0，Alice 先手，在 1 和 0 之间添加一个 or。此时无论 Bob 添加 or 还是 and，即 1 or 0 and 0 = 1 or 1 = true 或 1 or 0 or 0 = true，结果都为 true。

题解

首先，只要首尾有一个 1，Alice 只要在它旁边添加 or 即可。

如 1 0 0 0，无论右边的情况如何，最坏为 false，然后 1 or 0 = true。

对于其他情况，即 1 在中间不在首尾。有两种情况：

  1. 无连续 1：1 的左右必然一个 or（Alice） 和 and（Bob），最终结果为 0 or 1 and 0 = false。
  2. 有连续 1：这段 1 的左右必然一个 or（Alice） 和 and（Bob），最终为 0 or 1 ... 1 and 0 = true，可以看出，中间的运算符不会影响最终结果。

小技巧

在查找之前在首尾添加 1，然后是否有查找 11 即可。如果存在则 Alice 获胜，否则 Bob 获胜。

参考代码

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

void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  s = '1' + s + '1';
  if (s.find("11") != -1) {
    cout << "YES" << '\n';
  } else {
    cout << "NO" << '\n';
  }
}

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

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

  return 0;
}

复杂度分析

  • 时间复杂度：，其中 是 01 序列的长度。
  • 空间复杂度：。

D. QED’s Favorite Permutation

模拟

题意

一个排列 和一个操作序列 。可以执行任意次操作：

  • 如果 s[i] = 'L'，则 p[i] 可以和 p[i-1] 交换；
  • 如果 s[i] = 'R'，则 p[i] 可以和 p[i+1] 交换；

接下来有 次询问，每次查询都是在线处理，将 s[x] 替换成另一个字符。问在替换字符后的 的条件下，是否可以使得 升序。

题解

如果要交换 和 （），需要保证 中没有 ，且满足 s[k] = 'L' 并且 s[k+1] = 'R'。

因此需要找出所有的 ，并且要确保它们不在需要进行交换的区间中即可。

官方题解 中使用 差分 维护区间中包含 的个数。这里提供另外一种做法。

不妨先确定交换的方向，当 且 时，也就是大数在前，需要与后面的小数进行交换。具体做法可以求出前缀最大值 preMax，如果 ，表明当前位置需要和后面的某个数字进行交换，将当前位置进行标记，记为 bad。

如果满足 且 ，其中 表示 从 开始、截取长度为 2 的一个子串，则表示当前数字无法交换，统计符合该条件的个数，记 cnt。

当改变 时，影响到两侧情况，需要重新统计 cnt。即需要重新判断 、 和 、。

若可以使得排列为升序，则需要满足 ，即没有需要交换的数字或者数字可以与后面的数字进行交换。

参考代码

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

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

  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }
  for (int i = 1; i < n; i++) {
    p[i] = max(p[i - 1], p[i]);
  }

  vector<bool> bad(n);
  for (int i = 1; i < n; i++) {
    if (p[i - 1] != i) {
      bad[i] = true;
    }
  }

  string s;
  cin >> s;

  int cnt = 0;
  for (int i = 1; i < n; i++) {
    if (bad[i] && s.substr(i - 1, 2) == "LR") {
      cnt++;
    }
  }
  while (q--) {
    int x;
    cin >> x;
    x--;
    if (bad[x] && s.substr(x - 1, 2) == "LR") {
      cnt--;
    }
    if (bad[x + 1] && s.substr(x, 2) == "LR") {
      cnt--;
    }
    if (s[x] == 'R') {
      s[x] = 'L';
    } else {
      s[x] = 'R';
    }
    if (bad[x] && s.substr(x - 1, 2) == "LR") {
      cnt++;
    }
    if (bad[x + 1] && s.substr(x, 2) == "LR") {
      cnt++;
    }
    if (cnt == 0) {
      cout << "YES" << '\n';
    } else {
      cout << "NO" << '\n';
    }
  }
}

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

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

  return 0;
}

复杂度分析

  • 时间复杂度：，其中 为排列长度， 为操作次数。
  • 空间复杂度：。

E. MEXimize the Score

组合数学 动态规划

题意

定义数组 的分数为 的最大值，其中 表示 的一个非空子集，并且 之间互斥， 表示没有在 出现的最小正整数。换句话说，就是把 划分成 （） 个非空子集，其分数就是

求数组 的所有非空子序列的分数之和。

题解

根据贪心思想，要把 尽可能划分的更“平均”。

例如 ，则可以划分为 、 和 ，分数为 。

对于一个数组 ，统计每个元素出现的次数，记 cnt。假设构造的子集为 ，显然，为了分数最大， 也要尽可能大。换言之，找到最大的 ，满足 ，且对于所有的 （）满足 。

首先，我们需要枚举 确定划分的个数。根据上述分析，找到最大的 ，对于 且 。

1
2
3
while(p < n && cnt[p] >= k) {
  p++;
}

考虑 将序列分成两个部分， 表示当前可以枚举到的最大 值。

对于序列后缀，即 ，后缀不会影响一个序列的 的值，显然，总方案数为 。

对于序列前缀，即 ，类似背包问题，需要考虑当前剩余元素的个数，假设用 tmp 来维护当前剩余元素的个数。

定义 为 对答案的贡献。如果 ，说明 可以被放到 个分区，方案数为 ；否则无法进入分区。

将所有的前缀累乘得到总贡献，即 。

然后根据乘法原理将两者相乘加入到答案中。

参考代码

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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#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;

template<typename T>
constexpr T power(T a, u64 b) {
  T res{1};
  for (; b != 0; b /= 2, a *= a) {
    if (b % 2 == 1) {
      res *= a;
    }
  }
  return res;
}

template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
  return 1ULL * a * b % P;
}

template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
  u64 res = a * b * u64(1.L * a * b / P - 0.5L) * P;
  res %= P;
  return res;
}

template<typename U, U P>
requires std::unsigned_integral<U>
struct ModIntBase {
public:
  constexpr ModIntBase() : x(0) {}

  template<typename T>
  requires std::integral<T>
  constexpr ModIntBase(T x_) : x(norm(x_ % T{P})) {}

  constexpr static U norm(U x) {
    if ((x >> (8 * sizeof(U) - 1) & 1) == 1) {
      x += P;
    }
    if (x >= P) {
      x -= P;
    }
    return x;
  }

  constexpr U val() const {
    return x;
  }

  constexpr ModIntBase operator-() const {
    ModIntBase res;
    res.x = norm(P - x);
    return res;
  }

  constexpr ModIntBase inv() const {
    return power(*this, P - 2);
  }

  constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
    x = mulMod<P>(x, rhs.val());
    return *this;
  }

  constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
    x = norm(x + rhs.x);
    return *this;
  }

  constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
    x = norm(x - rhs.x);
    return *this;
  }

  constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
    return *this *= rhs.inv();
  }

  friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
    lhs *= rhs;
    return lhs;
  }

  friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
    lhs += rhs;
    return lhs;
  }

  friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
    lhs -= rhs;
    return lhs;
  }

  friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
    lhs /= rhs;
    return lhs;
  }

  friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
    return os << a.val();
  }

  friend constexpr bool operator==(ModIntBase lhs, ModIntBase rhs) {
    return lhs.val() == rhs.val();
  }

  friend constexpr bool operator!=(ModIntBase lhs, ModIntBase rhs) {
    return lhs.val() != rhs.val();
  }

  friend constexpr bool operator<(ModIntBase lhs, ModIntBase rhs) {
    return lhs.val() < rhs.val();
  }

private:
  U x;
};

template<u32 P>
using ModInt = ModIntBase<u32, P>;

template<u64 P>
using ModInt64 = ModIntBase<u64, P>;

constexpr u32 P = 998244353;
using Z = ModInt<P>;

struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }

    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);

        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }

    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

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

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

  vector<Z> suf(n);
  suf[n - 1] = 1;
  for (int i = n - 1; i > 0; i--) {
    suf[i - 1] = suf[i] * power(Z(2), cnt[i]);
  }

  Z ans = 0;
  int p = 0;
  vector<Z> f(n);
  auto tmp = cnt;
  for (int k = n; k > 0; k--) {
    while(p < n && cnt[p] >= k) {
      p++;
    }
    Z res = 1;
    for (int i = 0; i < p; i++) {
      while(tmp[i] >= k) {
        f[i] += comb.binom(cnt[i], tmp[i]);
        tmp[i]--;
      }
      res *= f[i];
      ans += res * suf[i];
    }
  }

  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;
}

复杂度分析

  • 时间复杂度：虽然代码看上去时间复杂度是 ，但是因为 确定了上限，因此实际的时间复杂度接近 ，其中 是数组 的长度。
  • 空间复杂度：。