Namomo Spring Camp 2022 Div1 每日一题记录 (Week 14)

发表于 更新于 分类于 ， 本文字数： 2.9k 阅读时长 ≈ 11 分钟

Namomo Spring Camp 2022 Div1 每日一题记录 (2022.05.28-2022.06.03)

序列中 ab 的个数 (CF1268B)

题目链接

3 s, 1024 MB

题目描述

给一个图表，图表是一个直方图，\(n\) 列的高度分别为 \(a_1, a_2, \dots, a_n\)\((a_1 \ge a_2 \ge a_3 .... \ge a_n)\), 你有许多大小为 \(1 \times 2\) 的多米诺骨牌 (可以旋转), 不重叠最多可以放置多少个呢

输入格式

第一行一个数字 \(n\)

接下来一行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)

输出格式

一个数，表示答案

样例输入

1
2
5
3 2 2 2 1

样例输出

1
4

数据规模

所有数据保证 \(1\leq n\leq 300000, 1 \leq a_i \leq 300000\)

解题思路

二分图染色

结论题，如果 Young 表二分图染色后黑白两色的格子数相等，则可以用骨牌密铺

代码参考

Show code

CodeForces_1268Bview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
auto solve() -> void {
  int n;
  cin >> n;
  i64 cnt1 = 0, cnt2 = 0;
  _for(i, 1, n, x) {
    cin >> x;
    cnt1 += (x + (x & i & 1)) / 2;
    cnt2 += (x + !(x & i & 1)) / 2;
  }
  cout << min(cnt1, cnt2);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

单词合并 (CF1200E)

题目链接

2 s, 256 MB

题目描述

\(xyq\) 有 \(n\) 个单词，他想把这个 \(n\) 个单词变成一个句子

具体来说就是从左到右依次把两个单词合并成一个单词

合并两个单词的时候，要找到最大的 \(i(i\ge0)\), 满足第一个单词的长度为 \(i\) 的后缀和第二个单词长度为 \(i\) 的前缀相等，然后把第二个单词第 \(i\) 位以后的部分接到第一个单词后面

请你输出最后合并后的单词

输入描述

第一行一个整数 \(n(n\leq 10^5)\) 表示单词的个数

接下来一行 \(n\) 个字符串 \(s\), 字符串之间用空格分割，分别代表每个单词。保证字符串总长不超过 \(10^6\)

输出描述

一行一个字符串表示合并后的答案

输入样例

1
2
5
sample please ease in out

输出样例

1
sampleaseinout

解题思路

Z 算法 / Hash

板子题，把合并的字符串和当前输入的字符串拼起来跑个 KMP 即可

代码参考

Show code

CodeForces_1200Eview raw
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
230
231
232
233
234
235
236
237
238
239
240
241
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
namespace fast_io {
namespace type_traits {
template <class Tp>
using is_int = typename std::conditional<(std::is_integral<Tp>::value &&
                                          std::is_signed<Tp>::value) ||
                                           std::is_same<Tp, __int128_t>::value,
                                         std::true_type,
                                         std::false_type>::type;
template <class Tp>
using is_uint =
  typename std::conditional<(std::is_integral<Tp>::value &&
                             std::is_unsigned<Tp>::value) ||
                              std::is_same<Tp, __uint128_t>::value,
                            std::true_type,
                            std::false_type>::type;
template <class Tp>
using make_uint = typename std::conditional<
  std::is_same<Tp, __int128_t>::value,
  __uint128_t,
  typename std::conditional<std::is_signed<Tp>::value,
                            std::make_unsigned<Tp>,
                            std::common_type<Tp>>::type>::type;
}  // namespace type_traits
template <size_t BUFFER_SIZE>
class FastIn {
  using self = FastIn<BUFFER_SIZE>;

protected:
  char buffer_[BUFFER_SIZE], *now_ = buffer_, *end_ = buffer_;
  FILE *file_;

public:
  explicit FastIn(FILE *file = stdin) noexcept: file_(file) {}
  char fetch() noexcept {
    return this->now_ == this->end_ &&
               (this->end_ = (this->now_ = this->buffer_) +
                             fread(this->buffer_, 1, BUFFER_SIZE, this->file_),
                this->now_ == this->end_) ?
             EOF :
             *(this->now_)++;
  }
  char visit() noexcept {
    return this->now_ == this->end_ &&
               (this->end_ = (this->now_ = this->buffer_) +
                             fread(this->buffer_, 1, BUFFER_SIZE, this->file_),
                this->now_ == this->end_) ?
             EOF :
             *(this->now_);
  }
  void set_file(FILE *file) noexcept {
    this->file_ = file;
    now_ = end_ = buffer_;
  }
  template <
    typename Tp,
    typename std::enable_if<type_traits::is_int<Tp>::value>::type * = nullptr>
  self &read(Tp &n) noexcept {
    bool is_neg = false;
    char ch = this->fetch();
    while (!isdigit(ch)) {
      is_neg |= ch == '-';
      ch = this->fetch();
    }
    n = 0;
    while (isdigit(ch)) {
      (n *= 10) += ch & 0x0f;
      ch = this->fetch();
    }
    if (is_neg) n = -n;
    return *this;
  }
  template <
    typename Tp,
    typename std::enable_if<type_traits::is_uint<Tp>::value>::type * = nullptr>
  self &read(Tp &n) noexcept {
    char ch = this->fetch();
    while (!isdigit(ch)) ch = this->fetch();
    n = 0;
    while (isdigit(ch)) {
      (n *= 10) += ch & 0x0f;
      ch = this->fetch();
    }
    return *this;
  }
  self &read(char &n) noexcept {
    n = this->fetch();
    return *this;
  }
  self &read(char *n) noexcept {
    char *n_ = n;
    while (!isgraph(*n_ = this->fetch()));
    while (isgraph(*(++n_) = this->fetch()));
    *n_ = '\0';
    return *this;
  }
  self &read(std::string &n) noexcept {
    n.clear();
    char n_;
    while (!isgraph(n_ = this->fetch()));
    n.push_back(n_);
    while (isgraph(n_ = this->fetch())) n.push_back(n_);
    return *this;
  }
  self &getline(char *n) noexcept {
    char *n_ = n;
    while (!isprint(*n_ = this->fetch()));
    while (isprint(*(++n_) = this->fetch()));
    *n_ = '\0';
    return *this;
  }
  self &getline(std::string &n) noexcept {
    char n_;
    while (!isprint(n_ = this->fetch()));
    n.push_back(n_);
    while (isprint(n_ = this->fetch())) n.push_back(n_);
    return *this;
  }
};
template <size_t BUFFER_SIZE, size_t INT_BUFFER_SIZE>
class FastOut {
  using self = FastOut<BUFFER_SIZE, INT_BUFFER_SIZE>;

private:
  char int_buffer_[INT_BUFFER_SIZE], *now_ib_;

protected:
  char buffer_[BUFFER_SIZE], *now_ = buffer_;
  const char * const end_ = buffer_ + BUFFER_SIZE;
  FILE *file_;

public:
  explicit FastOut(FILE *file = stdout) noexcept: file_(file) {}
  ~FastOut() noexcept { this->flush(); }
  void flush() noexcept {
    fwrite(this->buffer_, 1, this->now_ - this->buffer_, this->file_);
    this->now_ = this->buffer_;
  }
  void set_file(FILE *file) noexcept { this->file_ = file; }
  self &linebreak() noexcept {
    this->write('\n');
    return *this;
  }
  self &space() noexcept {
    this->write(' ');
    return *this;
  }
  self &write(const char &n) noexcept {
    if (this->now_ == this->end_) this->flush();
    *(this->now_++) = n;
    return *this;
  }
  self &write(const char *n) noexcept {
    size_t len = strlen(n), l_;
    const char *n_ = n;
    while (this->now_ + len >= this->end_) {
      l_ = this->end_ - this->now_;
      memcpy(this->now_, n_, l_);
      this->now_ += l_;
      n_ += l_;
      len -= l_;
      this->flush();
    }
    memcpy(this->now_, n_, len);
    this->now_ += len;
    return *this;
  }
  template <
    class Tp,
    typename std::enable_if<type_traits::is_int<Tp>::value>::type * = nullptr>
  self &write(Tp n) noexcept {
    if (n < 0) {
      this->write('-');
      n = -n;
    }
    return this->write(
      static_cast<typename type_traits::make_uint<Tp>::type>(n));
  }
  template <
    class Tp,
    typename std::enable_if<type_traits::is_uint<Tp>::value>::type * = nullptr>
  self &write(Tp n) noexcept {
    this->now_ib_ = this->int_buffer_ + INT_BUFFER_SIZE - 1;
    do { *(--(this->now_ib_)) = char(n % 10) | '0'; } while (n /= 10);
    this->write(this->now_ib_);
    return *this;
  }
  self &write(const std::string &str) noexcept {
    this->write(str.c_str());
    return *this;
  }
};
const std::size_t BUFFER_SIZE = 1 << 21;
FastIn<BUFFER_SIZE> fast_in;
FastOut<BUFFER_SIZE, 21> fast_out;
}  // namespace fast_io
using fast_io::fast_in;
using fast_io::fast_out;
using namespace std;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 1e6 + OFFSET, M = 2e5 + OFFSET, K = 21;
int kmp[N];
auto solve() -> void {
  int n;
  fast_in.read(n);
  string s, t;
  _for(i, 1, n) {
    fast_in.read(t);
    auto len = min(s.size(), t.size());
    auto __ = t.size();
    t.push_back('#');
    t.append(s.end() - len, s.end());
    for (int j = kmp[0] = -1, i = 1; i < t.size(); kmp[i++] = j) {
      while (~j && t[j + 1] != t[i]) j = kmp[j];
      if (t[j + 1] == t[i]) ++j;
    }
    s.append(t.begin() + kmp[t.size() - 1] + 1, t.begin() + __);
  }
  fast_out.write(s);
}
int main() {
  solve();
  return 0;
}

不降子数组游戏 (CodeForces Gym 102984D)

题目链接

3 s, 1024 MB

题目描述

Yuto 和 Platina 准备玩一个不降子数组游戏

具体的，给定一个长度为 \(N\) 的数组 \(A\), 和区间限制 \(L\) 和 \(R\)

Yuto 首先在 \([L, R]\) 中选择一个数字，并展示给 Platina 看

随后 Platina 也会选择一个在 \([L, R]\) 中的数字

我们不妨设 Yuto 选择了数字 \(a\), Platina 选择了数字 \(b\)

这局游戏的得分是 \(A[min(a,b):max(a,b)]\) 的不降子数组的个数. (\(A[l:r]\) 表示由数组 \(A\) 下标从 \(l\) 到 \(r\) 这一连续段构成的新数组)

注：数组 \(B\) 的子数组是从 \(B\) 的头尾连续删除若干 (可以为空) 个元素后得到的新数组

Yuto 想要得分尽可能的小，Platina 想要得分尽可能的大

他们将会在一个数组上游戏 \(Q\) 次，对于每次游戏，请输出最后游戏的得分

输入格式

第一行输入一个正整数 \(N\), 表示数组 \(A\) 的长度

接下来一行 \(N\) 个正整数，分别表示 \(A_1\), \(A_2\), ... , \(A_N\)

第三行输入一个正整数 \(Q\), 表示游戏进行的次数

接下来 \(Q\) 行，每一行输入两个正整数，分别表示 \(L\) 和 \(R\)

对于所有数据，满足 \(1 \leq N, Q \leq 5 \times 10^5\), \(1 \leq A_i \leq 10^9\) 且 \(1 \leq L \leq R \leq N\)

输出格式

对于每次游戏，输出一个正整数，表示游戏最后的得分

样例输入

1
2
3
4
5
6
7
8
8
7 10 3 1 9 5 5 2
5
1 5
2 2
5 8
1 8
3 5

样例输出

1
2
3
4
5
4
1
4
7
3

解题思路

三分 + 分块

首先将数组分成递增的若干段，如对于样例分为 [7 10] [3] [1 9] [5 5] [2] 五段，然后每一段都可以很容易地求出得分，进而用一个前缀和即可方便地求出某一段区间的得分

对于单次查询，显然无论先手选什么，后手必选端点，而且不难发现得分对先手选的点是单峰函数，所以直接三分即可

复杂度

\(O(N+Q\log N)\)

代码参考

Show code

CodeForces_Gym_102984Dview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 5e5 + OFFSET;
int a[N];
int block_id[N], block_end[N];
i64 sum_f[N];
auto _ = [](i64 len) -> i64 { return len * (len + 1) / 2; };
i64 query(int l, int r) {
  if (l > r) swap(l, r);
  if (block_id[r] == block_id[l]) return _(r - l + 1);
  return _(r - block_end[block_id[r] - 1]) + _(block_end[block_id[l]] - l + 1) +
         sum_f[block_id[r] - 1] - sum_f[block_id[l]];
}
i64 f(int l, int r, int x) { return max(query(l, x), query(x, r)); }
i64 tri(int l, int r) {
  int mid1, mid2;
  i64 f1, f2;
  i64 ans = INT64_MAX;
  int _l = l, _r = r;
  while (_r - _l > 10) {
    f1 = f(l, r, mid1 = _l + (_r - _l) / 3);
    f2 = f(l, r, mid2 = _r - (_r - _l) / 3);
    ans = min({ans, f1, f2});
    if (f1 > f2) _l = mid1;
    else _r = mid2;
  }
  _for(i, _l, _r) chkmin(ans, f(l, r, i));
  return ans;
}
auto solve() -> void {
  int n, m;
  cin >> n >> m;
  _for(i, 1, n) cin >> a[i];
  int cnt = 1;
  _for(i, 1, n) {
    if (a[i] < a[i - 1]) ++cnt;
    block_end[block_id[i] = cnt] = i;
  }
  _for(i, 1, cnt) sum_f[i] = sum_f[i - 1] + _(block_end[i] - block_end[i - 1]);
  _for(i, 1, m, l, r) {
    cin >> l >> r;
    cout << tri(l, r) << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

子串 (数据加强版) (牛客练习赛 98 D)

题目链接

1 s, 1024 MB

题目描述

给定一个长度为 \(n\) 的 \(01\) 串，问有多少种划分，使得每一个划分出来的子串的 \(1\) 的个数组成的序列是回文的，答案对 \(998244353\) 取模

输入格式

第一行一个正整数 \(n\), 表示 \(01\) 串的长度

第二行为一个长度为 \(n\) 的 \(01\) 串

输出格式

合法的划分方案数对 \(998244353\) 取模的值

样例输入

1
2
3
101

样例输出

1
4

样例解释

合法的划分方案为: \([101],[10,1],[1,01],[1,0,1]\), 其中 \(1\) 的个数组成的序列为 \([2],[1,1],[1,1],[1,0,1]\), 这些序列都是回文的

数据规模

\(1\leq n\leq 2500\)

解题思路

组合数学

似乎加强版是想让大家写 \(O(n^2)\) DP, 然而这题有线性做法

我们从两边向内找一对 \(1\) 所在的位置，设这两个 \(1\) 外侧的若干的 \(0\) 分别有 \(x,y\) 个，那么一对 \(1\) 和这些 \(0\) 对答案产生的贡献为

\[ \sum_{k=0}^{\min\{x,y\}}\binom{x}{k}\binom{y}{k} \]

然后把这些 \(0\) 和 \(1\) 删去，继续直到找不到两个 \(1\) 为止，此时有两种情况:

  • 只剩 \(1\) 个 \(1\)

    设这个 \(1\) 左右的 \(0\) 分别有 \(x,y\) 个，不难发现这些 \(0\) 对答案产生的贡献为

    \[ \sum_{k=0}^{\min\{x,y\}}\binom{x}{k}\binom{y}{k} \]

  • 没有 \(1\)

    设这些 \(0\) 有 \(x\) 个，不难发现这些 \(0\) 对答案产生的贡献为 \(2^x\)

例如，下图的答案为

\[ \left(\sum_{k=0}^{\min\{2,4\}}\binom{x}{k}\binom{y}{k}\right)\left(\sum_{k=0}^{\min\{2,1\}}\binom{x}{k}\binom{y}{k}\right)2^2=1200 \]

复杂度

\(O(n)\)

代码参考

Show code

Daimayuan_922view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define _rfor(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 1e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
const uint32_t MOD = 998244353;
i64 qpow(i64 a, i64 b = MOD - 2, const i64 &mod = MOD) {
  i64 res(1);
  for (; b; b >>= 1, (a *= a) %= mod)
    if (b & 1) (res *= a) %= mod;
  return res;
};
i64 fact[N * 2], inv_fact[N];
auto __STATIC__ = []() {
  static i64 ffact[N];
  ffact[0] = fact[0] = inv_fact[0] = fact[1] = inv_fact[1] = 1;
  _for(i, 2, N * 2 - 1) fact[i] = fact[i - 1] * i % MOD;
  _for(i, 1, N - 1) ffact[i] = ffact[i - 1] * fact[i] % MOD;
  i64 _ = qpow(ffact[N - 1]);
  _rfor(i, N - 1, 2) {
    inv_fact[i] = _ * ffact[i - 1] % MOD;
    _ = _ * fact[i] % MOD;
  }
  return 0.0;
}();
auto m_choose_n = [](int m, int n, i64 mod = MOD) -> i64 {
  return m < n ? 0 : fact[m] * inv_fact[n] % mod * inv_fact[m - n] % mod;
};
auto solve() -> void {
  int n;
  cin >> n;
  vector<int> v;
  v.reserve(n);
  v.push_back(1);
  char ch;
  _for(i, 1, n) {
    cin >> ch;
    if (ch & 1) v.push_back(i);
  }
  v.push_back(n);
  i64 ans = 1;
  for (auto l = v.begin() + 1, r = v.end() - 2;; ++l, --r) {
    int len_l = *l - *(l - 1), len_r = *(r + 1) - *r;
    if (r + 1 == l) {
      (ans *= qpow(2, *l - *r)) %= MOD;
      break;
    }
    if (r + 2 == l) break;
    i64 _ = 0;
    _for(i, 0, min(len_l, len_r))
      _ += m_choose_n(len_l, i) * m_choose_n(len_r, i) % MOD;
    (ans *= _ % MOD) %= MOD;
  }
  cout << ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

不降子数组游戏 (CodeForces Gym 102984D)

题目链接

3 s, 1024 MB

题目描述

Yuto 和 Platina 准备玩一个不降子数组游戏

具体的，给定一个长度为 \(N\) 的数组 \(A\), 和区间限制 \(L\) 和 \(R\)

Yuto 首先在 \([L, R]\) 中选择一个数字，并展示给 Platina 看

随后 Platina 也会选择一个在 \([L, R]\) 中的数字

我们不妨设 Yuto 选择了数字 \(a\), Platina 选择了数字 \(b\)

这局游戏的得分是 \(A[min(a,b):max(a,b)]\) 的不降子数组的个数. (\(A[l:r]\) 表示由数组 \(A\) 下标从 \(l\) 到 \(r\) 这一连续段构成的新数组)

注：数组 \(B\) 的子数组是从 \(B\) 的头尾连续删除若干 (可以为空) 个元素后得到的新数组

Yuto 想要得分尽可能的小，Platina 想要得分尽可能的大

他们将会在一个数组上游戏 \(Q\) 次，对于每次游戏，请输出最后游戏的得分

输入格式

第一行输入一个正整数 \(N\), 表示数组 \(A\) 的长度

接下来一行 \(N\) 个正整数，分别表示 \(A_1\), \(A_2\), ... , \(A_N\)

第三行输入一个正整数 \(Q\), 表示游戏进行的次数

接下来 \(Q\) 行，每一行输入两个正整数，分别表示 \(L\) 和 \(R\)

对于所有数据，满足 \(1 \leq N, Q \leq 5 \times 10^5\), \(1 \leq A_i \leq 10^9\) 且 \(1 \leq L \leq R \leq N\)

输出格式

对于每次游戏，输出一个正整数，表示游戏最后的得分

样例输入

1
2
3
4
5
6
7
8
8
7 10 3 1 9 5 5 2
5
1 5
2 2
5 8
1 8
3 5

样例输出

1
2
3
4
5
4
1
4
7
3

解题思路

三分 + 分块

首先将数组分成递增的若干段，如对于样例分为 [7 10] [3] [1 9] [5 5] [2] 五段，然后每一段都可以很容易地求出得分，进而用一个前缀和即可方便地求出某一段区间的得分

对于单次查询，显然无论先手选什么，后手必选端点，而且不难发现得分对先手选的点是单峰函数，所以直接三分即可

复杂度

\(O(N+Q\log N)\)

代码参考

Show code

CodeForces_Gym_102984Dview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 5e5 + OFFSET;
int a[N];
int block_id[N], block_end[N];
i64 sum_f[N];
auto _ = [](i64 len) -> i64 { return len * (len + 1) / 2; };
i64 query(int l, int r) {
  if (l > r) swap(l, r);
  if (block_id[r] == block_id[l]) return _(r - l + 1);
  return _(r - block_end[block_id[r] - 1]) + _(block_end[block_id[l]] - l + 1) +
         sum_f[block_id[r] - 1] - sum_f[block_id[l]];
}
i64 f(int l, int r, int x) { return max(query(l, x), query(x, r)); }
i64 tri(int l, int r) {
  int mid1, mid2;
  i64 f1, f2;
  i64 ans = INT64_MAX;
  int _l = l, _r = r;
  while (_r - _l > 10) {
    f1 = f(l, r, mid1 = _l + (_r - _l) / 3);
    f2 = f(l, r, mid2 = _r - (_r - _l) / 3);
    ans = min({ans, f1, f2});
    if (f1 > f2) _l = mid1;
    else _r = mid2;
  }
  _for(i, _l, _r) chkmin(ans, f(l, r, i));
  return ans;
}
auto solve() -> void {
  int n, m;
  cin >> n >> m;
  _for(i, 1, n) cin >> a[i];
  int cnt = 1;
  _for(i, 1, n) {
    if (a[i] < a[i - 1]) ++cnt;
    block_end[block_id[i] = cnt] = i;
  }
  _for(i, 1, cnt) sum_f[i] = sum_f[i - 1] + _(block_end[i] - block_end[i - 1]);
  _for(i, 1, m, l, r) {
    cin >> l >> r;
    cout << tri(l, r) << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

Nearest Opposite Parity (CF1272E)

题目链接

1 s, 128 MB

题目描述

给定一个长度为 \(n\) 的下标从 \(1\) 开始的数组 \(a\), 在位置 \(i\) 可以移动到位置 \(i - a_i(1 \leq i - a_i)\) 或 \(i + a_i(i + a_i \leq n)\)

现在希望你对于每一个位置 \(i\) \((1 \leq i \leq n)\) 求出从这里出发，抵达任意一个位置 \(j\) 使得该位置 \(j\) 满足 \(a_i \bmod 2 \neq a_j \bmod 2\) 的最小步数，如果不存在这样的位置 \(j\) 则输出 -1

输入格式

第一行输入一个整数 \(n\) \((1 \leq n \leq 2 \times 10^5)\) 为数组长度

第二行输入 \(n\) 个整数 \(a_i\) \((1 \leq a_i \leq n)\) 为给定的数组

输出格式

输出一行，包含 \(n\) 个整数，第 \(j\) 个整数为从位置 \(j\) 出发的题目所求

输入样例

1
2
10
4 5 7 6 7 5 4 4 6 4

输出样例

1
1 1 1 2 -1 1 1 3 1 1

解题思路

BFS

建图之后爆搜即可

复杂度

代码参考

Show code

CodeForces_1272Eview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/extc++.h>
using namespace std;
template <typename Tp>
using vc = std::vector<Tp>;
template <typename Tp>
using vvc = std::vector<std::vector<Tp>>;
#define for_(i, l, r, vars...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vars; i <= i##end; ++i)
#define foreach_ref_(i, container) for (auto &i : (container))
#define foreach_cref_(i, container) for (const auto &i : (container))
#define all_(a) (a).begin(), (a).end()
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
#define read_container_(type, name, size) \
  type name(size);                        \
  foreach_ref_(i, name) std::cin >> i;
template <class Tp>
auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
};
template <class Tp>
auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
};
template <typename Tp>
auto discretization(Tp &var) -> Tp {
  Tp d__(var);
  std::sort(d__.begin(), d__.end());
  d__.erase(std::unique(d__.begin(), d__.end()), d__.end());
  for (auto &i : var)
    i = std::distance(d__.begin(), std::lower_bound(d__.begin(), d__.end(), i));
  return d__;
};
template <typename Tp>
auto ispow2(Tp i) -> bool {
  return i && (i & -i) == i;
}
template <class Tp, class Up>
std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) {
  if (&os == &std::cerr) return os << "(" << p.first << ", " << p.second << ")";
  return os << p.first << " " << p.second;
}
template <class Ch, class Tr, class Container>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os,
                                       const Container &x) {
  if (&os == &std::cerr) os << "[";
  if (&os == &std::cerr)
    for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ", ";
  else
    for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' ';
  os << x.back();
  if (&os == &std::cerr) os << "]";
  return os;
}
vvc<int> g;
auto solve([[maybe_unused]] int t_) -> void {
  read_var_(int, n);
  read_container_(vc<int>, v, n);
  g.resize(n);
  for_(i, 0, n - 1) {
    if (i - v[i] >= 0) g[i - v[i]].push_back(i);
    if (i + v[i] < n) g[i + v[i]].push_back(i);
  }
  vc<int> odd(n), even(n);
  transform(
    all_(v), odd.begin(), [](const int &x) -> int { return x % 2 - 1; });
  transform(
    all_(v), even.begin(), [](const int &x) -> int { return -(x % 2); });
  queue<int> q;
#define __(type)                                  \
  for_(i, 0, n - 1)                               \
    if (~type[i]) q.push(i);                      \
  while (!q.empty()) {                            \
    auto &&now = q.front();                       \
    foreach_cref_(v, g[now])                      \
      if (!~type[v] || type[v] > type[now] + 1) { \
        type[v] = type[now] + 1;                  \
        q.push(v);                                \
      }                                           \
    q.pop();                                      \
  }
  __(odd)
  __(even)
#undef __
  for_(i, 0, n - 1) cout << ((v[i] & 1) ? even : odd)[i] << " \n"[i == n - 1];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}

双端队列 (CF1579E2)

题目链接

1 s, 1024 MB

题目描述

给定一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\) 和一个空的双端队列

你需要按顺序将序列中的每一个数放进双端队列中，你可以选择将数插入到双端队列的队首或队尾

你需要最小化最终得到的序列的逆序对数量

输入格式

第一行一个整数 \(n\), 表示序列的长度. \((1 \leq n \leq 2 \times 10^5)\)

第二行 \(n\) 个数字 \(a_1,a_2,\dots,a_n\), 表示给定的序列. \((-10^9 \leq a_i \leq 10^9)\)

输出格式

输出一行一个整数，表示最少的逆序对数

样例输入

1
2
4
3 7 5 5

样例输出

1
2

解题思路

逆序对

如果我们将插入过程倒过来就会发现插入是没有后效性的，所以直接贪心插入即可

复杂度

\(O(n\log n)\)

代码参考

Show code

CodeForces_1579E2view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _foreach_cref(i, container) for (const auto &i : container)
#define _foreach_iter(it, container) \
  for (auto it = (container).begin(); it != (container).end(); ++it)
#define _all(a) (a).begin(), (a).end()
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
template <typename Tp>
class BIT {
protected:
  vector<Tp> tree;
  constexpr size_t lowbit(ptrdiff_t x) const { return x & (-x); }

public:
  explicit BIT(size_t n): tree(n) {}
  void modify(size_t pos, Tp val = 1) {
    for (size_t i = pos; i < tree.size(); i += lowbit(i)) tree[i] += val;
  }
  Tp query(size_t pos) const {
    Tp ret = 0;
    for (size_t i = pos; i; i = (ptrdiff_t)i - lowbit(i)) ret += tree[i];
    return ret;
  }
};
auto solve() -> void {
  int n;
  cin >> n;
  BIT<int> tr(n + 1);
  vector<int> a, idx;
  a.reserve(n);
  idx.reserve(n);
  _for(i, 1, n, x) {
    cin >> x;
    a.push_back(x);
    idx.push_back(x);
  }
  sort(_all(idx));
  idx.erase(unique(_all(idx)), idx.end());
  _foreach_iter(it, a) *it = lower_bound(_all(idx), *it) - idx.begin() + 1;
  i64 ans = 0;
  _foreach_cref(i, a) {
    ans += min(tr.query(i - 1), tr.query(n) - tr.query(i));
    tr.modify(i);
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

抽卡 (AtCoder ABC225F)

题目链接

1 s, 256 MB

题目描述

有 \(n\) 张卡片，每张卡片上有一个字符串 \(s_i\), 现在要求你从中选出 k 张卡片，使得在所有选取方案中，这 \(k\) 张卡片连起来的字典序是最小的 (具体详见样例)

输入描述

第一行两个整数 \(n, k(1\leq k\leq n\leq 50)\)

接下来 n 行每行一个字符串 \(s_i(1\leq |s_i|\leq 50)\)

输出描述

一个字符串，表示从中选 k 张卡片的所有方案中字典序最小的字符串

样例输入 1

1
2
3
4
5
4 3
ode
zaaa
r
atc

样例输出 1

1
atcoder

样例输入 2

1
2
3
4
5
6
5 2
z
z
zzz
z
zzzzzz

样例输出 2

1
zz

原题链接

戳我

解题思路

逆序对

如果我们将插入过程倒过来就会发现插入是没有后效性的，所以直接贪心插入即可

复杂度

\(O(n\log n)\)

代码参考

Show code

CodeForces_Gym_102984Dview raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 5e5 + OFFSET;
int a[N];
int block_id[N], block_end[N];
i64 sum_f[N];
auto _ = [](i64 len) -> i64 { return len * (len + 1) / 2; };
i64 query(int l, int r) {
  if (l > r) swap(l, r);
  if (block_id[r] == block_id[l]) return _(r - l + 1);
  return _(r - block_end[block_id[r] - 1]) + _(block_end[block_id[l]] - l + 1) +
         sum_f[block_id[r] - 1] - sum_f[block_id[l]];
}
i64 f(int l, int r, int x) { return max(query(l, x), query(x, r)); }
i64 tri(int l, int r) {
  int mid1, mid2;
  i64 f1, f2;
  i64 ans = INT64_MAX;
  int _l = l, _r = r;
  while (_r - _l > 10) {
    f1 = f(l, r, mid1 = _l + (_r - _l) / 3);
    f2 = f(l, r, mid2 = _r - (_r - _l) / 3);
    ans = min({ans, f1, f2});
    if (f1 > f2) _l = mid1;
    else _r = mid2;
  }
  _for(i, _l, _r) chkmin(ans, f(l, r, i));
  return ans;
}
auto solve() -> void {
  int n, m;
  cin >> n >> m;
  _for(i, 1, n) cin >> a[i];
  int cnt = 1;
  _for(i, 1, n) {
    if (a[i] < a[i - 1]) ++cnt;
    block_end[block_id[i] = cnt] = i;
  }
  _for(i, 1, cnt) sum_f[i] = sum_f[i - 1] + _(block_end[i] - block_end[i - 1]);
  _for(i, 1, m, l, r) {
    cin >> l >> r;
    cout << tri(l, r) << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}