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

发表于 2022-05-28 更新于 2023-12-05 分类于算法竞赛，题解本文字数： 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\leq n\leq 300000, 1 \leq a_i \leq 300000\)

解题思路

二分图染色

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

代码参考

Show code

CodeForces_1268Bview raw

/*
 * @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

/*
 * @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\)

输出格式

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

样例输入

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

样例输出

解题思路

三分 + 分块

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

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

复杂度

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

代码参考

Show code

CodeForces_Gym_102984Dview raw

/*
 * @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

样例输出

样例解释

合法的划分方案为: \([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

/*
 * @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\)

输出格式

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

样例输入

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

样例输出

解题思路

三分 + 分块

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

复杂度

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

代码参考

Show code

CodeForces_Gym_102984Dview raw

/*
 * @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

/*
 * @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

样例输出

解题思路

逆序对

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

复杂度

\(O(n\log n)\)

代码参考

Show code

CodeForces_1579E2view raw

/*
 * @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

4 3
ode
zaaa
r
atc

样例输出 1

atcoder

样例输入 2

5 2
z
z
zzz
z
zzzzzz

样例输出 2

zz

原题链接

戳我

解题思路

逆序对

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

复杂度

\(O(n\log n)\)

代码参考

Show code

CodeForces_Gym_102984Dview raw

/*
 * @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;
}