AtCoder Beginner Contest 186 A~F

传送门：https://atcoder.jp/contests/abc186/tasks

A - Brick 签到

1
2
3
4
5
6
7
8
9
10
11
12
##include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m; cin >> n >> m;
    cout << n / m << endl;
}

signed main() {
    solve();
}

B - Blocks on Grid 暴力

先找矩阵最小值mx,最后找$ans=mp[i][j] - mx$

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

using namespace std;

typedef long long ll;

int mp[105][105];

void solve() {
    int mx = 99999999;
    int n, m; cin >> n >> m;
    for(int i = 1;i <= n; i++) {
        for(int j = 1;j <= m; j++) {
            cin >> mp[i][j];
            mx = min(mx, mp[i][j]);
        }
    }
    ll ans = 0;
    for(int i = 1;i <= n; i++) {
        for(int j = 1;j <= m; j++) {
            ans += mp[i][j] - mx;
        }
    }
    cout << ans << endl;
}

signed main() {
    solve();
}

C - Unlucky 7 暴力

分别找十进制下和八进制中不出现7这个数的个数。

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

using namespace std;

typedef long long ll;

void solve() {
    int n; cin >> n;
    ll ans = n;
    for(int i = 7;i <= n; i++) {
        int tt = i;
        bool flag1 = 0;
        while(tt) {
            if(tt % 10 == 7) {
                flag1 = 1;
                break;
            }
            tt /= 10;
        }
        tt = i;
        bool flag2 = 0;
        while(tt) {
            if(tt % 8 == 7) {
                flag2 = 1;
                break;
            }
            tt /= 8;
        }
        if(flag1  flag2) ans--;
    }
    cout << ans << endl;
}

signed main() {
    solve();
}

D - Sum of difference 思维

先排序，在对每个数$a_j-a_i$取贡献。

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

using namespace std;

typedef long long ll;

void solve() {
    int n; cin >> n;
    vector<ll> v(n + 1), sum(n + 1);
    v[0] = -1e9;
    for(int i = 1;i <= n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    ll ans = 0;
    for(int i = 1;i <= n; i++) {
        sum[i] = sum[i - 1] + v[i];
    }
    for(int i = 1;i <= n - 1; i++) {
        ans += (sum[n] - sum[i]) - (n - i) * v[i];
    }
    cout << ans << endl;
}

signed main() {
    solve();
}

E - Throne 扩展欧几里得

求$Kx+Ny=N-S$的最小正整数x，有则输出，无则输出-1。

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

using namespace std;

typedef long long ll;

ll ex_gcd(ll a, ll b, ll &x, ll &y)
{
    ll res, t;
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    res = ex_gcd(b, a % b, x, y);
    t = x;
    x = y;
    y = t - (a / b) * y;
    return res;
}

ll solve_ex_gcd(ll a, ll b, ll c, ll &x, ll &y)
{
    ll d = ex_gcd(a, b, x, y);
    if(c % d)
    {
        x = -1;
        y = -1;
        return -1;
    }
    x *= (c / d);
    b = abs(b / d);
    x %= b;
    while(x < 0) {
        x += b;
    }
    y = (c - a * x) / b;
    return 0;
}

void solve() {
    int _; cin >> _;
    while(_--) {
        ll x, y;
        ll N, S, K; cin >> N >> S >> K;
        solve_ex_gcd(K, N, N - S, x, y);
        cout << x << endl;
    }
}

signed main() {
    solve();
}

F - Rook on Grid 扫描线 + BIT

我们到达一个点，有两种走法，先右在下和先下在右。 但是对于x=1或y=1的情况，有一个障碍堵在中间，那么也是走不到的，所以我们先找最小的x=1是的y和最小的y=1时的x，在把这两个障碍之后的所有格子都设为障碍。 然后记得去重（可能重复添加障碍）。

1
2
3
4
5
6
7
8
9
10
11
12
int upx = H + 1, upy = W + 1;
    for(int i = 1;i <= M; i++) {
        cin >> p[i].x >> p[i].y;
        if(p[i].x == 1) upy = min(upy, p[i].y);
        if(p[i].y == 1) upx = min(upx, p[i].x);
    }
    for(int i = upx + 1;i <= H; i++) {
        p[++M].x = i; p[M].y = 1;
    }
    for(int j = upy + 1;j <= W; j++) {
        p[++M].y = j; p[M].x = 1;
    }

我们怎么找那些去不到的格子呢？ 答：我们利用扫描线的思想，先纵向扫描，在横向搜索，在做ans贡献。

如果一个格子既不能右下走也不能下右走，那么这个格子到达不了。 纵向扫描： 用BIT维护右下路径被堵住的列，将这些格子视为到达不了。

横向搜索： 对于每一行，计算区间和，因为右下到不了，但是下右可能到达，所以我们将这些重新加回来。

Code

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
67
68
69
70
71
72
73
74
75
76
77
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
##define lowbit(x) x & (-x)

const int N = 1e6 + 10;
ll t[N];

void modify(int x, int n) {
    while(x <= n) {
        t[x]++;
        x += lowbit(x);
    }
}

ll query(int x) {
    ll ans = 0;
    while(x) {
        ans += t[x];
        x -= lowbit(x);
    }
    return ans;
}

struct Point {
    int x, y;
    friend bool operator < (const Point &a,const Point &b){
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }
    friend bool operator == (const Point &a,const Point &b){
        return a.x == b.x && a.y == b.y;
    }
}p[N];

bool vis[N];

void solve() {
    int H, W, M;
    cin >> H >> W >> M;
    int upx = H + 1, upy = W + 1;
    for(int i = 1;i <= M; i++) {
        cin >> p[i].x >> p[i].y;
        if(p[i].x == 1) upy = min(upy, p[i].y);
        if(p[i].y == 1) upx = min(upx, p[i].x);
    }
    for(int i = upx + 1;i <= H; i++) {
        p[++M].x = i; p[M].y = 1;
    }
    for(int j = upy + 1;j <= W; j++) {
        p[++M].y = j; p[M].x = 1;
    }
    sort(p + 1, p + M + 1);
    M = unique(p + 1, p + M + 1) - (p + 1);

    int h = 1;
    ll ans = 0;
    for(int i = 1;i <= M; i++) {
        // 纵向扫描
        if(vis[p[i].y] == 0) {
            vis[p[i].y] = 1;
            modify(p[i].y, W);
        }

        // 横向扫描
        if(i == M  p[i + 1].x != p[i].x) {
            ans += query(W) - query(p[h].y - 1);
            h = i + 1;
        }
    }
    cout << (1ll * H * W - ans) << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/21/atcoder-beginner-contest-186-af/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！