# A

水题

1
2
3
4

void solve () {
    cin >> n;
    cout << (400 % n == 0 ? 400 / n : -1);
}

# B

水题，给定 $n,m$，判断 $x = \sum\limits_{i=0}^m {n^i}$ 是否 $\le 10^9$
利用爆一边的数据范围后，会返回另一边的值的特性就能 $AC$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int n, m, res = 0;

void solve () {
    cin >> n >> m;
    for (int i = 0; i <= m; i++) {
        int k = pow(n, i);
        if (k < 0 || k > 1e9) {
            cout << "inf" << endl;
            return;
        }

        res += k;

        if (res > 1e9 || res < 0) {
            cout << "inf" << endl;
            return;
        }
    }

    cout << res << endl;
}

# C

# 题目大意

当且仅当一个正整数 $X$ 满足以下条件时，它才被称为好整数：

• 存在一对正整数 $(a,b)$ ，使得 $X = 2^a \times b^2$.
  给定正整数 $N(1 \le N \le 10^{18})$ ，求在 $1$ 和 $N$ 之间（包括首尾两个整数）的好整数个数。

# 题解

显然，就算是 $O(n)$ 的做法也是会超时的，考虑优化

这样就可以优化到 $log$ 的时间复杂度
但是，此时会出现 $sqrt$ 的精度问题， double  类型尾数为 $52$ 位，可精确表示约 ​​15-17 位十进制数​​，当数据超过 $10^{15}$ 的时候，$sqrt$ 就会有精度问题，此时需要手写$sqrt$，题解后给出两种手写方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int getT(int x) {
    for (int i = 1; i <= x; i++)
        if ((i + 1) * (i + 1) > x)
            return i;
}

void solve () {
    cin >> n;
    int cnt = 0;
    for (int i = 1;; i++) {
        int k = pow(2, i);
        if (k > n)
            break;

        int maxx = n / k;
        cnt += (int)((getT(maxx) + 1) / 2);
    }

    cout << cnt << endl;
}

# 暴力手写

1
2
3
4
5

int getT(int x) {
    for (int i = 1; i <= x; i++)
        if ((i + 1) * (i + 1) > x)
            return i;
}

# 整数二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int efSqrt(int x) {
    if (x < 0)
	    return -1;
	    
    int l = 0, r = x;
    
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (mid <= x / mid)
	        l = mid;
        else
	        r = mid - 1;
    }
    
    return l;
}

# D

# 题目大意

高桥居住的小镇被划分成一个由 $H$ 行和 $W$ 列组成的网格。每个单元格要么是一条路，要么是一堵墙
我们把从上面 $(1\leq i \leq H)$ 起第 $i$ 行，从左边 $(1\leq j \leq W)$ 起第 $j$ 列的单元格称为单元格 $(i,j)$
每个单元格的信息由长度为 $W$ 的 $H$ 字符串 $S_1,S_2,...,S_H$ 提供。具体来说：

• 如果 $S_i$ 的 $j-th$ 字符是 $(1\leq i \leq H,1\leq j\leq W)$ 是 . ，那么 $(i,j)$ 单元格就是一条路
• 如果是 # ，那么 $(i,j)$ 单元格就是一堵墙

他可以按任意顺序重复执行以下两种操作：

• 移动到相邻的单元格（向上、向下、向左或向右），该单元格位于小镇内且是一条道路。
• 从四个方向（上、下、左或右）中选择一个，然后朝该方向踢一脚
  • 当他踢出一脚时，如果该格是一堵墙，则该格就会变成一条路
  • 如果距离最多 $2$ 步的一些单元格在城镇之外，则仍然可以进行前踢，但城镇之外的任何东西都不会改变
    他从 $(A,B)$ 单元格开始，想要移动到 $(C,D)$ 单元格的鱼店。
    可以保证他起始的单元格和有鱼店的单元格都是道路。
    求他到达鱼店所需的最少个前踢

# 数据范围

• $1\leq H,W \leq 1000$

# 题解

使用 $0-1~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

  int dx[] = {0, 1, -1, 0, 0}; int dy[] = {0, 0, 0, 1, -1}; int n, m, dist[N][N]; int a, b, c, d; char s[N][N]; bool inside(int x, int y) { return (x >= 1 && x <= n && y >= 1 && y <= m); } void bfs() { memset(dist, 0x3f, sizeof dist); deque<PII> q; dist[a][b] = 0; q.push_front({a, b}); while (q.size()) { auto [x, y] = q.front(); q.pop_front(); if (x == c && y == d) break; for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 2; j++) { int nx = x + j * dx[i], ny = y + j * dy[i]; if (!inside(nx, ny)) break; if (s[nx][ny] == '.') { if (j == 1 && dist[nx][ny] > dist[x][y]) dist[nx][ny] = dist[x][y], q.push_front({nx, ny}); } else { if (dist[nx][ny] > dist[x][y] + 1) dist[nx][ny] = dist[x][y] + 1, q.push_back({nx, ny}); } } } } } void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> s[i][j]; cin >> a >> b >> c >> d; bfs(); cout << dist[c][d] << endl; }