1. 云图网首页
  2. 技术专区
  3. 编程笔记

Codeforces Global Round 21

• 编程笔记


A. NIT orz!

观察可得：/(z/)二进制表示中包含的/(1/)的个数非增。

由此最大的数一定可以在第一步得到，值为/(/max_i a_i /operatorname{or} z/)。

B. NIT Destroys the Universe

首先，一段连续的非0子数组可以一次操作变成全0。

然后，通过连续两次对整个数组操作可以将整个数组变成全0。

两者取最小。

C. Fishingprince Plays With Array

题意

给两个数组/(a/)和/(b/)，还有一个数/(m/)。

支持两种操作：

  1. 如果/(a_i /equiv 0 /mod m/)，则可以将/(a_i/)拆成/(m/)个/(/frac{a_i}{m}/)。
  2. 如过从/(a_i/)开始往后数/(m/)个数，这/(m/)个数值相等，则可以将这/(m/)个数合成1个/(m /times a_i/)。

问通过有限次操作是否能把/(a/)变成/(b/)。

其中/(1 /le |a|, |b| /le 5 /times {10}^4，1 /le a_i, b_i /le {10}^9, 2 /le m /le {10}^9/)。

思路

对于数组/(a/)，先对于所有元素不断拆分直到无法继续拆分，然后为了方便存储需要把连续且值相同的元素合并成一个二元组，结果记为/(f(a)/)。

如果/(f(a) = f(b)/)，则有解，反之无解。

证明的话，就是对于/(a/)做任何一种操作之后得到/(a^/prime/)会有/(f(a) = f(a^/prime)/)。

AC代码 
// Problem: C. Fishingprince Plays With Array
// Contest: Codeforces - Codeforces Global Round 21
// URL: https://codeforces.com/contest/1696/problem/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve_case(t);
  }
  return 0;
}

void solve_case(int Case) {
  auto f = [](const std::vector<i64>& a, int m) {
    std::vector<std::pair<i64, i64>> d;
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
      i64 c = 1;
      i64 v = a[i];
      while (v % m == 0) {
        c *= m;
        v /= m;
      }
      d.push_back({c, v});
      while (d.size() >= 2 && d[d.size() - 2].second == d[d.size() - 1].second) {
        d[d.size() - 2].first += d[d.size() - 1].first;
        d.pop_back();
      }
    }
    return d;
  };

  int n, m;
  std::cin >> n >> m;

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

  int k;
  std::cin >> k;
  std::vector<i64> b(k);
  for (int i = 0; i < k; ++i)
    std::cin >> b[i];

  std::cout << (f(a, m) == f(b, m) ? "Yes" : "No") << "/n";
}

D. Permutation Graph

题意

给定一个长度为/(n/)的排列/(a/)，根据以下方法建图：如果/(i, j/)满足/(a_i/)是区间最小值且/(a_j/)是区间最大值，或者满足/(a_i/)是区间最大值且/(a_j/)是区间最小值，就在/(i, j/)之间连一条边，这里的区间最值对应区间为/([i, j]/)。

问点/(1/)到点/(n/)的最短路。

其中/(1 /le n /le 2.5 /times {10}^5/)。

思路1

转化一下就是从下标/(1/)开始，最少跳几步能跳到下标/(n/)。

然后观察易得：假设当前位于/(i/)，/(a_i < a_{i+1}/)，下一步跳到/(nxt/)，则区间/([i, nxt]/)里不能有值比/(a_i/)小。易得满足这个条件的右边界/(r/)具有单调性。

更进一步，如果区间/([i, r]/)的最大值位于/(p/)，则/(nxt/)不能大于/(p/)。

然后假设某一步能够从/(i/)跳到/(r/)的，但是只跳到了/(m < r/)，从/(m/)起跳最远还是只能跳到/(r/)。所以不妨贪心能跳多远跳多远。

/(a_i > a_{i+1}/)的情况类似。

数据结构和二分搞一搞，时间复杂度/(O(n /log^2 n)/)。

思路2

TBA。

思路1 AC代码 
// Problem: D. Permutation Graph
// Contest: Codeforces - Codeforces Global Round 21
// URL: https://codeforces.com/contest/1696/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve_case(t);
  }
  return 0;
}

template <typename ValueType>
class RMQ {
 private:
  using Operator = std::function<ValueType(ValueType, ValueType)>;

  int n_;
  std::vector<std::vector<ValueType>> a_;
  std::vector<int> lg_;
  Operator op_;

 public:
  RMQ(const std::vector<ValueType>& a, Operator op) : op_(op) {
    n_ = a.size();

    lg_.resize(n_ + 1);
    lg_[1] = 0;
    for (int i = 2; i <= n_; ++i)
      lg_[i] = lg_[i >> 1] + 1;

    a_.resize(n_);
    for (int i = 0; i < n_; ++i) {
      a_[i].resize(lg_[n_] + 1);
      a_[i][0] = a[i];
    }
    for (int j = 1; j <= lg_[n_]; ++j) {
      for (int i = 0; i + (1 << (j - 1)) < n_; ++i) {
        a_[i][j] = op_(a_[i][j - 1], a_[i + (1 << (j - 1))][j - 1]);
      }
    }
  }

  ValueType get(int l, int r) {
    int k = lg_[r - l + 1];
    return op_(a_[l][k], a_[r - (1 << k) + 1][k]);
  }
};

void solve_case(int Case) {
  logd(Case);
  int n;
  std::cin >> n;

  std::vector<std::pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i].first;
    a[i].second = i;
  }

  RMQ<std::pair<int, int>> mx(
      a, [](const std::pair<int, int>& x, const std::pair<int, int>& y) -> std::pair<int, int> {
        return std::max(x, y);
      });
  RMQ<std::pair<int, int>> mn(
      a, [](const std::pair<int, int>& x, const std::pair<int, int>& y) -> std::pair<int, int> {
        return std::min(x, y);
      });
  logd(a);

  int ans = 0;
  for (int i = 0; i < n - 1;) {
    ++ans;

    logd(i);
    int l = i + 1, r = n - 1, mid, nxt = i + 1;
    while (l <= r) {
      mid = (l + r) >> 1;

      if (a[i].first < a[i + 1].first) {
        logd(mid, mn.get(i, mid).first);
        if (mn.get(i, mid).first >= a[i].first)
          l = mid + 1, nxt = mid;
        else
          r = mid - 1;
      } else {
        if (mx.get(i, mid).first <= a[i].first)
          l = mid + 1, nxt = mid;
        else
          r = mid - 1;
      }
    }
    logd(nxt);
    if (a[i].first < a[i + 1].first) {
      i = mx.get(i + 1, nxt).second;
    } else {
      i = mn.get(i + 1, nxt).second;
    }
  }

  std::cout << ans << "/n";
}

E. Placing Jinas

题意

给定一个长度为/(n/)的非升序列/(a/)。

有一个矩阵，满足/(0 /le y < a_x/)的方格/((x, y)/)为白色，其余方格均为黑色。

初始时有个娃娃在/((0, 0)/)处，你可以花费一个操作把/((x, y)/)处的娃娃收走，然后在/((x + 1, y)/)和/((x, y + 1)/)处各放一个娃娃。

问使得所有白格上都没有娃娃的最小操作次数，答案对/({10}^9 + 7/)取模。

其中/(1 /le n /le 2 /times{10}^5, 0 /le a_i /le 2 /times {10}^5/)，

思路

假设需要在/((x, y)/)处操作/(f(x, y)/)次，则/(f(x, y) = f(x – 1, y) + f(x, y – 1)/)，这个式子可太经典了，/(f(x, y) = /binom{x + y}{y}/)。

然后就有

/[ans = /sum_{i = 0}^{n} /sum_{j = 0}^{a_i – 1} /binom{i + j}{i}.
/]

将/(/sum_{i = 0}^{k} /binom{n + i}{n} = /binom{n + k + 1}{n + 1}/)带入可得

/[ans = /sum_{i = 0}^{n} /binom{i + a_i}{i + 1}
/]

AC代码 
// Problem: E. Placing Jinas
// Contest: Codeforces - Codeforces Global Round 21
// URL: https://codeforces.com/contest/1696/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve_case(t);
  }
  return 0;
}

template <typename ValueType, ValueType mod_, typename SupperType = int64_t>
class Modular {
 private:
  ValueType value_;

  ValueType normalize(ValueType value) const {
    if (value >= 0 && value < mod_)
      return value;
    value %= mod_;
    if (value < 0)
      value += mod_;
    return value;
  }

  ValueType power(ValueType value, size_t exponent) const {
    ValueType result = 1;
    ValueType base = value;
    while (exponent) {
      if (exponent & 1)
        result = SupperType(result) * base % mod_;
      base = SupperType(base) * base % mod_;
      exponent >>= 1;
    }
    return result;
  }

 public:
  Modular() : value_(0) {}

  Modular(const ValueType& value) : value_(normalize(value)) {}

  ValueType value() const { return value_; }

  Modular inv() const { return Modular(power(value_, mod_ - 2)); }

  Modular power(size_t exponent) const { return Modular(power(value_, exponent)); }

  friend Modular operator+(const Modular& lhs, const Modular& rhs) {
    ValueType result = lhs.value() + rhs.value() >= mod_ ? lhs.value() + rhs.value() - mod_
                                                         : lhs.value() + rhs.value();
    return Modular(result);
  }

  friend Modular operator-(const Modular& lhs, const Modular& rhs) {
    ValueType result = lhs.value() - rhs.value() < 0 ? lhs.value() - rhs.value() + mod_
                                                     : lhs.value() - rhs.value();
    return Modular(result);
  }

  friend Modular operator*(const Modular& lhs, const Modular& rhs) {
    ValueType result = SupperType(1) * lhs.value() * rhs.value() % mod_;
    return Modular(result);
  }

  friend Modular operator/(const Modular& lhs, const Modular& rhs) {
    ValueType result = SupperType(1) * lhs.value() * rhs.inv().value() % mod_;
    return Modular(result);
  }
};
template <typename StreamType, typename ValueType, ValueType mod, typename SupperType = int64_t>
StreamType& operator<<(StreamType& out, const Modular<ValueType, mod, SupperType>& modular) {
  return out << modular.value();
}
template <typename StreamType, typename ValueType, ValueType mod, typename SupperType = int64_t>
StreamType& operator>>(StreamType& in, Modular<ValueType, mod, SupperType>& modular) {
  ValueType value;
  in >> value;
  modular = Modular<ValueType, mod, SupperType>(value);
  return in;
}
using Mint = Modular<int, 1'000'000'007>;
// using Mint = Modular<int, 998'244'353>;

class Binom {
 private:
  std::vector<Mint> f, g;

 public:
  Binom(int n) {
    f.resize(n + 1);
    g.resize(n + 1);

    f[0] = Mint(1);
    for (int i = 1; i <= n; ++i)
      f[i] = f[i - 1] * Mint(i);
    g[n] = f[n].inv();
    for (int i = n - 1; i >= 0; --i)
      g[i] = g[i + 1] * Mint(i + 1);
  }
  Mint operator()(int n, int m) {
    if (n < 0 || m < 0 || m > n)
      return Mint(0);
    return f[n] * g[m] * g[n - m];
  }
};
Binom binom(4e5 + 5);

void solve_case(int Case) {
  int n;
  std::cin >> n;

  std::vector<int> a(n + 1);
  for (int i = 0; i <= n; ++i)
    std::cin >> a[i];

  Mint ans = Mint(0);
  for (int i = 0; i <= n; ++i) {
    ans = ans + binom(a[i] + i, i + 1);
  }

  std::cout << ans.value() << "/n";
}

原创文章，作者：dweifng，如若转载，请注明出处：https://blog.ytso.com/270390.html

赞 (0)
0
上一篇 2022年6月26日
下一篇 2022年6月26日

相关推荐

发表回复

登录后才能评论