Wings 的博客Wings 的博客
归档 系列 分类 标签 关于 友链 开往
Wings 的博客Wings 的博客

目录

目录

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

Wings avatarWings  收录于  类别 ACM
     约 1362 字   预计阅读 6 分钟    次阅读     条评论  

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

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

1≤n≤10106,0≤k≤91 \le n \le 10^{10^6}, 0 \le k \le 9

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

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

  1. 没有进位
  2. 有进位

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

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

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

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

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

复杂度 O(n)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;
}

nn 个物品, 每个物品有两个值 ai,bia_i, b_i, 且满足不存在某一个物品的两个值都分别大于另一个物品的. 从中选 xx 个物品放入集合 AA, yy 个物品放入集合 BB, 显然 x+y=nx + y = n. 若某物品 ii 是放入集合 AA 的第 kk 个物品, 那么它带来的贡献是 kaika_i. 同理若某物品 ii 是放入集合 BB 的第 kk 个物品, 那么它带来的贡献是 kbikb_i. 最后, 将贡献累加, 再减去 (x−y)2(x - y)^2, 得到最后的值. 问这个最大值是多少. (物品的选择顺序自行确定)

1≤n≤2×106,0≤ai,bi≤1061 \le n \le 2 \times 10^6, 0 \le a_i, b_i \le 10^6

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

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

复杂度 O(nlogn)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;
}

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

1≤n,m≤103,1≤aij≤1091 \le n, m \le 10^3, 1 \le a_{ij} \le 10^9

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

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

复杂度 O(nmloga)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;
}

在 a1∼ana_1 \sim a_n 中填入范围在 [1,c][1, c] 中的数, 使得 ∀i∈[2,n],ai−1∣ai\forall i \in [2, n], a_{i-1} \mid a_i. 问一共有多少种填法. 1≤n,c≤1051 \le n, c \le 10^5

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

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

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

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

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

复杂度 O(nπ(n))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-06-29
 | 主页
0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.5.6