2022 年西安电子科技大学校赛的部分题解

2022-05-25

题目 & 题面

被出题人打爆了.

现场赛

D 数位相邻

解题思路

首先考虑最后答案长度和给定数字长度一样的情况, 也就是答案的第一位不是进位得到 1 的情况.

考虑给定数字中第一个不满足相邻两数字之差不等于 $k$ 的位置 $p$, 即 $p$ 满足 $|A_{p - 1} - A_p| = k$, 那么位置 $p$ 在答案中一定是会被修改的, 即使不是 $p$ 也是 $p$ 之前的位置.

直觉上把位置 $p$ 对应数字加上 1 就好了, 但可能会导致进位或者不满足差的绝对值不等于 $k$ 的限制. 前者可看作修改 $p-1$ 位置上的数字. 对于后者, 枚举位置 $p$ 对于数字的改变量. 如果所有的可能值都不满足限制, 同样可以转为从位置 $p-1$ 下手解决. 确定修改位置 $p$ 后, $p$ 前按照原数字保留, $p$ 后构造满足限制的最小数字就好了.

至于原数字首位进位的情况, 答案一定是 1 开头的某一个数字, 构造一个尽量小的串就好了.

代码实现

~~一生之敌啊.~~ 不要想一堆似是而非的条件就开始写代码…

> 点击显示 / 隐藏

// D
// DeP
#include <cmath>
#include <cstdio>
#include <cstring>

constexpr int MAXN = 1e6 + 5;

int n, K;
char str[MAXN];

int A[MAXN];

int check(int p) {
  for (int k = 1; A[p] + k <= 9; ++k)
    if (abs(A[p] + k - A[p - 1]) != K)
      return k;
  return -1;
}

int main() {
  int Ti;
  scanf("%d", &Ti);
  while (Ti--) {
    scanf("%s%d", str + 1, &K);

    n = strlen(str + 1);
    A[0] = 0;
    for (int i = 1; i <= n; ++i) A[i] = str[i] - '0';

    int p = -1;
    for (int i = 2; i <= n && p < 0; ++i)
      if (abs(A[i - 1] - A[i]) == K) p = i;
    if (p < 0) p = n;
    while (p > 1 && check(p) < 0)
      --p;
    int d = check(p);
    A[p] += (d < 0 || p == 1)? 1: d;
    for (int i = p; i >= 1; --i)
      if (A[i] > 9) A[i - 1] += A[i] / 10, A[i] %= 10;
    for (int i = (A[0] > 0)? 1: p + 1; i <= n; ++i)
      A[i] = (A[i - 1] == K);

    for (int i = (A[0] == 0); i <= n; ++i)
      putchar(A[i] + '0');
    putchar('\n');
  }
  return 0;
}

E 属性成长 plus

解题思路

注意到和网络赛不一致的地方, 此时按照 $a_i$ 升序排序, 那么 $b_i$ 一定是降序的. 可以证明, 如果选择 $p$ 个 $b$ 属性, 那么选择的 $p$ 个 $b$ 属性的位置一定是排序后位置的一个前缀, $n - p$ 个 $a$ 属性则是后缀. 枚举 $p$ 计算答案就好了, 需要预处理一些量以加速枚举.

时间复杂度 $O(n \log n)$.

一个可能的坑点: 最后的答案可能小于 0.

代码实现

> 点击显示 / 隐藏

// E
// DeP
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

typedef long long LL;
constexpr int MAXN = 2e6 + 5;

int n;
int A[MAXN], B[MAXN], rnk[MAXN];
LL sa[MAXN], sb[MAXN], sia[MAXN], sib[MAXN];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d%d", A + i, B + i);

  for (int i = 1; i <= n; ++i) rnk[i] = i;
  sort(rnk + 1, rnk + 1 + n, [](int i, int j) {
      return A[i] < A[j] || (A[i] == A[j] && B[i] > B[j]);
      });
  for (int i = 1; i <= n; ++i) {
    int b = B[rnk[i]];
    sb[i] = sb[i - 1] + b, sib[i] = sib[i - 1] + (LL) i * b;
  }
  for (int i = n; i >= 1; --i) {
    int a = A[rnk[i]];
    sa[i] = sa[i + 1] + a, sia[i] = sia[i + 1] + (LL) i * a;
  }

  LL ans = LLONG_MIN;
  for (int p = 0; p <= n; ++p) { // B: [1, p], A: [p + 1, n]
    LL ta = (p + 1 <= n)? sia[p + 1] - p * sa[p + 1]: 0;
    LL tb = (1 <= p)? (p + 1) * sb[p] - sib[p]: 0;
    ans = max(ans, ta + tb - (2LL * p - n) * (2LL * p - n));
  }

  printf("%lld\n", ans);
  return 0;
}

F 永久流放

解题思路

记 $f(i, j)$ 表示卡片在第 $j$ 轮传到 $i$ 号玩家时传递次数的期望. 则有

$f(i, j) = \sum_{1 \le k \le i - 1} \frac{1}{n-1} \Big( f(k, j) + 1 \Big) + \sum_{i + 1 \le k \le n} \frac{1}{n-1} \Big( f(k, j - 1) + 1 \Big)$

最后的答案就是 $f(n, m)$, 因为第 $m$ 轮结束时卡片只能在 $n$ 号玩家手里, 否则可以继续传递.

转移利用前缀和优化一下就好了, 时间复杂度 $O(nm)$.

代码实现

> 点击显示 / 隐藏

// F
// DeP
#include <cstdio>

typedef long long LL;
constexpr int MAXN = 1e3 + 5, P = 998244353;

int fpow(int b, int m) {
  int ret = 1;
  while (m > 0) {
    if (m & 1) ret = (LL) ret * b % P;
    b = (LL) b * b % P, m >>= 1;
  }
  return ret;
}

int n, m;
int f[MAXN][MAXN], s[MAXN];

int main() {
  scanf("%d%d", &n, &m);

  int iv = fpow(n - 1, P - 2);
  for (int j = 1; j <= m; ++j) {
    int s0 = 0;
    for (int i = 1; i <= n; ++i)
      s[i] = (s[i - 1] + f[i][j - 1] + 1) % P;
    for (int i = 1; i <= n; ++i) {
      f[i][j] = (f[i][j] + (LL) iv * s0 % P) % P;
      if (i + 1 <= n)
        f[i][j] = (f[i][j] + (LL) iv * (s[n] - s[i] + P) % P) % P;
      s0 = (s0 + f[i][j] + 1) % P;
    }
  }

  printf("%d\n", f[n][m]);
  return 0;
}

G 永世乐土

解题思路

依次考虑答案在二进制下的每一位是否为 1. 当答案某一位是 1 的时候, 能经过位置 $(i, j)$ 的对应值 $A_{i, j}$, 一定有 $A_{i, j}$ 和答案按位与之后和答案相等. 答案某一位是 0 的时候并不影响前面的判断, 所以按照顺序依次确定答案每一位上的值就好了. 此时问题转化为连通性的判定, 接下来怎么做都没问题了.

代码实现

> 点击显示 / 隐藏

// G
// DeP
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
constexpr int MAXN = 1e3 + 5, MAXM = 1e6 + 5;
const int dx[] = { 1, 0 }, dy[] = { 0, 1 };

int n, m, s, e, st, ed;
int A[MAXN][MAXN];
pii S[MAXM], E[MAXM];

inline int idx(int x, int y) { return (x - 1) * m + y; }

namespace DSU {
  int fa[MAXM], size[MAXM];

  void init() {
    for (int i = 1; i <= n * m + 2; ++i)
      fa[i] = i, size[i] = 1;
  }

  int findfa(int u) {
    return (fa[u] == u)? u: fa[u] = findfa(fa[u]);
  }
  inline void join(int u, int v) {
    int fu = findfa(u), fv = findfa(v);
    if (fu == fv) return;
    if (size[fu] < size[fv]) swap(fu, fv);
    fa[fv] = fu, size[fu] += size[fv];
  }
}

int main() {
  int Ti;
  scanf("%d", &Ti);
  while (Ti--) {
    scanf("%d%d", &n, &m);
    scanf("%d", &s);
    for (int i = 1; i <= s; ++i)
      scanf("%d%d", &S[i].first, &S[i].second);
    scanf("%d", &e);
    for (int i = 1; i <= e; ++i)
      scanf("%d%d", &E[i].first, &E[i].second);
    int mx = 0;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j)
        scanf("%d", A[i] + j), mx = max(mx, A[i][j]);

    st = n * m + 1, ed = n * m + 2;
    int ans = 1, k = 0;
    while (ans <= mx) ans <<= 1, ++k;
    while (k >= 0) {
      DSU::init();
      for (int i = 1; i <= s; ++i) {
        int x = S[i].first, y = S[i].second;
        if ((A[x][y] & ans) == ans) DSU::join(st, idx(x, y));
      }
      for (int i = 1; i <= e; ++i) {
        int x = E[i].first, y = E[i].second;
        if ((A[x][y] & ans) == ans) DSU::join(ed, idx(x, y));
      }
      for (int x = 1; x <= n; ++x)
        for (int y = 1; y <= m; ++y) if ((A[x][y] & ans) == ans) {
          for (int d = 0; d < 2; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx <= n && ny <= m && ((A[nx][ny] & ans) == ans))
              DSU::join(idx(x, y), idx(nx, ny));
          }
        }
      if (DSU::findfa(st) == DSU::findfa(ed)) {
        if (--k >= 0) ans ^= (1 << k);
      } else {
        ans ^= (1 << (k--));
        if (k >= 0) ans ^= (1 << k);
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

H 朝歌夜雪

解题思路

既然被简化为一维了, 那就按行称呼好了.

枚举一行中 $n$ 个数的第一个值 $x$, 显然 $x \leq c$, 其余位置均为 $x$ 的约数. 对 $x$ 质因数分解, 记

$x = \prod_i{p_i ^ {c_i}}$

针对于每个质数 $p_i$ 单独考虑, 最后只需要把每个质数的贡献乘起来就是 $x$ 对答案的贡献. 对于质数 $p_i$, 贡献为

$\sum_{k = 0} ^ {\min\{c_i,\ n - 1\}} \binom{c_i}{k} \binom{n - 1}{k}$

感性理解这个式子的方式很多, 比如说一个高为 $c_i$ 宽为 $n$ 的台阶的可能数量之类的. 计算的时候直接枚举就好了, $c_i$ 大概是 $O(\log c)$ 吧…

时间复杂度 $O(c\sqrt c)$, $O(\sqrt c)$ 来源于质因数分解.

至于简化前的情况, 数论忘完了不会做 (

代码实现

滥用 lambda 函数…

> 点击显示 / 隐藏

// H
// DeP
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;
const LL P = 998244353;

int main() {
  int n, C;
  scanf("%d%d", &n, &C);

  int N = max(n, C);
  vector<LL> inv(N + 1), fac(N + 1), ifac(N + 1);
  inv[1] = 1;
  for (int i = 2; i <= N; ++i)
    inv[i] = inv[P % i] * (P - P / i) % P;
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= N; ++i)
    fac[i] = i * fac[i - 1] % P, ifac[i] = inv[i] * ifac[i - 1] % P;

  auto binom = [&](int x, int y) {
    return fac[x] * ifac[y] % P * ifac[x - y] % P;
  };

  LL ans = 0;
  for (int x = 1; x <= C; ++x) {
    auto factor = [](int v) {
      vector<int> ret;
      for (int d = 2; d * d <= v; ++d) if (v % d == 0) {
        ret.push_back(0);
        while (v % d == 0) ++ret.back(), v /= d;
      }
      if (v > 1) ret.push_back(1);
      return ret;
    };
    vector<int> fc = factor(x);
    auto f = [&](int c) {
      LL ret = 0;
      for (int k = 0; k <= min(c, n - 1); ++k)
        ret = (ret + binom(c, k) * binom(n - 1, k) % P) % P;
      return ret;
    };
    LL t = 1;
    for (auto c: fc) t = t * f(c) % P;
    ans = (ans + t) % P;
  }
  printf("%lld\n", ans);
  return 0;
}

DepletedPrism's Blog

2022 年西安电子科技大学校赛的部分题解

现场赛

D 数位相邻

解题思路

代码实现

E 属性成长 plus

解题思路

代码实现

F 永久流放

解题思路

代码实现

G 永世乐土

解题思路

代码实现

H 朝歌夜雪

解题思路

代码实现