Atcoder ABC280

A. Pawn on a Grid

统计##个数。

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
/**
 *    author:  jujimeizuo
 *    created: 2022-12-03 20:00:15
**/
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        cnt += std::count(s.begin(), s.end(), '##');
    }

    std::cout << cnt << '\n';

    return 0;
}

B. Inverse Prefix Sum

模拟。

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
/**
 *    author:  jujimeizuo
 *    created: 2022-12-03 20:01:17
**/
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        if (i > 0) std::cout << a[i] - a[i - 1] << " ";
        else std::cout << a[i] << ' ';
    }
    return 0;
}

C. Extra Character

找到第一个不相等字符位置。

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
/**
 *    author:  jujimeizuo
 *    created: 2022-12-03 20:03:26
**/
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string s, t;
    std::cin >> s >> t;

    int p = 0;
    while (p < (int) s.size() && s[p] == t[p]) {
        p++;
    }

    std::cout << p + 1 << '\n';

    return 0;
}

D. Factorial and Multiple

题意

找到最小的n是的n!是k的倍数。

思路

n!的因子p个数为n / p + n / p / p + ... 质因数分解K，对于K的一个质因子p，个数为cnt，二分求出最小的x，使得x的p个数大于等于cnt。 ans = std::max(ans, x)

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
/**
 *    author:  jujimeizuo
 *    created: 2022-12-03 20:05:06
**/
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long K;
    std::cin >> K;

    long long ans = 1;

    auto check = [&](long long x, long long i, long long c) -> bool {
        long long cnt = 0;
        while (x) {
            cnt += x / i;
            x /= i;
        }
        return cnt >= c;
    };

    for (long long i = 2; i * i <= K; i++) {
        int cnt = 0;
        while (K % i == 0) cnt++, K /= i;
        if (cnt == 0) continue ;
        long long l = l, r = 1E12;
        long long x = -1;
        while (l <= r) {
            long long mid = (l + r) / 2;
            if (check(mid, i, cnt)) {
                x = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        ans = std::max(ans, x);
    }
    if (K > 1) {
        ans = std::max(ans, K);
    }
    std::cout << ans << '\n';
    return 0;
}

E. Critical Hit

题意

一只怪物有n滴血，攻击一滴血的概率为p/100 (p1),攻击两滴血的概率为1 - (100 / p) (p2)，求打死怪物的攻击期望。

思路

设dp[i]表示攻击i滴血的攻击期望，则转移方程为 dp[i] = dp[i - 1] * p1 + dp[i - 2] * P2 + 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
/**
 *    author:  jujimeizuo
 *    created: 2022-12-03 21:18:42
**/
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, p;
    std::cin >> n >> p;

    Mint inv100 = power(Mint(100), md - 2);
    Mint p2 = inv100 * p, p1 = inv100 * (100 - p);

    std::vector<Mint> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] * p1 + dp[std::max(0, i - 2)] * p2 + 1;
    }

    std::cout << dp[n] << '\n';

    return 0;

}

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