AtCoder Beginner Contest 443

RookieSama_

公告

欢迎来到小破站ようこそ私のブログへ！

Learn Morea

标签

1766 字

9 分钟

AtCoder Beginner Contest 443

2026-02-01

题解

C Addiction#

题目大意：#

你可以打开电脑摸鱼，但你的同事会关掉你的电脑，并且你将在关掉电脑后的100分钟内不会再次打开电脑，问你摸鱼的总时间。

思路：#

很明显，本题是模拟题，需要遍历模拟同事来关电脑，若从关电脑的那一刻起到下一次查岗的时间相差 100 分钟以上，则会摸鱼，遍历所有 $a_i$ 最近一次减去关电脑时间即可

易错点：#

需要特别注意，从0分钟开始是默认打开电脑的（如果只靠 $a_i$ 判断需要特别加上该时间）
计算最后一段时间，即从 $a_n$ ~ $m$ 的时间

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
6
const int N = 3e5 + 10;
7

8
int n, m;
9
int a[N];
10

11
void solve(){
12
    cin >> n >> m;
13
    for(int i = 1; i <= n; i++) cin >> a[i];
14
    sort(a + 1, a + 1 + n);
15
    int flag = 1, now = 0, sum = 0;
16
    for(int i = 1; i <= n; i++){
17
        if(flag){
18
            sum += a[i] - now;
19
            flag = 0;
20
            now = a[i];
21
        }else{
22
            if(a[i] - now >= 100){
23
                sum += a[i] - now - 100;
24
                now = a[i];
25
            }
26
        }
27
    }
28
    if(flag){
29
        cout << m << endl;
30
        return;
31
    }
32
    if(m - now >= 100){
33
        sum += m - now - (flag? 0 : 100);
34
    }
35
    cout << sum << endl;
36
}
37

38
signed main(){
39
    IOS;
40
    int _ = 1;
41
    //cin >> _;
42
    while(_--){
43
        solve();
44
    }
45
}

D: Pawn Line#

题目大意:#

一个 $n * n$ 大小的棋盘，每一列都有一个棋子，你可以让棋子向上走（不能向下）现在问你用最少的步数，让相邻的棋子距离最多为 1 即 $|a_i - a_{i+1}|==1$

理解：#

现在要求所有点都要相邻，并且只能往上，那么一定是找最小的高度点，他决定了其他点的位置
- 比如：有一个在第一行，那么旁边两个点最远也只能在第二行
- 因此，当前前的点移动的最小数就是，左右两边行数最小的值 - 自己所在的行数 - 两点列之差
- $a_i - min(l_i,r_i)-abs(j-i)$
最后把所有点全部加起来即可

代码:#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
6
const int N = 3e5 + 10;
7

8
using PII = pair<int,int>;
9

10
int n, m;
11
int a[N], l[N], r[N];
12

13
void init(){
14
    for(int i = 1; i <= n; i++) l[i] = r[i] = 0;
15
}
16

17
void solve(){
18
    cin >> n;
19
    init();
20

21
    for(int i = 1; i <= n; i++) cin >> a[i];
22
    l[1] = a[1], r[n] = a[n];
23
    for(int i = 2; i <= n; i++){
24
        l[i] = min(a[i], l[i - 1] + 1);
25
    }
26
    for(int i = n - 1; i >= 1; i--){
27
        r[i] = min(a[i], r[i + 1] + 1);
28
    }
29
    int ans = 0;
30
    for(int i = 1; i <= n; i++){
31
        int cur = min(l[i], r[i]);
32
        ans += (a[i] - cur);
33
    }
34
    cout << ans << endl;
35

36
}
37

38
signed main(){
39
    IOS;
40
    int _ = 1;
41
    cin >> _;
42
    while(_--){
43
        solve();
44
    }
45
}

E Silver#

题目大意:#

$N*N$ 的地图，你从 $(N,C)$ 出发，要求到达 $(1,j)$ 的点,若能到达，则 $s_j=1$ 否则为 $s_j=0$
你能够往左上方，右上方或者上方走。如果存在墙壁，且该列中除了这行以外的所有行都是能走的地方，就可以撞破该墙壁
- 即： $g[i][j+1,N]=='.'$ 就能撞破 $g[i][j]$ 的墙壁,且变为能够走的单元格
让你输出 $s_{1-N}$

理解:#

其实就是类似于 bfs 走迷宫的题目，但本题有一个状态转移的问题
- 如果当前墙壁能被破坏，则当前列所有墙壁都能被破坏。
- 如果无法破坏，则保留无法破坏的规则，往后的所有也都无法破坏
- 最后只要暴力模拟所有情况即可，找到能走到 $g[1][j]$ 的所有点

代码：#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
6
const int N = 3e3 + 10;
7

8
using PII = pair<int,int>;
9

10
class Point{
11
public:
12
    int x, y, dis;
13
};
14

15
int n, m;
16
char g[N][N];
17
int f[N][N]; //当前点是否能够直接破坏
18
int st[N][N];
19

20

21
void bfs(){
22
    st[n][m] = 1;
23
    for(int i = n; i >= 1; i--){
24
        for(int j = 1; j <= n; j++){
25
            if(g[i][j] == '#') {
26
                f[i][j] = 1;
27
            }
28
            f[i - 1][j] = f[i][j];
29
        }
30
    }
31

32
    for(int i = n; i > 1; i--){ //从第 n 遍历
33
        for(int j = 1; j <= n; j++){// j 列
34

35
            if(st[i][j] == 1){
36
                int dy[3] = {0, 1, -1};
37
                int dx[3] = {-1, -1, -1};
38
                for(int k = 0; k < 3; k++){
39
                    int x = i + dx[k], y = j + dy[k];
40
                    if(x >= 1 && x <= n && y >= 1 && y <= n && (g[x][y] == '.' || f[x + 1][y] == 0)){
41
                        st[x][y] = 1;
42
                        f[x][y] = f[x + 1][y];
43
                    }
44
                }
45
            }
46
        }
47
    }
48
    for(int j = 1; j <= n; j++)
49
    {
50
        if(st[1][j] == 1) cout << "1" ;
51
        else cout << "0" ;
52
    }
53
    cout << endl;
54
}
55

56
void init(){
57
    for(int i = 1; i <= n; i++){
58
        for(int j = 1; j <= n; j++){
59
            f[i][j] = 0;
60
            st[i][j] = 0;
61
        }
62
    }
63
}
64

65
void solve(){
66
    cin >> n >> m;
67

68
    init();
69

70
    for(int i = 1; i <= n; i++)
71
        for(int j = 1; j <= n; j++)
72
            cin >> g[i][j];
73

74
    bfs();
75
}
76

77
signed main(){
78
    IOS;
79
    int _ = 1;
80
    cin >> _;
81
    while(_--){
82
        solve();
83
    }
84
}

F: Non-Increasing Number#

题目大意：#

让你找出最小的数字 m ,满足 m 是 n 的倍数且m的十进制位数前面小于等于后面
- 例如: 11223359 属于好数字
- 21 -> 126

题目理解：#

本题入手比较麻烦：若是想不到用bfs 暴力查找则很难找到答案。
需要对取模有一定理解:
- (A + B) % C == A % C + B % C;
- 由此我们可以得出，其实就是对一个数不断取模，再加一个数使得该数能够被整除
- 比如 (A + B) % C = D -> (D + E) % C = F … 直到等于 0 （或者没有答案)
- 只需要从第一位开始查找，遍历所有位上的数字即可（同时满足 $a_i\leq a_{i+1}$ )
如果通过bfs 找到过该数字则说明当前数字没有答案

代码:#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define int long long
5
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
6
const int N = 3e7 + 10;
7

8
int n, m;
9
int mp[N];
10

11
void solve()
12
{
13
    cin >> n;
14
    queue<int> q;
15
    // 枚举第一位的数字
16
    for (int d = 1; d <= 9; d++)
17
    {
18
        int r = d % n;
19
        int id = r * 10 + d; // 要存储的二位数字
20
        if (!mp[id])
21
        {
22
            mp[id] = -1;
23
            if (r == 0)
24
            {
25
                cout << d << endl;
26
                return;
27
            }
28
            q.push(id);
29
        }
30
    }
31

32
    int flag = 0; // 表示当前找不到
33
    while (!q.empty())
34
    {
35
        int u = q.front();
36
        q.pop();
37
        int d = u % 10; // 余数
38
        int r = u / 10; // 改变第个位的数
39
        for (int i = d; i <= 9; i++)
40
        {
41
            int nr = (r * 10 + i) % n; //不断模拟取余的过程 直到找到余数为0
42
            int nid = nr * 10 + i;
43
            if(!mp[nid]){
44
                mp[nid] = u;
45
                if(nr == 0){
46
                    flag = nid;
47
                    break;
48
                }
49
                q.push(nid);
50
            }
51

52
        }
53
        if(flag) break;
54
    }
55

56
    if(!flag){
57
        cout << -1 << endl;
58
        return;
59
    }
60

61
    //回溯数字 ，每次只取最后一位
62
    vector<int> ans;
63
    int cur = flag;
64
    while(cur != -1){
65
        ans.push_back(cur % 10);
66
        cur = mp[cur];
67
    }
68
    reverse(ans.begin(), ans.end()); //反转 ，ans最开始得到的是从后往前的数字
69
    for(int i = 0; i < ans.size(); i++)
70
        cout << ans[i];
71
    cout << endl;
72
}
73

74
signed main()
75
{
76
    IOS;
77
    int _ = 1;
78
    // cin >> _;
79
    while (_--)
80
    {
81
        solve();
82
    }
83
}

注意点：#

我采取的方法是，不断取余，用 余数 * 10 + i 成为新的值
如果 $mp[nid]==1$ 表示已经查找过了，说明这种情况没有答案
由于我们是通过添加最后一位，让当前值能够被整除，因此，所得到的ans是反向的，即从最小到最大。
反转 ans 就是我们的答案

AtCoder Beginner Contest 443

https://blog.rookiesama.space/posts/atcoder/atcoder-beginner-contest-443/

作者

Rookiesama

发布于

2026-02-01

许可协议

CC BY

部分信息可能已经过时

P1266 速度限制

Shortest Statement Ever

素晴らしき日々

C Addiction#

题目大意：#

思路：#

易错点：#

D: Pawn Line#

题目大意:#

理解：#

代码:#

E Silver#

题目大意:#

理解:#

代码：#

F: Non-Increasing Number#

题目大意：#

题目理解：#

代码:#

注意点：#