第二届ACC(AcWing Cup)全国联赛

T1 人话版本

对于最开始的 $0$，有两种操作：

  • 加上非负数 $a$，代价为 $a$
  • 乘以 $2$，没有代价

问，把 $0$ 变成 $n$ 的最小代价

求解

首先，注意非负整数，说明我们只能让我们的数字变大，因此不能操作到超过当前数，而另一个操作是把当前数字乘以2，因此这一步我们只能得到偶数

那么如果目标数是一个奇数，我们就得找到它最近的偶数，然后代价加上1即可，而最近的偶数，可以用同样的办法来得到

特别地，当目标数是2的整数幂的时候，答案是1，因为只需要得到1，然后不断地乘以2即可，而乘以2是不消耗代价的

代码

1
2
3
4
5
6
7
8
n = int(input())
def solve(x):
    if not x&(x - 1):
        return 1
    if x&1:
        return solve(x / 2) + 1
    return solve(x / 2)
print(solve(n))

T2 人话版本

给一个 $n$ 进制数的前 $101$ 位权重值（也就是 $n ^ i$，其中$i = 0,1\dots100$），以及一个数 $m$

问，能不能在这 $101$ 个数字中选一些（也可以不选）加到 $m$ 上，再选另一些出来求和，让它与前面的和相等

注意，每个权重只能选一遍

求解

把 $m$ 表示为 $n$ 进制数，目标是把每一位加上 $0$ 或者 $1$，让它的数位变成 $0$ 或者 $1$ 构成的数，因为每一个权重只有一个，表示选择或者不选择，不能多选

假设最开始 $m$ 的重量全放在右边，而对于这些权重，取 $1$ 表示放左侧，取 $0$ 表示放右侧

左边不够的时候，需要用右侧去代替左侧补充，使得左侧进位，这样可以让权重的需求降低

例如，$3, 7$

$7$ 对应三进制数字 $21$，表示第一个权重选 $1$ 个，第二个权重选 $2$ 个

而当第二个权重需要两个的时候，我们就需要做处理，因为每个权重只有一个

由于是三进制，当前数字取二，我们可以把左右两侧都多放一个当前权重，这样就可以保证每个权重只用一次并且平衡，因为左边多放一个当前的权重能导致进位，把对当前权重的需求，转换为下一位更高权重的需求了，变成 $91和73$，而也只有这种情况下（当前位是$n - 1$）我们可以做此处理

其他情况无法凑出，因为如果不是仅仅相差一位，凑过去右侧仍然会导致多用权重

例如，$4, 7$

$7$ 对应四进制数字 $13$，表示第一个权重选 $3$ 个，第二个权重选 $1$ 个

由于我们没有 3 个 1，因此我们要想办法，左右同时加上1，转换为 2 个 4 和 $7 + 1$ ，这样就可以让我们把对1的需求从3个降低为1个，但是加重了下一权重的需求

当我们需要 2 个 4 的时候，我们仍然需要做处理，我们将左右两侧都补充 4，但是由于距离进位还差 2 个 4，因此是凑不出的

因此我们有：

  • 当前位置是 0 或者 1，无需处理
  • 如果当前是 $n - 1$ ，那么右侧重量补充

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    while (m) {
        if (m % n == 1 || m % n == 0) m /= n;
        else if (m % n == n - 1) m /= n, m ++ ;
        else return 0 & puts("NO");
    }

    puts("YES");

    return 0;
}

T3 人话版本

$n \times m$ 的矩阵，有 0 表示空地，1表示陷阱

在空地上，可以决定走上下左右四个方向

问从起点到终点的最少次数是多少

注意，每一次移动可以移动 $1 到 k$ 步，我们回答的是 次数，而不是 步数

求解

bfs即可，每一次枚举走的步数，更新最近距离

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 2010;
int step[N][N];
int g[N][N];
int wx[4] = {-1, 1, 0, 0};
int wy[4] = {0, 0, 1, -1};

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            char c;
            cin >> c;
            if (c == '#') g[i][j] = 1;
        }

    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    memset(step, -1, sizeof step);
    step[sx][sy] = 0;
    if (sx == tx && sy == ty) return 0 & puts("0");

    queue<PII> q;
    q.push({sx, sy});

    while (q.size()) {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
            for (int j = 1; j <= k; j ++ ) {
                int dx = t.first + wx[i] * j; 
                int dy = t.second + wy[i] * j;

                if (g[dx][dy] || dx < 1 || dx > n || dy < 1 || dy > m) break;
                if (step[dx][dy] != -1 && step[dx][dy] <= step[t.first][t.second]) break;
                if (step[dx][dy] != -1) continue;

                step[dx][dy] = step[t.first][t.second] + 1;
                q.push({dx, dy});
                if (dx == tx && dy == ty) {
                    printf("%d", step[tx][ty]);
                    return 0;
                }
            }
    }
    puts("-1");
    return 0;
}