第 378 场 LeetCode 周赛题解

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

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;}
};

同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;elser = mid - 1;}return l != 0 ? l : -1;}
};

二分：首先将 $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;elser = mid - 1;}return l != 0 ? l : -1;}
};

字符串哈希 + 分类讨论：每次查询对应两个区间 $[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、psrfor (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<=e2if (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<=s1if (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;}};
};