AtCoder Beginner Contest 300-有解無憂

A - N-choice question (abc300 a)

題目大意

給定一個元素互不相同的陣列\(c\)和 \(a,b\)，找到 \(i\)使得 \(c_i = a + b\)

解題思路

直接for回圈尋找即可，

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    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 (abc300 b)

題目大意

給定兩個矩陣\(A,B\)，問能否對 \(A\)進行若干次變換操作得到 \(B\)，

變換分兩種，一種是將第一列放到最后一列，另一種是將第一行放到最后一行，

解題思路

范圍不大，直接列舉所有變換操作判斷即可，

如果我們將左右連通，上下連通，那么變換操作實際上不改變每個點的上下左右點，即變換操作可以看成將矩形左上角的點移動，

時間復雜度為\(O(H^2W^2)\)

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> a(h), b(h);
    for(auto &i : a){
        cin >> i;
    }
    for(auto &i : b){
        cin >> i;
    }
    auto equal = [&](int x, int y){
        for(int i = 0; i < h; ++ i)
            for(int j = 0; j < w; ++ j){
                int X = (x + i) % h;
                int Y = (y + j) % w;
                if (a[X][Y] != b[i][j]){
                    return false;
                }
            }
        return true;
    };
    auto check = [&](){
        for(int i = 0; i < h; ++ i)
            for(int j = 0; j < w; ++ j)
                if (equal(i, j))
                    return true;
        return false;
    };
    if (check()){
        cout << "Yes" << '\n';
    }
    else 
        cout << "No" << '\n';
    return 0;
}

C - Cross (abc300 c)

題目大意

給定一個包含.#的矩形，問由#組成的形如X的最長長度，每個長度的數量，

解題思路

范圍不大，列舉X的位置和大小判斷即可，

時間復雜度為\(O(HW\min(HW))\)

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for(auto &i : s)
        cin >> i;
    int sz = min(h, w);
    vector<int> ans(sz + 1);
    auto check = [&](int x, int y){
        if (s[x][y] != '#')
            return 0;
        for(int i = 0; i <= sz; ++ i){
            for(int dx = -1; dx <= 1; dx += 2)
                for(int dy = -1; dy <= 1; dy += 2){
                    int nx = x + i * dx, ny = y + i * dy;
                    if (nx >= h || nx < 0 || ny < 0 || ny >= w)
                        return i - 1;
                    if (s[nx][ny] != '#')
                        return i - 1;
                }
        }
        return sz;
    };
    for(int i = 0; i < h; ++ i)
        for(int j = 0; j < w; ++ j)
            ans[check(i, j)] ++;
    for(int i = 1; i <= sz; ++ i)
        cout << ans[i] << " \n"[i == sz];

    return 0;
}

D - AABCC (abc300 d)

題目大意

問\(1 \sim n\)中能表示成 \(a^2 \times b \times c^2(a < b < c)\)且 \(a,b,c\)為質數的數的個數，

解題思路

由于\(n \leq 10^{12}\)，預處理\(1 \to 10^6\)的質數，然后列舉\(c\)和 \(a\)，計算得到乘積小于等于 \(n\)的最大的 \(b\)，此時符合條件的數量就是 \(1 \sim b\)中的質數個數，這個事先預處理即可，

時間復雜度是 \(O(\sqrt{n} \log n)\)

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

const LL p_max = 1E6 + 100;
LL pr[p_max], p_sz;
int cnt[p_max];
void get_prime() {
    static bool vis[p_max];
    FOR (i, 2, p_max) {
        if (!vis[i]) {
            pr[p_sz++] = i;
            cnt[i] = 1;
        }
        FOR (j, 0, p_sz) {
            if (pr[j] * i >= p_max) break;
            vis[pr[j] * i] = 1;
            if (i % pr[j] == 0) break;
        }
    }
    FOR(i, 2, p_max)
        cnt[i] += cnt[i - 1];
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    LL n;
    cin >> n;
    LL ans = 0;
    get_prime();
    for(int i = 0; i < p_sz; ++ i){
        for(int j = 0; j < i; ++ j){
            LL sum = 1ll * pr[i] * pr[i] * pr[j] * pr[j];
            if (sum > n)
                break;
            LL maxb = min(n / sum, pr[i] - 1);
            if (maxb <= pr[j])
                break;
            ans += cnt[maxb] - cnt[pr[j]];
        }
    }
    cout << ans << '\n';

    return 0;
}

E - Dice Product 3 (abc300 e)

題目大意

六面骰子，每面等概率出現，

現在不斷擲骰子，直到擲出來的數的乘積大于等于\(N\)，

問恰好為 \(N\)的概率，對 \(998244353\)取模，

解題思路

顯然\(n\)的質因數只能有 \(2,3,5\)，

設\(dp[n]\)表示最終是 \(n\)的概率，根據定義， \(dp[n] = \frac{1}{6}dp[\frac{n}{1}] + \frac{1}{6}dp[\frac{n}{2}] + \frac{1}{6}dp[\frac{n}{3}] + \frac{1}{6}dp[\frac{n}{4}] + \frac{1}{6}dp[\frac{n}{5}] + \frac{1}{6}dp[\frac{n}{6}]\)，即擲出\(n\)的概率，應當是先擲出 \(\frac{n}{1}\) ，然后再以\(\frac{1}{6}\)的概率擲出 \(1\)，或者先擲出 \(\frac{n}{2}\) ，然后再以\(\frac{1}{6}\)的概率擲出 \(2\)，依次類推，

當然，如果不整除就沒有這部分的概率貢獻，

化簡一下就是\(dp[n] = \frac{1}{5}dp[\frac{n}{2}] + \frac{1}{5}dp[\frac{n}{3}] + \frac{1}{5}dp[\frac{n}{4}] + \frac{1}{5}dp[\frac{n}{5}] + \frac{1}{5}dp[\frac{n}{6}]\)

因為每次轉移狀態大小都會除以一個數，所以最終的狀態數量應該不會超過\(O(n \log n)\)，寫個記憶化就可以了，

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

long long qpower(long long a, long long b){
    long long qwq = 1;
    while(b){
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x){
    return qpower(x, mo - 2);
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    LL n, ba;
    cin >> n;
    ba = n;
    int cnt2 = 0, cnt3 = 0, cnt5 = 0;
    while (n % 2 == 0){
        ++ cnt2;
        n /= 2;
    }
    while (n % 3 == 0){
        ++ cnt3;
        n /= 3;
    }
    while (n % 5 == 0){
        ++ cnt5;
        n /= 5;
    }
    if (n != 1)
        cout << 0 << '\n';
    else{
        map<LL, int> cache;
        LL inv5 = inv(5);
        function<LL(LL)> dfs = [&](LL n){
            if (n == 1)
                return 1;
            if (cache.find(n) != cache.end())
                return cache[n];
            LL ans = 0;
            for(int i = 2; i <= 6; ++ i)
                if (n % i == 0){
                    ans = (ans + dfs(n / i));
                    if (ans >= mo)
                        ans -= mo;
                }
            cache[n] = ans * inv5 % mo;
            return cache[n];
        };
        cout << dfs(ba) << '\n';

    }

    return 0;
}

F - More Holidays (abc300 f)

題目大意

給定一個包含xo的字串\(t\)，它由一個長度為\(n\)的串\(s\)重復 \(m\)次拼接得到，要求將恰好 \(k\)個 x變成o，問連續o的最大長度，

解題思路

把x的位置都記錄下來，容易發現我們進行變換的x肯定是一組連續的x，

我們列舉進行變化的第一個x，然后找到之后的第 \(k\)個 x，之間的長度取個最大值即可，

雖然這個x有\(nm = 10^{14}\)個，但由于串是重復拼接得到的，第二部分的串的 x實際上跟第一個串的情況一致（并且不會更優），因此我們只需要列舉第一個串x和第二個串的第一個x（注意這個情況，會利用第一個串最后一個x和第二個串的第一個x之間的o，可能從第一個串的第一個x更優），

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    LL k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    vector<int> pos;
    LL cnt = 0;
    for(int i = 0; i < n; ++ i){
        cnt += (s[i] == 'x');
        if (s[i] == 'x')
            pos.push_back(i);
    }
    LL ans = 0;
    LL la = -1;
    auto solve = [&](int st){
        LL left = pos.size() - st;
        LL minn = min(left, k);
        left = k - minn;
        if (left == 0){
            if (st + k == pos.size()){
                return 1ll * n + pos[0] * (m > 1);
            }else {
                return 1ll * pos[st + k];
            }
        }
        LL shift = left / cnt + 1;
        LL remain = left % cnt;
        if (remain == 0 && shift == m){
            return shift * n;
        }else if (shift > m || shift == m && remain > 0)
            return 0ll;
        else{
            return shift * n + pos[remain];
        }
    };
    for(int i = 0; i < pos.size(); ++ i){
        LL r = solve(i);
        ans = max(ans, r - la - 1);
        la = pos[i];
    }
    if (m > 1){
        m -= 1;
        LL r = solve(0);
        ans = max(ans, n + r - pos.back() - 1);
    }
    cout << ans << '\n';

    return 0;
}

求第\(k\)個 x可能有些情況要討論，官方題解采用的二分法就可以以\(\log\)的代價避免這個討論，

且x的數量和串\(s\)的長度是同一個數量級，我們也可以列舉答案的左端點，然后二分找到恰好包含\(k\)個x的最右端點，長度取個最大值，

神奇的代碼

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL inf = 1e18;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    LL k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    vector<int> sum(n);
    LL cnt = 0;
    for(int i = 0; i < n; ++ i){
        if (s[i] == 'x'){
            sum[i] = 1;
        }
    }
    partial_sum(sum.begin(), sum.end(), sum.begin());
    LL ans = 0;
    LL la = -1;
    auto count = [&](LL pos){
        LL shift = pos / n, remain = pos % n;
        return shift * sum.back() + sum[remain] * (shift != m);
    };
    auto solve = [&](int st){
        LL l = st, r = 1ll * n * m;
        LL down = st == 0 ? 0 : sum[st - 1];
        while(l + 1 < r){
            LL mid = (l + r) >> 1;
            if (count(mid) - down <= k)
                l = mid;
            else 
                r = mid;
        };
        return r;
    };
    for(int i = 0; i < n; ++ i){
        LL r = solve(i);
        ans = max(ans, r - i);
    }
    cout << ans << '\n';

    return 0;
}

G - P-smooth number (abc300 g)

題目大意

<++>

解題思路

<++>

神奇的代碼

Ex - Fibonacci: Revisited (abc300 h)

題目大意

<++>

解題思路

<++>

神奇的代碼

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551515.html

標籤：其他

上一篇：中國剩余定理（CRT）學習筆記

下一篇：返回列表