第 378 场 LeetCode 周赛题解

A 检查按位或是否存在尾随零

枚举：枚举两个元素的组合即可

class Solution {
public:
    bool hasTrailingZeros(vector<int> &nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
                if ((nums[i] | nums[j]) % 2 == 0)
                    return true;
        return false;
    }
};

B 找出出现至少三次的最长特殊子字符串 I

同C …

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size();
        vector<vector<int>> li(26);
        for (int i = 0, j = 0; i < n; i = ++j) {
            while (j + 1 < n && s[j + 1] == s[j])
                j++;
            li[s[i] - 'a'].push_back(j - i + 1);
        }
        int l = 0, r = n;
        auto can = [&](int len) {
            for (auto &v: li) {
                int cnt = 0;
                for (auto blk: v)
                    if (blk >= len)
                        cnt += blk - len + 1;
                if (cnt >= 3)
                    return true;
            }
            return false;
        };
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (can(mid))
                l = mid;
            else
                r = mid - 1;
        }
        return l != 0 ? l : -1;
    }
};

C 找出出现至少三次的最长特殊子字符串 II

二分：首先将 $s$ 划分成若干特殊子字符串，然后二分枚举答案，判断当前枚举值是否满足条件

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size();
        vector<vector<int>> li(26);
        for (int i = 0, j = 0; i < n; i = ++j) {
            while (j + 1 < n && s[j + 1] == s[j])
                j++;
            li[s[i] - 'a'].push_back(j - i + 1);
        }
        int l = 0, r = n;
        auto can = [&](int len) {//判断是否存在出现至少三次长为len的特殊子字符串
            for (auto &v: li) {
                int cnt = 0;
                for (auto blk: v)
                    if (blk >= len)
                        cnt += blk - len + 1;
                if (cnt >= 3)
                    return true;
            }
            return false;
        };
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (can(mid))
                l = mid;
            else
                r = mid - 1;
        }
        return l != 0 ? l : -1;
    }
};

D 回文串重新排列查询

字符串哈希 + 分类讨论：每次查询对应两个区间 $[s1,e1]$ 和 $[s2,e2]$ ，两个区间的位置关系可以分为：

• 两个区间不相交
• 两个区间相交
  • 一个区间包含另一个区间
  • 两个区间都不包含另一个区间

class Solution {
public:
    using ll = long long;

    vector<bool> canMakePalindromeQueries(string s, vector<vector<int>> &queries) {
        string sl = s.substr(0, s.size() / 2), sr = s.substr(s.size() / 2, s.size() / 2);
        reverse(sr.begin(), sr.end());//反转s后半段
        srand(time(0));
        ll e_ = 2333 + rand() % 10;
        ll mod_ = 1e9 + rand() % 10;

        shash hl(sl, e_, mod_), hr(sr, e_, mod_);
        int n = sl.size();
        vector<vector<int>> psl(26, vector<int>(n + 1)), psr(26, vector<int>(n + 1));//各个字符出现数目的前缀和

        auto cmp_ps = [&](string &s, vector<vector<int>> &ps) {//计算psl、psr
            for (int i = 0; i < 26; i++)
                ps[i][0] = 0;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < 26; j++)
                    ps[j][i + 1] = s[i] - 'a' == j ? ps[j][i] + 1 : ps[j][i];
        };
        cmp_ps(sl, psl);
        cmp_ps(sr, psr);

        auto eql = [&](int l, int r) {//判断 sl[l,r] 和 sr[l,r] 中各字符数目是否都相等
            for (int i = 0; i < 26; i++)
                if (psl[i][r + 1] - psr[i][l] != psr[i][r + 1] - psr[i][l])
                    return false;
            return true;
        };

        auto ge = [&](int s1, int e1, int s2, int e2) {//判断 sl[s1,e1] 中各字符数目是否都不小于 sr[s2,e2] 中对应字符数目
            for (int i = 0; i < 26; i++)
                if (psl[i][e1 + 1] - psr[i][s1] < psr[i][e2 + 1] - psr[i][s2])
                    return false;
            return true;
        };
        auto le = [&](int s1, int e1, int s2, int e2) {//判断 sl[s1,e1] 中各字符数目是否都不大于 sr[s2,e2] 中对应字符数目
            for (int i = 0; i < 26; i++)
                if (psl[i][e1 + 1] - psr[i][s1] > psr[i][e2 + 1] - psr[i][s2])
                    return false;
            return true;
        };

        vector<bool> res(queries.size(), false);

        for (int ind = 0; ind < queries.size(); ind++) {
            int s1 = queries[ind][0], e1 = queries[ind][1], s2 = n * 2 - 1 - queries[ind][3], e2 = n * 2 - 1 - queries[ind][2];
            if (e1 < s2 || e2 < s1) {//两个区间不相交
                if (e2 < s1) {
                    swap(s1, s2);
                    swap(e1, e2);
                }
                if (s1 != 0 && hl(0, s1 - 1) != hr(0, s1 - 1))
                    continue;
                if (e1 + 1 < s2 && hl(e1 + 1, s2 - 1) != hr(e1 + 1, s2 - 1))
                    continue;
                if (e2 != n - 1 && hl(e2 + 1, n - 1) != hr(e2 + 1, n - 1))
                    continue;
                if (!eql(s1, e1) || !eql(s2, e2))
                    continue;
            } else {//两个区间相交
                if (s1 <= s2 && e1 >= e2) {//[s1,e1] 包含 [s2,e2]
                    if (s1 != 0 && hl(0, s1 - 1) != hr(0, s1 - 1) || e1 != n - 1 && hl(e1 + 1, n - 1) != hr(e1 + 1, n - 1))
                        continue;
                    if (!eql(s1, e1))
                        continue;
                } else if (s2 <= s1 && e2 >= e1) {[s2,e2] 包含 [s1,e1]
                    if (s2 != 0 && hl(0, s2 - 1) != hr(0, s2 - 1) || e2 != n - 1 && hl(e2 + 1, n - 1) != hr(e2 + 1, n - 1))
                        continue;
                    if (!eql(s2, e2))
                        continue;
                } else {//两个区间相交,且任意一个都不包含另一个
                    if (s1 < s2) {// s1<s2<=e1<=e2
                        if (s1 != 0 && hl(0, s1 - 1) != hr(0, s1 - 1) || e2 != n - 1 && hl(e2 + 1, n - 1) != hr(e2 + 1, n - 1))
                            continue;
                        if (!ge(s1, e1, s1, s2 - 1) || !le(e1 + 1, e2, s2, e2) || !eql(s1, e2))
                            continue;
                    } else {//s2<s1<=e2<=s1
                        if (s2 != 0 && hl(0, s2 - 1) != hr(0, s2 - 1) || e1 != n - 1 && hl(e1 + 1, n - 1) != hr(e1 + 1, n - 1))
                            continue;
                        if (!le(s2, s1 - 1, s2, e2) || !ge(s1, e1, e2 + 1, e1) || !eql(s2, e1))
                            continue;
                    }
                }
            }
            res[ind] = true;
        }
        return res;
    }

    class shash {//字符串哈希模板
    public:
        vector<ll> pres;
        vector<ll> epow;
        ll e, p;

        shash(string &s, ll e, ll p) {
            int n = s.size();
            this->e = e;
            this->p = p;
            pres = vector<ll>(n + 1);
            epow = vector<ll>(n + 1);
            epow[0] = 1;
            for (int i = 0; i < n; i++) {
                pres[i + 1] = (pres[i] * e + s[i]) % p;
                epow[i + 1] = (epow[i] * e) % p;
            }
        }

        ll operator()(int l, int r) {
            ll res = (pres[r + 1] - pres[l] * epow[r - l + 1] % p) % p;
            return (res + p) % p;
        }
    };
};