2022杭电多校（九）

2022杭电多校（九）

文章目录

• 2022杭电多校（九）
• • 一、比赛小结
  • 二、题目分析及解法（基础题）
  • • 1001、Arithmetic Subsequence
    • 1003、Fast Bubble Sort
    • 1007、Matryoshka Doll
    • 1008、Shortest Path in GCD Graph
    • 1010、Sum Plus Product
  • 三、题目分析及解法（进阶题）

一、比赛小结

比赛链接：

二、题目分析及解法（基础题） 1001、Arithmetic Subsequence

题目链接：Problem - 7233 (hdu.edu.cn)

题意：

题目描述. 给一个长度为𝑁的整数序列𝐴 = (𝐴𝑖)，问能否将该序列重排得到序列𝐵 = (𝐵𝑖)，满足

• 1 ≤ 𝑖 < 𝑗 < 𝑘 ≤ 𝑁;

• (𝐵𝑖 , 𝐵𝑗 , 𝐵𝑘 )不构成等差序列。

题解：

首先如果某个数出现次数大于等于3则不存在解。然后如果所有数字均为偶数，我们可将所有数除以二;如果所有数字均为奇数，我们可将所有数减去一;否则,我们将所有奇数放在左边，所有偶数放在右边，对奇数/偶数分治解决。单组数据时间复杂度𝑂(𝑛 log max𝐴𝑖)。

代码：

// #pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #pragma GCC optimize("trapv")
#include 
// #include 
#define int long long
#define double long double
// #define i128 long long
// #define double long double
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

typedef long long ll;
typedef unsigned long long ull;
// typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const int mod = 998244353;
const double EPS = 1e-9;
const double pi = acos(-1);
const int INF = 1e18;
const int N = 5007;
mt19937 rng(1235);
int n;
vi ans;
void solve(vi &x) {
  vector<pair<int, int>> y;
  int n = sz(x);
  for (int i = 0; i < n; ++i) {
    y.push_back({0, x[i]});
    for (int j = 0; j < 30; ++j) {
      if (x[i] >> j & 1) y[i].first |= (1ll << (29 - j));
    }
  }
  sort(range(y));
  for (int i = 0; i < n; ++i) ans.push_back(y[i].second);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cout.precision(15);
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    vi a(n, 0);
    rep(i, n) cin >> a[i];
    map<int, int> cnt;
    ans.clear();
    rep(i, n) {
      cnt[a[i]]++;
      if (cnt[a[i]] > 2) {
        cout << "NO\n";
        goto cont;
      }
    }
    cout << "YES\n";
    solve(a);
    for (auto c : ans) cout << c << " ";
    cout << "\n";
  cont:;
  }
  return 0;
}
/*

*/

1003、Fast Bubble Sort

题目链接：Problem - 7235 (hdu.edu.cn)

题意：

给定任何一个长度为𝑁的数组𝐴 = (𝑎1, 𝑎2, . . . , 𝑎𝑛),令𝐵(𝐴)表示对𝐴进行一次bubble sort循环之后得到的数组。令𝑛𝑢𝑚(𝐴)表示从𝐴到𝐵(𝐴)最少需要移动元素(数组区间循环移位)的次数。给定一个1 − 𝑛的排列𝑃以及𝑞组1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛，求𝑛𝑢𝑚(𝑃 [𝑙, 𝑟])

题解：

假设𝑃 = 𝑛1𝜆1𝑛2𝜆2 · · · 𝑛𝑘𝜆𝑘 ,则𝐵(𝑃) = 𝜆1𝑛1𝜆2𝑛2 · · · 𝜆𝑘𝑛𝑘 ,其中𝑛1, · · · , 𝑛𝑘为从左到右的局部最大值且有𝑛1 < 𝑛2 < · · · < 𝑛𝑘,则不难证明答案为非空𝜆𝑖的个数。

将询问离线,每次从𝑛到1倒序扫描左端点𝑙并回答所有左端点为𝑙的询问。对于每个固定的左端点𝑙，[𝑙, 𝑛]中从左到右的局部最大值可以通过单调栈维护，局部最大值插入/删除对于答案的影响可以用树状数组/线段树快速更新/求解。单组数据时间复杂度为𝑂( (𝑛 + 𝑞) log 𝑛)

代码：

// #pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #pragma GCC optimize("trapv")
#include 
// #include 
#define int long long
#define double long double
// #define i128 long long
// #define double long double
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

typedef long long ll;
typedef unsigned long long ull;
// typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
  int x = 0;
  while ((1U << x) < (unsigned int)(n)) x++;
  return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
// constexpr int bsf_constexpr(unsigned int n) {
//     int x = 0;
//     while (!(n & (1 << x))) x++;
//     return x;
// }

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
  unsigned long index;
  _BitScanForward(&index, n);
  return index;
#else
  return __builtin_ctz(n);
#endif
}

}  // namespace internal

template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
 public:
  segtree() : segtree(0) {}
  segtree(int n) : segtree(std::vector<S>(n, e())) {}
  segtree(const std::vector<S>& v) : _n((int)(v.size())) {
    log = internal::ceil_pow2(_n);
    size = 1 << log;
    d = std::vector<S>(2 * size, e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i >= 1; i--) {
      update(i);
    }
  }

  void set(int p, S x) {
    assert(0 <= p && p < _n);
    p += size;
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  S get(int p) {
    assert(0 <= p && p < _n);
    return d[p + size];
  }

  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    S sml = e(), smr = e();
    l += size;
    r += size;

    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }
    return op(sml, smr);
  }

  S all_prod() { return d[1]; }

  template <bool (*f)(S)>
  int max_right(int l) {
    return max_right(l, [](S x) { return f(x); });
  }
  template <class F>
  int max_right(int l, F f) {
    assert(0 <= l && l <= _n);
    assert(f(e()));
    if (l == _n) return _n;
    l += size;
    S sm = e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(op(sm, d[l]))) {
        while (l < size) {
          l = (2 * l);
          if (f(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*f)(S)>
  int min_left(int r) {
    return min_left(r, [](S x) { return f(x); });
  }
  template <class F>
  int min_left(int r, F f) {
    assert(0 <= r && r <= _n);
    assert(f(e()));
    if (r == 0) return 0;
    r += size;
    S sm = e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(op(d[r], sm))) {
        while (r < size) {
          r = (2 * r + 1);
          if (f(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

 private:
  int _n, size, log;
  std::vector<S> d;

  void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

using S = int;
S op(S l, S r) { return l + r; }
S e() { return 0; }

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const int mod = 998244353;
const int base[] = {12321, 32123};
const double EPS = 1e-9;
const double pi = acos(-1);
const int INF = 1e18;
const int N = 100017;
mt19937 rng(1235);

int n, q;
int p[N];
int ans[N], C[N], now[N];
vector<pii> info[N];
int st[N];

int lowbit(int u) { return u & (-u); }
void update(int u, int w) {
  for (int i = u; i <= n + 7; i += lowbit(i)) C[i] += w;
}
int query(int u) {
  int ans = 0;
  for (int i = u; i; i -= lowbit(i)) ans += C[i];
  return ans;
}
signed main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  //_=1;
  while (_--) {
    cin >> n >> q;
    rep(i, n) cin >> p[i];
    for (int i = 1; i <= n + 5; ++i) C[i] = 0, now[i] = 0;
    rep(i, N) info[i].clear();
    p[n] = n + 1;
    rep(i, q) {
      int u, v;
      cin >> u >> v;
      u--, v--;
      info[u].pb({i, v});
    }
    int cnt = 0;
    st[cnt++] = n;
    auto upd = [&](int u) {
      update(u + 1, (now[u + 1] ? -1 : 1)), now[u + 1] ^= 1;
      update(u + 2, (now[u + 2] ? -1 : 1)), now[u + 2] ^= 1;
    };
    for (int i = n - 1; i > -1; --i) {
      while (cnt && p[i] > p[st[cnt - 1]]) {
        cnt--;
        upd(st[cnt]);
      }
      st[cnt++] = i, upd(i);
      for (auto c : info[i]) {
        int id = c.F, r = c.S;
        if (i == r)
          ans[id] = 0;
        else
          ans[id] = (query(r + 1) - query(i)) / 2;
      }
    }
    rep(i, q) cout << ans[i] << "\n";
  }
  return 0;
}

1007、Matryoshka Doll

题目链接：Problem - 7239 (hdu.edu.cn)

题意：

题目描述. 有𝑛个套娃，大小为𝑎1 ≤ 𝑎2 ≤ … ≤ 𝑎𝑛，现在要将这些套娃分成𝑘组，每组套娃按照大小排序后相邻两个套娃之间的大小差距要求≥ 𝑟，求方案数。

题解：

做法. 𝑑𝑝(𝑥, 𝑦)表示将前𝑥个套娃分成𝑦组的方案数，转移为𝑑𝑝(𝑥, 𝑦) = 𝑑𝑝(𝑥 − 1, 𝑦 − 1) + 𝑑𝑝(𝑥 − 1, 𝑦) · max{0, 𝑦 − 𝑓 (𝑥)}. 其中𝑓 (𝑥)表示满足1 ≤ 𝑧 < 𝑥且𝑎𝑥 − 𝑟 < 𝑎𝑧 ≤ 𝑎𝑥的𝑧的个数。单组数据时间复杂度:𝑂(𝑛2).

代码：

#include 
using namespace std;
typedef long long ll;
const int M = 998244353;
int n, k, r, a[5005], dp[5005][5005];
void solve() {
  memset(dp, 0, sizeof(dp));
  cin >> n >> k >> r;
  for (int i = 1; i <= n; i++) cin >> a[i];
  int p = 0;
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    while (p + 1 < i && a[p + 1] + r <= a[i]) ++p;
    int s = i - p - 1;
    for (int j = s + 1; j <= i; j++)
      dp[i][j] = (1ll * (j - s) * dp[i - 1][j] + dp[i - 1][j - 1]) % M;
  }
  cout << dp[n][k] << endl;
}
int main() {
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  int T;
  cin >> T;
  while (T--) solve();
}

1008、Shortest Path in GCD Graph

题目链接：Problem - 7240 (hdu.edu.cn)

题意：

给定𝑛个点的完全图，两个点之间距离为它们的gcd，𝑞次询问两个点之间的最短

路以及方案数。

题解：

首先最短路长度不超过2，因为对任意(𝑥, 𝑦)，沿路径𝑥 → 1 → 𝑦即可得到一条长

度为2的路径。最短路长度为1当且仅当𝑔𝑐𝑑 (𝑥, 𝑦) = 1，否则等价于询问[1, 𝑛]中满足𝑔𝑐𝑑 (𝑥, 𝑧) =1且𝑔𝑐𝑑 (𝑦, 𝑧) = 1的𝑧的数量，分解𝑥, 𝑦后用容斥可以解决。注意𝑔𝑐𝑑 (𝑥, 𝑦) = 2时，直接𝑥 → 𝑦也是一条长度为2的路径。单组数据时间复杂度: 𝑂(𝑛 + 𝑄 · 2𝑝 )，其中𝑝 ≤ 12为𝑥, 𝑦的不同质因子个数。

代码：

#include 
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 5;
typedef vector<int> vi;
int prime[maxn / 10], f[maxn], n, Q;
bool p[maxn];
void sieve(int n) {
  int cnt = 0;
  for (int i = 2; i <= n; i++) {
    if (!p[i]) prime[++cnt] = i, f[i] = i;
    for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
      p[prime[j] * i] = 1;
      f[prime[j] * i] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
}
int m, ret;
set<int> S;
vi a;
void pv(int x) {
  while (x > 1) {
    int y = f[x];
    if (S.find(y) == S.end()) S.insert(y);
    while (x % y == 0) x /= y;
  }
}
void dfs(int x, int s, int o) {
  if (x == m) {
    ret += o * (n / s);
    return;
  }
  dfs(x + 1, s, o);
  if (s <= n / a[x]) dfs(x + 1, s * a[x], -o);
}
int calc(int x, int y) {
  S.clear();
  pv(x);
  pv(y);
  a.clear();
  for (auto x : S) a.pb(x);
  m = a.size();
  ret = 0;
  dfs(0, 1, 1);
  return ret;
}
int main() {
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  ios::sync_with_stdio(false);
  cin >> n >> Q;
  sieve(n);
  while (Q--) {
    int x, y;
    cin >> x >> y;
    assert(x != y);
    if (__gcd(x, y) == 1) {
      cout << 1 << ' ' << 1 << endl;
      continue;
    }
    int ans = calc(x, y);
    if (__gcd(x, y) == 2) ans++;
    cout << 2 << ' ' << ans << endl;
  }
  return 0;
}

1010、Sum Plus Product

题目链接：Problem - 7242 (hdu.edu.cn)

题意：

盒子里有 n 个球，每次随机取出两个球 a , b ，放回一个球 ( a + b ) + ( ab ) ，问最后一个球的期望值是多少

题解：

取球顺序与结果无关

代码：

#include 
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 600;
int n;
int a[maxn];
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 1ll;
    for (int i = 1; i <= n; i++) {
      ans = ans * (a[i] + 1ll) % mod;
    }
    ans = (ans - 1ll + mod) % mod;
    cout << ans << endl;
  }
  return 0;
}

三、题目分析及解法（进阶题）