# D

# 题目大意

给定 $n$ 个数 $a_1, \ldots, a_n$，你可以做 $0$ 次或任意次操作，每次操作你可以选择任意一个数 $-1$。
若要满足

$$\forall i \in [1, n), \quad | a_i - a_{i + 1} | \le 1$$

则最小操作次数是多少

# 数据范围

• $1 \le T \le 5 \times 10^4$
• $2 \le N \le 3 \times 10^5$
• $sum(N) \le 3 \times 10^5$

# 题解

每个数都对其左右两边的数有限制
对于 $a_i$，其左边数最低为 $\min(a_{i - 1}, a_i + 1)$，其右边最低为 $\min(a_{i + 1}, a_i + 1)$

所以只需要做两次循环，先正着跑一遍 $a_i = \min(a_i, a_{i - 1} + 1)$ 然后再反着跑一遍 $a_i = \min({a_i, a_{i + 1} + 1})$
正着跑保证了左侧的约束，反着跑保证了右侧的约束
所得到的数组就是答案，计算与原数组的差即可

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

import math
_ = int(input())

while _ != 0:
    n = int(input())
    a = [0] + list(map(int, input().split()))
    b = [0] + [a[i] for i in range(1, n + 1)]

    for i in range(2, n + 1):
        b[i] = min(b[i - 1] + 1, b[i])
    for i in range(n - 1, 0, -1):
        b[i] = min(b[i + 1] + 1, b[i])
    
    res = 0
    for i in range(1, n + 1):
        res += a[i] - b[i]
   
    print(res)
    _ -= 1

# E（不懂的神秘）

# 题目大意

给你一个 $n \times n$ 的网格，由 # 和 . 组成。你初始的时候在 $(n, c)$，你每次可以到左上、正上、右上
如果到的点是 # 并且其下方没有 # ，则你可以摧毁它，然后问你，$(1, 1), \ldots, (1, n)$ 中，哪些点是可达的？

# 数据范围

• $1 \le n \le 3000$

# 题解

我的想法就是从起点开始 $BFS$，如果

• 遇到可以摧毁的 #
• 或者是某个 . 其下方没有 #
• 直接抵达 $(1, x)$
  那么就代表，这列是可达的
  但是 $\color{red}{WA~28 / 48}$，只过了 $50\%$，暂时我还没搞懂
  

  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

  void solve() { cin >> n >> c; a = vector<vector<char>>(n + 1, vector<char>(n + 1)); st = vector<vector<bool>>(n + 1, vector<bool>(n + 1)); flag = vector<bool>(n + 1); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j]; vector<vector<int>> preCol(n + 1, vector<int>(n + 1)); for (int j = 1; j <= n; j++) for (int i = 1; i <= n; i++) preCol[j][i] = preCol[j][i - 1] + (a[i][j] == '#'); // (n, c) queue<PII> q; q.push({n, c}); while (q.size()) { PII t = q.front(); q.pop(); int x = t.first, y = t.second; if (preCol[y][n] - preCol[y][x] == 0 || (x == 1 && a[x][y] != '#')) flag[y] = true; for (int i = 1; i <= 3; i++) { int xx = x + dx[i], yy = y + dy[i]; if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && !st[xx][yy]) { if (a[xx][yy] == '#' && preCol[yy][n] - preCol[yy][xx] != 0) continue; q.push({xx, yy}), st[xx][yy] = true; } } } for (int i = 1; i <= n; i++) cout << (flag[i] && preCol[i][n] != n); cout << '\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
38

void solve() {
    cin >> n >> c;
    a = vector<vector<char>>(n + 1, vector<char>(n + 1));
    st = vector<vector<bool>>(n + 1, vector<bool>(n + 1));
    flag = vector<bool>(n + 1);

    for (int i = 1; i <= n; i++)    for (int j = 1; j <= n; j++)    cin >> a[i][j];

    vector<vector<int>> preCol(n + 1, vector<int>(n + 1));

    for (int j = 1; j <= n; j++)    for (int i = 1; i <= n; i++)    preCol[j][i] = preCol[j][i - 1] + (a[i][j] == '#');


    queue<PII> q;
    q.push({n, c});

    while (q.size()) {
        PII t = q.front();
        q.pop();
        int x = t.first, y = t.second;

        if (preCol[y][n] - preCol[y][x] == 0 || x == 1) flag[y] = true;

        for (int i = 1; i <= 3; i++) {
            int xx = x + dx[i], yy = y + dy[i];

            if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && !st[xx][yy]) {
                if (!flag[yy] && a[xx][yy] == '#' && preCol[yy][n] - preCol[yy][xx] != 0)    continue;

                q.push({xx, yy}), st[xx][yy] = true;
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << flag[i];
    cout << '\n';
}

# F

# 题目大意

定义好数如下
一个数显然可以拆分为 $$\sum\limits_{i = 0}^n d_i \times 10^i$$
其中，$n$ 是 $num$ 的位数
如果满足 $d$ 是一个不严格递增序列，则 $num$ 就是好数

现在给你一个数 $n$，问存不存在 $kn~(k \ge 1)$ 是好数，如果存在的话 $\min kn$ 是多少？

# 数据范围

• $1 \le n \le 3 \times 10^6$

# 题解

这题的关键在于一个性质

$$(x \times 10 + i) \mod n = (x \mod n \times 10 + i) \mod n$$

所以，定义

• $r$ 是 $x \% n$
• $last$ 是 $n$ 的最后一位
  如果 $(r, last)$ 相同，代表状态重复出现
• 过去怎么造出来的已经不重要了
• 只要 (余数，个位) 一样，未来的可能性就完全一样

所以我们可以暴搜
用 pre_r 和 pre_l 去记录上一步的状态

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

int n;
bitset<10> vis[N];
int pre_r[N][10], pre_l[N][10];

void solve() {
    cin >> n;

    if (n % 10 == 0) {
        cout << -1 << '\n';
        return;
    }

    queue<pair<int,int>> q;

    for (int d = 1; d <= 9; d++) {
        int r = d % n;

        if (r == 0) {
            cout << d << '\n';
            return;
        }
        
        vis[r][d] = 1, pre_r[r][d] = -1, pre_l[r][d] = -1;
        q.push({r, d});
    }

    while (!q.empty()) {
        auto [r, last] = q.front();
        q.pop();

        for (int d = last; d <= 9; d++) {
            int nr = (r * 10 + d) % n;
            if (vis[nr][d]) continue;

            vis[nr][d] = 1, pre_r[nr][d] = r, pre_l[nr][d] = last;

            if (nr == 0) {
                string ans;
                int cr = nr, cl = d;
                while (cl != -1) {
                    ans.push_back('0' + cl);
                    
                    int tr = pre_r[cr][cl], tl = pre_l[cr][cl];
                    cr = tr, cl = tl;
                }
                reverse(ans.begin(), ans.end());
                cout << ans << '\n';
                return;
            }

            q.push({nr, d});
        }
    }

    cout << -1 << '\n';
}