Anagram Search
题意简述
两个字符串 \(s\) 和 \(t\) 相似的定义为：\(s\) 可以打乱之后重新排列成为 \(t\)。题目给出\(a\) 和 \(b\)，问 \(a\) 中有多少子串(连续的一段)与 \(b\) 相似。
同时，\(a\) 中还含有 \(?\) 字符，他可以等价于任何字符（可以变成任何字符）
解题思路
实际上，根据题目对于相似的定义，我们可以知道，对于任意字符串\(s\)和\(t\)，只要满足长度相等，且组成的字母对应的个数相同，就可以认为他们相似3
因此，我们可以使用一个特殊技巧: 滑动窗口。对于字符串 \(a\) ,我们每次维护一个长度为 \(len(b)\) 的窗口，每次一个一个单位地移动窗口，每移动一次就统计窗口中字母的个数，并与 \(b\) 中的字母个数进行比较，如果相同，则说明窗口中的子串与 \(b\) 相似。
关于比较：首先，我们可以预处理出 \(b\) 中每个字母出现的次数，用 \(cnt\) 来记录 \(b\) 中出现的字母个数。然后，同样使用数组 \(cnt_a\) 来记录窗口中字母出现的次数。但是，由于 \(a\) 中 \(?\) 的存在，我们每次比较 \(cnt\) 和 \(cnt_a\) 的时候，由于窗口长度和\(b\) 长度相同，所以只需要满足 $ {\forall}cnt_a[i] <= cnt[i]$，二者即相似，因为 \(?\) 可以等价于任何字符，\(cnt_a\)少于\(cnt\)的部分就是 \(?\) 的数量。
复杂度分析
预处理 \(b\) 中每个字母出现的次数，时间复杂度为 \(O(n)\)，其中 \(n\) 为 \(b\) 的长度。
滑动窗口，时间复杂度为 \(O(n)\)，其中 \(n\) 为 \(a\) 的长度。
每次比较，由于循环次数为常数26,时间复杂度为 \(O(1)\)。
因此，总时间复杂度为 \(O(n)\)。
AC代码
void solve()
{
string s, t;
cin >> s >> t;
vector<int> cnt(26), vcnt(26); //cnt记录b中字母个数，vcnt记录窗口中字母个数
int ans = 0;
for (auto i : t) //预处理字符串t
{
cnt[i - 'a']++;
}
for (int i = 0; i < s.size(); i++)
{
if (s[i] != '?') //向右移动一个单位，加入右边的新字符
vcnt[s[i] - 'a']++;
if (i >= t.size() && s[i - t.size()] != '?') //同时弹出最左边的一个字符
vcnt[s[i - t.size()] - 'a']--;
if (i >= t.size() - 1)
//当窗口长度为t的长度时，开始判断窗口中的子串是否与t相似
{
bool ok = 1;
for (int i = 0; i < 26; i++)
{
if (vcnt[i] > cnt[i]) //如果窗口内某个字母的个数大于b中该字母的个数，则二者不相似
{
ok = 0;
break;
}
}
ans += ok;
}
}
cout << ans << endl;
}
Exposition
题目简述
给一个 \(n\) 个元素的序列，从中挑出最长的子串，要求子串中元素差的最大值不超过 \(k\)
思路分析
既然要求任意两个数之差不超过 \(k\) 的最长子串，实际上是求最大极差，考虑暴力的做法，那么我们可以考虑枚举子串的起点，从 \(1 ～ n\) 的每一个点开始，利用双指针维护一个子串，一个指针指向起点，另一个从起点开始向后枚举，维护双指针所覆盖区间的极差，直到遇到一个极差大于 \(k\) 的点，此时记录当前子串的长度，并更新答案，然后继续枚举下一个起点，直到枚举完所有起点。
暴力做法，每一次从一个点开始向后枚举，复杂度为 \(O(n)\)，序列一共有 \(n\) 个点，所以总的时间复杂度为 \(O(n^2)\)。而此题数据范围为 \(n ≤ 10^5\)，而 \(n^2 = 1^10\)，所以暴力做法会超时。
以此为思路，我们考虑暴力法中有那些步骤可以优化，我们发现，枚举 \(n\) 个起点似乎已经无法优化了，而每一次从该起点向后枚举，维护双指针所覆盖区间的极差，似乎可以优化。
首先，由于我们起点确定，记为 \(a_{st}\)，需要维护的是终点，假设存在 \(a_i\)，使得 \(a_i - {\forall}a_{st～i} \geq k\)，那么对于 \(a_i\) 以及之后的数，我们一定不会将他们选进子串中，由此我们可以发现，我们维护的极差具有单调性！同时，求小于 \(k\) 的最大极差，同时又有单调性，那不就可以采用二分搜索了吗？那么我们每次枚举的复杂度就降到了 \(O(\log_2 n)\)，但是，枚举的时间复杂度降低了，我们还有一个问题，如何快速求出每次询问区间的极差？这就得请我们的区间操作神器--线段树登场了！，我们可以对原序列建立线段树，维护区间极差，这样每次时间复杂度就降到了 \(O(\log_2 n)\)，总的时间复杂度就降到了 \(O(n\log_2 n)\)，而 \(n ≤ 10^5\)，所以总的时间复杂度为 \(O(n\log_2 n)\)，可以接受。
时间复杂度分析
在原序列上建立线段树，复杂度为 \(O(n)\)。
枚举 \(n\) 个起点，复杂度为 \(O(n)\)。
对于每次枚举的起点，我们用二分搜索，会产生 \(O(\log_2 n)\) 次询问，而线段树上每次查询时间复杂度为 \(O(\log_2 n)\)，因此枚举枚举的总复杂度为 \(O(\log_2 n)^2\)。
因此总的时间复杂度为 \(O(n\log_2 n)\)。
AC代码
vector<int> a;
struct node //线段树节点
{
int l, r, max, min;
} tr[N << 2]; //线段树需要4倍的空间
void update(int u) //从子节点更新当前节点
{
tr[u].max = max(tr[u << 1].max, tr[u << 1 | 1].max);
tr[u].min = min(tr[u << 1].min, tr[u << 1 | 1].min);
}
void build(int u, int l, int r) //建立线段树
{
tr[u] = {l, r, a[r], a[r]};
if (l == r)
return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
update(u);
}
node query(int u, int l, int r) //区间查询
{
if (l <= tr[u].l && tr[u].r <= r)
return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid)
return query(u << 1, l, r);
else if (l > mid)
return query(u << 1 | 1, l, r);
else
{
auto L = query(u << 1, l, r), R = query(u << 1 | 1, l, r);
node res;
res.max = max(L.max, R.max);
res.min = min(L.min, R.min);
return res;
}
}
int query(int l, int r) //区间查询
{
auto p = query(1, l, r);
return p.max - p.min; //返回极值
}
void solve()
{
IOS;
int n, k;
cin >> n >> k;
a.resize(n + 1);
rep(i, 1, n + 1) cin >> a[i];
build(1, 1, n); //建立线段树
int len = 0, cnt = 0;
vector<pii> st;
rep(i, 1, n + 1)
{
int l = i, r = n;
while (l < r) //二分查找
{
int mid = l + r + 1 >> 1;
if (query(i, mid) <= k)
l = mid;
else
r = mid - 1;
}
if (r - i + 1 > len) //如果找到了一个更长的子串
{
len = r - i + 1, cnt = 1; //更新答案
st.clear(); //舍弃之前所有较短的子串
st.push_back({i, r}); //存入答案
}
else if (r - i + 1 == len) //如果找到一个等于最长串的子串，把他存入
cnt++, st.push_back({i, r});
}
cout << len << " " << cnt << endl; //输出答案
for (auto [l, r] : st)
cout << l << " " << r << endl;
}
Music in Car
题意简述
给定两个长度为 \(n\) 的序列，其中 \(a_i\) 表示第 \(i\) 个元素的贡献，\(b_i\) 表示获得第 \(i\) 个元素的代价。
同时，给出 \(n,w,k\) 分别代表序列长度，操作次数以及最大代价，对于每次操作，你可以任意挑选一个位置 \(i\),让他的代价 \(b_i\) 变成 \(\lceil \frac{b_i}{2} \rceil\)。
你可以选定任意一段从 \(i\) 开始，\(j\) 结束的序列，满足\(\sum b_{i～j} \leq k\)，并得到 \(\sum a_{i～j}\) 的贡献。
求出最大贡献。
思路分析
对于任意一个区间，我们拥有 \(w\) 次操作机会，根据贪心的思想，我们每次选择代价最大的位置进行操作，这样我们就一定可以得到最大的贡献。
因此，类似于滑动窗口的思想，我们可以枚举区间右端点 \(r\)，让指针 \(r\) 向右一直前进，同时维护一个左端点指针\(l\),每次移动完 \(r\) 后，我们就检查是否有 \(\sum b_{l～r} > k\) ，若出现这种情况，则不断向前移动左指针 \(l\)，并不断删除最左边的数，直到 \(\sum b_{l～r} \leq k\)，这样我们就可以维护一个区间，满足条件，每次完成上述操作后更新答案。
对于 \(w\) 次操作，我们每次选择代价前 \(w\) 大的位置进行操作(打折)，而求前 \(w\) 大正好可以采用平衡树来维护，这里并不需要我们手写平衡树，cpp的STL中就自带了一个红黑树multiset，利用muiltset,我们可以很轻松地维护数之间的大小关系。
tip: muiltset存储数据天然有序，muiltset的最前面的元素一定是最小的元素，最后面的一定是最大的元素
在区间扫描的过程中，我们可以使用两个平衡树来维护打折区间 \(L\) 以及原价区间 \(H\)，右端点每次扫过一个数，我们可以进行如下操作
- 首先，将新的数的代价\(b_i\)加入到\(L\)中，总贡献加上\(a_i\)，总代价加上\(\lceil \frac{b_i}{2} \rceil\)
- 如果\(L\)中的数超过了 \(w\) 个，那么我们删除\(L\)中代价最小的数(即\(L_1\))，总代价减去\(\lceil \frac{L_1}{2} \rceil\)，并加上\(L_1\)，同时将弹出来的数加入到\(H\)中
- 检查总代价 \(p\) 是否超过了 \(k\)，若超过，则应该移除 \(l\) 指针的数，并将其向左移动一个单位
关于弹出 \(l\) 指针对应的数:首先，我们应该检查\(b_i\)是否存在于打折区间 \(L\) 中(即比较\(L_1\) 和 \(b_i\) 的大小，由于我们打着区间中存放的是前 \(w\) 大的数，若\(b_l\)大于打着区间中最小的数(\(b_l \geq L_1\)),则\(b_l\)一定存在于打折区间中)，我们从\(L\)中删除\(b_i\)，同时总贡献减掉 \(\lceil \frac{b_l}{2} \rceil\)，删除 \(b_l\) 后，打折区间多出一个空位，我们让原价区间中最大的数( \(H_{H.size()-1}\) )加入到打折区间中，总代价减掉 \(b_{H_{H.size()-1}}\) 并加上 \(\lceil \frac{b_{H_{H.size()-1}}}{2} \rceil\)。如果 \(b_l\) 不存在于打折区间，那么我们直接从原价区间中删掉 \(b_i\) 并将贡献减去 \(b_l\) 即可。最后将总贡献减掉 \(a_l\)。重复上述步骤，不断左移动 \(l\) 指针，直到总代价不超过 \(k\) 为止。
- 更新答案
时间复杂度分析
枚举右端点 \(r\),复杂度为 \(O(n)\)
维护左端点 \(l\)，每次移动 \(l\) 指针，复杂度为 \(O(n)\)
红黑树维护打折区间 \(L\) 和原价区间 \(H\)，每次插入一个数，删除一个数，复杂度为 \(O(\log n)\)
总时间复杂度为 \(O(n^2 \log n)\)
AC代码
void solve()
{
int n,w,k;
cin >> n >> w >> k;
vector<int> a(n+1),b(n+1);
rep(i, 1, n + 1) cin >> a[i];
rep(i, 1, n + 1) cin >> b[i];
int l = 1, p = 0, all = 0 ,ans = 0; //p为当前区间总代价，all为总贡献
multiset<int> H,L; //H存原时长，L存折半
for(int i = 1; i<= n; i++)
{
L.insert(b[i]); //将新的数加入打折区间
p += b[i]+1>>1; //累加贡献和代价
all += a[i];
if(L.size()>w) //如果打折区间超过w个数，弹出代价最小的数
{
H.insert(*L.begin()); //并将他加入到原价区间中
p += *L.begin(); //处理代价
p -= (*L.begin()+1) >> 1;
L.erase(L.begin()); //弹出
}
while(p > k) //如果当前区间的总代价p超过k，则需要弹出左端点
{
if(b[l] >= *L.begin()) //如果左端点对应的代价在打折区间内
{
p -= (b[l]+1)>>1; //处理代价
L.erase(L.find(b[l])); //从打折区间删除
if(H.size()) //如果原价区间中有数，则把其中最大的那一个弹出并加入到打折区间
{
L.insert(*H.rbegin()); //rbegin相当于末尾的指针
p -= *H.rbegin();
p += (*H.rbegin()+1)>>1;
H.erase(H.find(*H.rbegin()));
}
}
else //如果在原价区间，直接操作即可
{
p -= b[l];
H.erase(H.find(b[l]));
}
all -= a[l]; //减掉被弹出左端点的贡献
l++; //左移指针
}
ans = max(ans,all);//更新答案
}
cout << ans << endl;
}