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

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

找出一个严格大于 $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$ 就可能有一些情况:

  1. 没有进位
  2. 有进位

没有进位, 那么就做完了; 有进位的话, 可以等效成 $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)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
}

$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)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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 \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)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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;
}