2022 西安电子科技大学程序设计竞赛补题

Wings 收录于类别 ACM

2022-06-02 2022-06-29 约 1362 字预计阅读 6 分钟次阅读条评论

大半年没训练, 加上早起做数电实验赶场导致状态不好, 被 pllj 的键盘薄鲨心态爆炸, 成绩惨淡…

D. 数位相邻

找出一个严格大于 $n$ 的最小的整数 $m$, 使得 $m$ 中任意相邻两个数位的差的绝对值不等于 $k$.

$1 \le n \le 10^{10^6}, 0 \le k \le 9$

看到就跳过了, 这种题需要分析的题一直是我的弱项.

很显然应该是 $O(n)$ 扫一遍, 于是一个简单的想法是, 从高位开始, 找到第一个不符合的数位 $p$, 即 $|a_p - a_{p+1}| = k$, 然后这一位加 $1$, 更低位就尽量填最小(如 $0$, 可能会因为限制填不同的, 先放一边, 之后分析). 如果都符合, 那么由于需要 $m > n$, 所以可以认为 $p = 0$. 第 $p$ 位加 $1$ 就可能有一些情况:

没有进位
有进位

没有进位, 那么就做完了; 有进位的话, 可以等效成 $p+1$ 位需要改变. 需要注意, 原本 $|a_{p+1} - a_{p+2}| \ne k$, 有可能因为 $a_{p+1} + 1$ 而导致非法. 这样就需要继续调整, 根据贪心, 尝试加 $2$.

还需要注意的是, 这一位也可能导致进位, 可能是直接 $9+1$, 也可能是 $8+1$ 非法, 从而 $8+2$. 然后就需要继续往高位走. (这里可以简单证明一下只可能是加 $1$ 或者 $2$)

这样走到最后可能导致最高位进位, 这里需要判断一下边界条件. 最高位进位, 新的最高位就始终是 $1$, 因为没有更高位, 不需要比较.

那么问题就可以分成两步, 首先找到最高的不满足条件的位置 $p$, 然后尝试给 $a_p$ 加 $1$, 若不满足条件则加 $2$(第一次一定是加 $1$, 加 $2$ 是由于进位可能导致的, 这里可以综合在一起). 若导致进位则改变 $p$, 重新判断是否满足条件. 直到找到一个满足条件的 $p$.

将找到的 $a_p$ 按照需求加 $1$ 或者 $2$ (显然不会导致进位), 然后依次考虑更低位. 显然填满足条件的最小的最好. 这里可以简单写成 a[i] = a[i+1] == k, 也就是填 $0$ 如果不满足, 那就填 $1$. 否则填 $0$.

复杂度 $O(n)$

cpp

int T = 1, k, a[MAXN], n;
char str[MAXN];

int delta(int p) {
  if (p+1 >= n)
    return 1;
  for (int i = 1; i <= 2 && i + a[p] <= 9; i++)
    if (abs(i + a[p] - a[p+1]) != k)
      return i;
  return 0;
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%s%d", str, &k);
    n = strlen(str);
    for (int i = 0; str[i]; i++)
      a[n-i-1] = str[i] - '0';
    a[n] = a[n+1] = a[n+2] = 0;
    int p = 0;
    for (p = max(0, n-2); p; p--)
      if (abs(a[p] - a[p+1]) == k)
        break;
    for (; p <= n; p++)
      if (delta(p) && a[p] + delta(p) <= 9)
        break;
    a[p] += delta(p);
    n += p == n;
    for (int i = p - 1; ~i; i--)
      a[i] = a[i+1] == k;
    for (int i = 0; i < n; i++)
      str[n-i-1] = a[i] + '0';
    puts(str);
  }
  return 0;
}

E. 属性成长 plus

$n$ 个物品, 每个物品有两个值 $a_i, b_i$, 且满足不存在某一个物品的两个值都分别大于另一个物品的. 从中选 $x$ 个物品放入集合 $A$, $y$ 个物品放入集合 $B$, 显然 $x + y = n$. 若某物品 $i$ 是放入集合 $A$ 的第 $k$ 个物品, 那么它带来的贡献是 $ka_i$. 同理若某物品 $i$ 是放入集合 $B$ 的第 $k$ 个物品, 那么它带来的贡献是 $kb_i$. 最后, 将贡献累加, 再减去 $(x - y)^2$, 得到最后的值. 问这个最大值是多少. (物品的选择顺序自行确定)

$1 \le n \le 2 \times 10^6, 0 \le a_i, b_i \le 10^6$

我是 sb. 简单的排序不等式. 排一下, 求前后缀, 枚举分界点, 没了. 考场丢 pair 里排导致排错了.

需要注意的是, 答案可能是负数, 所以最后开始枚举分界点前, ans 要设为 $-INF$ 而不是 $0$.

复杂度 $O(nlogn)$

cpp

int T = 1, n;

struct Node {
  int a, b;
  bool operator < (const Node &N) const {
    return a == N.a ? b > N.b : a < N.a;
  }
};

vector<Node> v;
LL pre_b[MAXN], suf_a[MAXN];
LL pre_bb[MAXN], suf_aa[MAXN];

int main() {
  while (T--) {
    scanf("%d", &n);
    v.push_back({0, 0});
    for (int i = 1; i <= n; i++) {
      int a, b;
      scanf("%d%d", &a, &b);
      v.push_back({a, b});
    }
    sort(v.begin()+1, v.end());
    for (int i = 1; i <= n; i++) {
      pre_b[i] = pre_b[i-1] + v[i].b;
      pre_bb[i] = pre_bb[i-1] + pre_b[i];
    }
    for (int i = n; i; i--) {
      suf_a[i] = suf_a[i+1] + v[i].a;
      suf_aa[i] = suf_aa[i+1] + suf_a[i];
    }
    LL ans = -INF;
    for (int i = 0; i <= n + 1; i++)
      ans = max(ans, pre_bb[i] + suf_aa[i+1] - LL(n-i-i)*(n-i-i));
    printf("%lld\n", ans);
  }
  return 0;
}

G. 永世乐土

$n \times m$ 的四连通网格, 每个格子有一个值 $a_{ij}$. 其中有 $s$ 个起点和 $e$ 个终点. 选择一个起点到终点的路径, 使得格子的值按位与最大. 求最大值.

$1 \le n, m \le 10^3, 1 \le a_{ij} \le 10^9$

题不难, 考场搞 E 心态爆炸, G 压根没怎么想.

位运算, 拆位考虑. 贪心, 从大到小考虑每一位. 考虑某一位的时候, 简单看成 01 矩阵即可. 这样, 如果有某个起点和某个终点是连通的, 那么答案这一位是 1. 如果起点终点集合被分开, 则答案这一位是 0. 如果确定了某一位是 1, 那么接下来再看连通性的时候, 就不能看全部格子了. 假如考虑最高位时, 为 1 的格子集合为 $S$, 那么接下来就只能在 $S$ 中考虑, 而不是全部的 $nm$ 个格子. 可以发现, 这个可用点集合是越来越小的. 如果这一位为 0, 那么可用点集合不变. (自然语言说不明白, 看代码中的 mask 数组吧).

复杂度 $O(nmloga)$

cpp

const int MAXN = 1e3 + 10;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int T = 1, n, m, s, e, layout[MAXN][MAXN];
vector<PII> ss, ee;
int vis[MAXN][MAXN], mask[MAXN][MAXN];

bool check(int x, int y) {
  if (x <= 0 || x > n || y <= 0 || y > m)
    return false;
  return true;
}

void dfs(int x, int y, int k) {
  vis[x][y] = 1;
  for (int t = 0; t < 4; t++) {
    int nx = x + dx[t], ny = y + dy[t];
    if (check(nx, ny) && mask[nx][ny] && (layout[nx][ny] & (1 << k)) && !vis[nx][ny])
      dfs(nx, ny, k);
  }
}

int main() {
  scanf("%d", &T);
  while (T--) {
    ss.clear(); ee.clear();
    scanf("%d%d", &n, &m);
    scanf("%d", &s);
    for (int i = 0; i < s; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      ss.emplace_back(x, y);
    }
    scanf("%d", &e);
    for (int i = 0; i < e; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      ee.emplace_back(x, y);
    }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) {
        scanf("%d", &layout[i][j]);
        mask[i][j] = 1;
      }
    int ans = 0;
    for (int k = 29; ~k; k--) {
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
          vis[i][j] = 0;
      for (auto[x, y] : ss)
        if (mask[x][y] && (layout[x][y] & (1 << k)))
          dfs(x, y, k);
      for (auto[x, y] : ee)
        if (mask[x][y] && (layout[x][y] & (1 << k)))
          ans |= vis[x][y] << k;
      if (ans & (1 << k))
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= m; j++)
            mask[i][j] = vis[i][j] & mask[i][j];
    }
    printf("%d\n", ans);
  }
  return 0;
}

H. 朝歌夜雪

在 $a_1 \sim a_n$ 中填入范围在 $[1, c]$ 中的数, 使得 $\forall i \in [2, n], a_{i-1} \mid a_i$. 问一共有多少种填法. $1 \le n, c \le 10^5$

第一眼动态规划, 但是得二维, 显然复杂度不对. ~~然后就看题解去了~~

这种关于约数倍数的题, 思考的方向是质因数分解, 对每个质因数考虑, 就像位运算的题把每一位拉出来考虑一样.

可以发现, 每个质因数对答案产生的贡献是相互独立的. 那么接下来考虑枚举第 $n$ 个数, 假设是 $x = \Pi p_i^{e_i}$. 对每个质因数 $p_i$ 考虑, $p_i^{e_i} \mid a_n$ ($a_n = x$), 然后看 $a_1 \sim a_{n-1}$, 填入 $p_i^{k_i}$, 只要幂次形成不递减的序列, 那么这个质因数就满足条件了. 这样的填法有多少? 隔板法可以轻松算出来.

将每个位置看成球, 假设现在枚举的最后一位有一个因数 $p_i^{e_i}$, 那么需要把前 $n - 1$ 个球, 分成 $e_i + 1$ 份 (指数从 $0$ 到 $e_i$), 可以空. 所以这个因数对答案的贡献是 $\binom{n+e_i-1}{e_i}$. (隔板法, 共 $e_i$ 个板, $n - 1$ 个球, 可以空). 然后所有的 $p_i^{e_i}$ 贡献乘起来, 得到当前枚举的 $a_n$ 的贡献. 枚举 $a_n = x$ 对答案的贡献相加.

注意一下, 组合数在求的时候, 数组开 $2 \times 10^5$ (表达式中有 $n+e_i-1$).

复杂度 $O(n \pi(n))$

cpp

int pls(LL a, LL b) {
  a += a < 0 ? P : 0, b += b < 0 ? P : 0;
  return a + b >= P ? a + b - P : a + b;
}
int mult(LL a, LL b) {
  a += a < 0 ? P : 0, b += b < 0 ? P : 0;
  return a * b >= P ? a * b % P : a * b;
}

int power(int a, int b = P-2) {
  int res = 1;
  while (b) {
    if (b&1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}

int frac[MAXN], inv[MAXN];
void init_comb(int _n) {
  frac[0] = inv[0] = 1;
  for (int i = 1; i <= _n; i++) frac[i] = mult(frac[i - 1], i);
  inv[_n] = power(frac[_n]);
  for (int i = _n-1; i; i--) inv[i] = mult(inv[i + 1], i + 1);
}
int comb(int n, int m) {
  return mult(mult(frac[n], inv[m]), inv[n - m]);
}

int prime[MAXN], isnotprime[MAXN], p_cnt;
void init_prime(int _n) {
  isnotprime[0] = isnotprime[1] = 1; p_cnt = 0;
  for (int i = 2; i <= _n; i++) {
    if (!isnotprime[i]) prime[p_cnt++] = i;
    for (int j = 0; j < p_cnt && i * prime[j] <= _n; j++) {
      isnotprime[i * prime[j]] = 1;
      if (!(i % prime[j])) break;
    }
  }
}

int T = 1, n, c;
int ans = 0;

vector<PII> prime_dec(int x) {
  vector<PII> v;
  for (int i = 0; i < p_cnt && x > 1; i++) {
    int p = prime[i], e = 0;
    while (x % p == 0) { e++, x /= p; }
    if (e) v.emplace_back(p, e);
  }
  return v;
}

int main() {
  scanf("%d%d", &n, &c);
  init_prime(c);
  init_comb(n+c);
  ans = 1;
  for (int m = 2; m <= c; m++) {
    int res = 1;
    vector<PII> v = prime_dec(m);
    for (auto pa : v) {
      int e = pa.second;
      res = mult(res, comb(n+e-1, e));
    }
    ans = pls(ans, res);
  }
  printf("%d\n", ans);
  return 0;
}

目录

目录

2022 西安电子科技大学程序设计竞赛补题

D. 数位相邻

E. 属性成长 plus

G. 永世乐土

H. 朝歌夜雪

目录

2022 西安电子科技大学程序设计竞赛 补题

D. 数位相邻

E. 属性成长 plus

G. 永世乐土

H. 朝歌夜雪

2022 西安电子科技大学程序设计竞赛补题