发表更新算法9 分钟读完 (大约1308个字)

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)【A - G】

学到很多……

比赛链接：https://atcoder.jp/contests/abc300/tasks

A - N-choice question

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

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

    int n, a, b;
    cin >> n >> a >> b;

    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;

        if (c == a + b) {
            cout << i + 1 << "\n";
            return 0;
        }
    }

    return 0;
}

B - Same Map in the RPG World

题解

枚举 s,ts, t 的值。

代码

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

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

    int h, w;
    cin >> h >> w;

    vector a(h, vector<char>(w)), b(h, vector<char>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> b[i][j];
        }
    }

    auto cal = [&](int s, int t) {
        auto c = a;
        for (int loop = 0; loop < s; loop++) {
            auto d = c;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    d[i][j] = c[(i + 1) % h][j];
                }
            }
            c = d;
        }
        for (int loop = 0; loop < t; loop++) {
            auto d = c;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    d[i][j] = c[i][(j + 1) % w];
                }
            }
            c = d;
        }
        return c;
    };

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (cal(i, j) == b) {
                cout << "Yes" << "\n";
                return 0;
            }
        }
    }

    cout << "No" << "\n";
    return 0;
}

C - Cross

题解

模拟。

代码

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;

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

    int h, w;
    cin >> h >> w;

    vector<string> MP(h);
    for (int i = 0; i < h; i++) {
        cin >> MP[i];
    }

    vector<int> ans(min(h, w));
    auto legal = [&](int x, int y) {
        return 0 <= x and x < h and 0 <= y and y < w and MP[x][y] == '#';
    };
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            int sz = 0;
            while (legal(i - sz, j - sz) and legal(i - sz, j + sz) and legal(i + sz, j - sz) and legal(i + sz, j + sz)) {
                sz += 1;
            }
            if (sz >= 2) {
                ans[sz - 2] += 1;
            }
        }
    }
    for (int i = 0; i < min(h, w); i++) {
        cout << ans[i] << " \n"[i == min(h, w) - 1];
    }

    return 0;
}

D - AABCC

题解

枚举 a,ba, b 的值。

代码

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;

constexpr int N = 1e6 + 10;

vector<bool> is_prime(N, true);
vector<long long> primes;

void Init() {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < N; i++) {
        if (not is_prime[i]) {
            continue;
        }
        primes.push_back(i);
        for (int j = 2 * i; j < N; j += i) {
            is_prime[j] = false;
        }
    }
}

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

    long long N;
    cin >> N;

    Init();

    int n = primes.size();

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (primes[i] >= 252) {
            break;
        }
        for (int j = i + 1; j < n; j++) {
            if (primes[j] >= 10000) {
                break;
            }
            int k = upper_bound(primes.begin(), primes.end(), sqrt(N / primes[i] / primes[i] / primes[j])) - primes.begin() - 1;
            if (k <= j or primes[i] * primes[i] * primes[j] * primes[k] * primes[k] > N) {
                continue;
            }
            ans += k - j;
        }
    }
    cout << ans << "\n";

    return 0;
}

E - Dice Product 3

题解

设 dp[n]dp[n] 为得到 nn 的概率，则有：

dp[n]=16(dp[n]+dp[n2]+dp[n3]+dp[n4]+dp[n5]+dp[n6])dp[n] = \frac{1}{6}(dp[n] + dp[\frac{n}{2}] + dp[\frac{n}{3}] + dp[\frac{n}{4}] + dp[\frac{n}{5}] + dp[\frac{n}{6}])

化简得：

dp[n]=15(dp[n2]+dp[n3]+dp[n4]+dp[n5]+dp[n6])dp[n] = \frac{1}{5}(dp[\frac{n}{2}] + dp[\frac{n}{3}] + dp[\frac{n}{4}] + dp[\frac{n}{5}] + dp[\frac{n}{6}])

利用记忆化进行搜索。

代码

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;

constexpr int MOD = 998244353;

int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(MOD - x)); }
    Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
    Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
    Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
    Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
    friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
    friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
    friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};

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

    long long n;
    cin >> n;

    map<long long, Z> mp;
    mp[1] = 1;
    function<Z(long long)> dfs = [&](long long cur) {
        if (mp.count(cur)) {
            return mp[cur];
        } else {
            Z res = 0;
            for (int i = 2; i <= 6; i++) {
                if (cur % i == 0) {
                    res += dfs(cur / i);
                }
            }
            return mp[cur] = res / 5;
        }
    };
    cout << dfs(n).val() << "\n";

    return 0;
}

F - More Holidays

题解

observation：一定存在一种最优方案，操作后连续 o 的左端点在前 nn 个字符内。

proof：假设存在一种最优方案不以前 nn 个字符的左端点为起点，则可以操作的每个字符的位置都向左提前 nn 个。

所以在前 nn 个字符内枚举连续 o 的左端点，贪心地操作后面的 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
#include <bits/stdc++.h>
using namespace std;

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

    long long n, m, k;
    cin >> n >> m >> k;

    string s;
    cin >> s;

    vector<int> cnt(n + 1);
    for (int i = 0; i < n; i++) {
        cnt[i + 1] = cnt[i] + (s[i] == 'x');
    }

    vector<int> pos;
    pos.push_back(-1);
    for (int i = 0; i < n; i++) {
        if (s[i] == 'x') {
            pos.push_back(i);
        }
    }

    long long ans = 0;
    auto cal = [&](int i) {
        int id = lower_bound(pos.begin(), pos.end(), i) - pos.begin();
        long long res = i - pos[id - 1] - 1;
        long long suf = cnt[n] - cnt[i];
        long long t_k = k;
        if (t_k < suf) {
            return res + pos[id + t_k] - i;
        } else {
            res += n - i;
            t_k -= suf;
            res += t_k / cnt[n] * n;
            t_k %= cnt[n];
            res += pos[t_k + 1];
            return min(res, n - pos[id - 1] - 1 + (m - 1) * n);
        }
    };
    for (int i = 0; i < n; i++) {
        ans = max(ans, cal(i));
    }
    cout << ans << "\n";

    return 0;
}

G - P-smooth number

题解

枚举，用到了一种被称为 meet in the middle 的搜索技巧，具体可以参考这篇博客。

代码

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

vector<int> minp, primes;

void Init(int n) {
    minp.assign(n + 1, 0);
    primes.clear();

    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

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

    long long n, p;
    cin >> n >> p;

    Init(p);

    vector<long long> a{1}, b{1};
    auto cal = [&](auto& vec, int fac) {
        int sz = vec.size();
        for (int i = 0; i < sz; i++) {
            long long x = vec[i] * fac;
            while (x <= n) {
                vec.push_back(x);
                x *= fac;
            }
        }
    };
    for (auto fac : primes) {
        if (a.size() < b.size()) {
            cal(a, fac);
        } else {
            cal(b, fac);
        }
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    long long ans = 0;
    for (int i = (int)b.size() - 1; auto x : a) {
        while (i >= 0 and x * b[i] > n) {
            i--;
        }
        if (i >= 0) {
            ans += i + 1;
        }
    }
    cout << ans << "\n";

    return 0;

}

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)【A - G】

https://www.kanoon.cn/2023/04/30/ABC-300/

作者

Kanoon

发布于

2023-04-30

更新于

2023-04-30

许可协议

#

评论

最新文章

分类

×