题目描述：
给出一个字符串 $s$ ，对 $s$ 的子串进行查询。每次查询 queries[i] = [l, r, k]，可以重新排列子串 s[l], ..., s[r]，并且从中选择最多的 $k$ 项替换成任何小写英文字母。如果子串可以变成回文形式的字符串，那么查询结果为 true，否则结果为 false。
数据范围：
$1\le s.len, q.len \le 10^5$
题解：
使用位运算加前缀和来表示前缀中各个字母个数的奇偶性。可以考虑使用异或，异或是不带进位的加减法。异或加前缀和，可以快速统计待查询的子区间中各个字母数量的奇偶性。如果一个字母为偶数，那么他可以放在子串的两边，如果为奇数，那么就需要进行替换，最中间的不需要替换。假设有 $t$ 个字母的个数为奇数，那么需要被替换的个数为 $(t - 1) / 2$ ，当 $(t - 1) / 2 \le k$ 时返回 true，否则返回 false。
统计数字中 $1$ 的个数：
刚好可以使用 $x \& x - 1$ 将 $x$ 末尾的 $1$ 变成 $0$ ，因此只需要看 $x$ 能够进行几次该操作就好。
另外一个用处就是判断一个数是不是 $2^i$ ，如果 $x \& x - 1 = 0$ 则该数必是 $2 ^ i$ ，否则不是。
$x \& -x$ ：
树状数组中常用的，用来得到 $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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 1;
int sum[maxn] = {};
vector<bool> canMakePaliQueries(string& s, vector<vector<int>> &queries)
{
int n = s.size();
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] ^ (1 << (s[i - 1] - 'a'));
}
int l, r, k, tot;
vector<bool> ans(queries.size(), false);
for (int j = 0; j < queries.size(); ++j)
{
auto &q = queries[j];
l = q[0] + 1, r = q[1] + 1, k = q[2];
int cnt = 0;
tot = sum[r] ^ sum[l - 1];
while(tot)
{
tot &= tot - 1;
++cnt;
}
if (cnt <= k * 2 + 1)
ans[j] = true;
}
return ans;
}
};
|