AtCoder Beginner Contest 185 A~F

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

A - ABC Preparation 签到

取4个数中最小的一个。

Code

1
2
3
4
5
6
7
8
##include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << min(a, min(b, min(c, d))) << endl;
}

B - Smartphone Addiction 模拟

暴力模拟，只要中中途中电量<0，直接输出No。 注意最后一次完成后回家的那一段。

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

struct Node {
    ll A, B;
}t[100005];

void solve() {
    ll n, m, T;
    cin >> n >> m >> T;
    for(int i = 1;i <= m; i++) cin >> t[i].A >> t[i].B;
    ll ans = n;
    for(int i = 1;i <= m; i++) {
        ans -= t[i].A - t[i - 1].B;
        if(ans <= 0) {
            cout << "No" << endl;
            return ;
        }
        ans = (ans + t[i].B - t[i].A > n ? n : ans + t[i].B - t[i].A);
    }
    if(ans > T - t[m].B) cout << "Yes" << endl;
    else cout << "No" << endl;
}

signed main() {
    solve();
}

C - Duodecim Ferra 排列组合

简单推导一波$ans=C_{n-1}^{11}$

注意会爆long long，所以我选择Java大数。

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
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

    public static Scanner in = new Scanner(System.in);
    public static PrintStream out = new PrintStream(System.out);

    public static BigInteger ans = BigInteger.valueOf(1);
    public static int n;

    public static void solve() {
        n = in.nextInt();
        for(int i = n - 11;i <= n - 1; i++) {
            ans = ans.multiply(BigInteger.valueOf(i));
        }
        for(int i = 2;i <= 11; i++) {
            ans = ans.divide(BigInteger.valueOf(i));
        }
        out.println(ans);
    }

    public static void main(String[] args) {
        solve();
    }

}

D - Stamp 思维

找每两个都涂了颜色区间的最小值，然后计算贡献。 注意m=0时直接输出1，因为1次就可以涂完。

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

ll a[200005];

void solve() {
    int n, m; cin >> n >> m;
    for(int i = 1;i <= m; i++) cin >> a[i];
    sort(a + 1, a + m + 1);
    ll k = 0;
    a[0] = 0;
    for(int i = 1;i <= m; i++) {
        if((a[i] - a[i - 1] - 1) > 0) {
            if(k == 0) k = a[i] - a[i - 1] - 1;
            else k = min(k, a[i] - a[i - 1] - 1);
        }
    }
    if(k && n != a[m]) k = min(k, n - a[m]);
    ll ans = 0;
    if(k) {
        for(int i = 1;i <= m; i++) {
            if((a[i] - a[i - 1] - 1) > 0) {
                ans += (int) ceil(1.0 * (a[i] - a[i - 1] - 1) / k);
            }
        }

        if(n != a[m]) ans += (int)ceil(1.0 * (n - a[m]) / k);
    }

    if(m == 0) ans = 1;
    cout << ans << endl;
}

signed main() {
    solve();
}

E - Sequence Matching 线性dp

有两个数组a和b，长度分别为n和m，求解删掉x个数后，a数组和b数组不同数的个数y，输出x+y。 考虑dp，dp[i][j]表示a数组选到了i个，b数组选到了第j个的x+y答案。

所以我们有以下四种状态转移：

  • 选择删掉$a_i$，保留b_j$，$f[i][j] = min(f[i][j], f[i - 1][j] + 1)$
  • 选择保留$a_i$，删掉b_j$，$f[i][j] = min(f[i][j], f[i][j - 1] + 1)$
  • 选择保留$a_i$，保留b_j$，$f[i][j] = min(f[i][j], f[i - 1][j - 1])$
  • 选择删掉$a_i$，保留b_j$，$f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1)$

注意dp数组的初始化。

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define lc u << 1
##define rc u << 1  1
##define mid (t[u].l + t[u].r) / 2
##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 1005;
int f[N][N];

void solve() {
    int n, m; cin >> n >> m;
    vector<int> A(n + 1), B(m + 1);
    for(int i = 1;i <= n; i++) cin >> A[i];
    for(int i = 1;i <= m; i++) cin >> B[i];
    for(int i = 0;i <= n; i++)
        for(int j = 0;j <= m; j++)
            f[i][j] = INF;
    for(int i = 0;i <= n; i++) f[i][0] = i;
    for(int i = 0;i <= m; i++) f[0][i] = i;

    for(int i = 1;i <= n; i++) {
        for(int j = 1;j <= m; j++) {
            if(A[i] == B[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j] + 1);
            f[i][j] = min(f[i][j], f[i][j - 1] + 1);
        }
    }
    cout << f[n][m] << endl;
}

signed main() {
    solve();
}

F - Range Xor Query 线段树

一道单点修改，维护区间异或和的裸线段树。

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
78
79
80
81
82
83
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define lc u << 1
##define rc u << 1  1
##define mid (t[u].l + t[u].r) / 2
##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 3e5 + 10;

int A[N];

struct Node {
    int l, r;
    int sum;
}t[N << 2];

void push_up(int u) {
    t[u].sum = t[lc].sum ^ t[rc].sum;
}

void build(int u, int l, int r) {
    t[u].l = l; t[u].r = r;
    if(l == r) {
        t[u].sum = A[l];
        return ;
    }
    int m = (l + r) >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    push_up(u);
}

void modify(int u, int p, int v) {
    if(t[u].l == t[u].r) {
        t[u].sum = t[u].sum ^ v;
        return ;
    }
    if(p <= mid) modify(lc, p, v);
    else modify(rc, p, v);
    push_up(u);
}

int query(int u, int ql, int qr) {
    if(ql <= t[u].l && t[u].r <= qr) {
        return t[u].sum;
    }
    int ans = 0;
    if(ql <= mid) ans ^= query(lc, ql, qr);
    if(qr > mid)  ans ^= query(rc, ql, qr);
    return ans;
}

void solve() {
    int n, q; cin >> n >> q;
    for(int i = 1;i <= n; i++) {
        cin >> A[i];
    }
    build(1, 1, n);
    while(q--) {
        int opt, x, y; cin >> opt >> x >> y;
        if(opt == 1) modify(1, x, y);
        else cout << query(1, x, y) << endl;
    }
}

signed main() {
    solve();
}

这一场非常友好，我很喜欢。

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