2024牛客寒假算法基础集训营3

发表于 2024-02-09 更新于 2024-04-21 分类于题解阅读次数：本文字数： 1.1k 阅读时长 ≈ 4 分钟

To see the world, things dangerous to come to, to see behind walls, to draw closer, to find each other and to feel. That is the purpose of life. — The Secret Life of Walter Mitty

A. 智乃与瞩目狸猫、幸运水母、月宫龙虾

思路：

看题要仔细，就只用判断两个字符串的首尾即可，起初自己写成了整个字符串qwq

时间复杂度：

void solve() {
    std::string a, b;
    std::cin >> a >> b;

    char x = std::tolower(a[0]), y = std::tolower(b[0]);
    if (x != y) {
        std::cout << "No\n";
        return ;
    }
    std::cout << "Yes\n";
}

B. 智乃的数字手串

思路：

妥妥的诈骗题，只用判断N的奇偶性即可，关于本题的证明可以看看官方讲解

时间复杂度：

void solve() {
    int N;
    std::cin >> N;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }
    if (N & 1) {
        std::cout << "qcjj\n";
    } else {
        std::cout << "zn\n";
    }
}

C. 智乃的前缀、后缀、回文

思路：

用字符串hash，我们可以把字符串S, T的正序和逆序都做一遍hash，然后首先判断回文，然后判断是否相等
- 如果S字符串的正序[1, i]和S字符串的逆序[n-i+1, n]的hash值相同，那么他们就是回文字符串，同理，T串也是如此
- 如果S字符串的正序[1, i]和T字符串的逆序[1, i]的hash值相等，那么他们就是相等的，然后我们用数组记录当前的最大长度，T串也是如此
最后我们取一遍max即可

时间复杂度：

struct Shash{
    const i64 base[2] = {29, 31};
    const i64 hashmod[2] = {(i64)1e9, 998244353};

    std::array<std::vector<i64>, 2> hsh, pwMod;
    void init(std::string &s) {
        int n = s.size(); 
        s = ' ' + s;
        hsh[0].resize(n + 1), hsh[1].resize(n + 1);
        pwMod[0].resize(n + 1), pwMod[1].resize(n + 1);
        for(int i = 0; i < 2; i++){
            pwMod[i][0] = 1;
            for(int j = 1; j <= n; j++){
                pwMod[i][j] = pwMod[i][j - 1] * base[i] % hashmod[i];
                hsh[i][j] = (hsh[i][j - 1] * base[i] + s[j]) % hashmod[i];
            }
        }
    }
    std::pair<i64, i64> get(int l, int r) {
        std::pair<i64, i64> ans;
        ans.first = (hsh[0][r] - hsh[0][l - 1] * pwMod[0][r - l + 1]) % hashmod[0];
        ans.second = (hsh[1][r] - hsh[1][l - 1] * pwMod[1][r - l + 1]) % hashmod[1];
        ans.first = (ans.first + hashmod[0]) % hashmod[0];
        ans.second = (ans.second + hashmod[1]) % hashmod[1];
        return ans;
    }
    bool same(int la, int ra, int lb, int rb){
        return get(la, ra) == get(lb, rb);
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M;
    std::cin >> N >> M;

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

    s = std::string(S.rbegin(), S.rend());
    t = std::string(T.rbegin(), T.rend());

    Shash a, b, c, d;
    a.init(S), b.init(T);
    c.init(s), d.init(t);

    int mn = std::min(N, M);
    std::vector<int> p(N + 1), n(M + 1);

    for (int i = 1; i <= mn; i++) {
        auto l1 = a.get(1, i);
        auto l2 = c.get(N - i + 1, N);
        auto r1 = d.get(1, i);
        if (l1 == l2 && r1 == l1) p[i] = i;
        p[i] = std::max(p[i], p[i - 1]);
    }

    for (int i = 1; i <= mn; i++) {
        auto l1 = b.get(1, i);
        auto l2 = d.get(M - i + 1, M);
        auto r1 = c.get(1, i);
        if (l1 == l2 && r1 == l1) n[i] = i;
        n[i] = std::max(n[i], n[i - 1]);
    }

    int ans = -1;
    if (N <= M) {
        for (int i = 1; i <= N; i++) {
            if (p[i] && n[N - i]) {
                ans = std::max(ans, 2 * (p[i] + n[N - i]));
            }
        }
    } else {
        for (int i = 1; i <= M; i++) {
            if (p[M - i] && n[i]) {
                ans = std::max(ans, 2 * (n[i] + p[M - i]));
            }
        }
    }
    std::cout << ans << "\n";

    return 0;
}

D. chino's bubble sort and maximum subarray sum(easy version)

思路：

只能取两个数，所以我们只需要求，当大于时，就暴力交换两个数然后继续做一遍这个操作

时间复杂度：

constexpr i64 inf = 1LL << 60;

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

    int N, K;
    std::cin >> N >> K;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    i64 ans = -inf;
    auto get = [&]() {
        i64 mn = 0, sum = 0;
        for (int i = 0; i < N; i++) {
            sum += a[i];
            ans = std::max(ans, sum - mn);
            mn = std::min(mn, sum);
        }
    };
    get();
    if (K) {
        for (int i = 0; i + 1 < N; i++) {
            std::swap(a[i], a[i + 1]);
            get();
            std::swap(a[i], a[i + 1]);
        }
    }

    std::cout << ans << "\n";

    return 0;
}

GH. 智乃的比较函数

思路：

直接暴力模拟所有情况，只要出现至少一种合理的情况，就代表合法

时间复杂度：

std::vector<std::array<int, 3>> cmp;
void solve() {
    int N;
    std::cin >> N;

    int n = cmp.size();
    std::vector<int> f(n, 1);

    for (int i = 0; i < N; i++) {
        int x, y, z;
        std::cin >> x >> y >> z;
        for (int i = 0; i < f.size(); i++) {
            if ((cmp[i][x - 1] < cmp[i][y - 1]) != z) {
                f[i] = 0;
            }
        }
    }
    std::cout << (*max_element(f.begin(), f.end()) ? "Yes\n" : "No\n");
}

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

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                cmp.push_back({i, j, k});
            }
        }
    }

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }   
        
    return 0;
}

LM. 智乃的36倍数(Easy and normal version)

思路：