A. Spread
不说了，代码。
B. Next
不说了，代码。
C. Count xxx
Description
给定一个长度为 \(N\) 的字符串 \(S\)，求 \(S\) 中非空连续，并且包含重复字符的连续子串长度。
例如 $S = $ aaabaa，则它满足上述条件子串为 a，aa，aaa，b。
Solution
这道题 \(1 \le N \le 2 \times 10 ^ 5\)，显然不能暴力。
考虑如何优化。
维护数组 \(v\)，\(v_i\) 表示 \(S\) 中子串的重复字符为 \(i\) 的子串长度。
我们循环这个字符串，记录两个变量 lstc，lstnum，分别表示字符串 \(S\) 的上一个字符，和当前连续子串的长度。
如果我们发现，s[i] == lstc，则 lstnum++。否则，lstnum = 1，lstc = s[i]。
每次循环 v[lstc] = max(v[lstc],lstnum)。
最后循环字符 a ~ z，累加 \(v_i\) 即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, ans, v[300];
char s[N];
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
char lstc = 0;
int lstnum = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == lstc) {
++lstnum;
} else {
lstnum = 1;
lstc = s[i];
}
v[lstc] = max(v[lstc], lstnum);
}
int ans = 0;
for (int i = 'a'; i <= 'z'; ++i) {
ans += v[i];
}
printf("%d", ans);
return 0;
}
D. Election Quick Report
Description
有 \(N\) 个人，编号 \(1 \sim N\)。每次会将票投给某一个人，输出投票后票数最大值的人的编号。如果票数相同，输出编号小的。
Solution
每次记录一个桶，动态维护当前票数的最大值，位置即可。
如果当前的票数大于最大值，或者当前票数等于最大值但是编号小于最大值，则讲最大值更改为当前的票数，并且将位置更改为当前的位置。
每次询问输出位置即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, a[N], cnt[N], ma = 0, p;
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
if (cnt[a[i]] > ma || (cnt[a[i]] == ma && a[i] < p)) {
ma = cnt[a[i]];
p = a[i];
}
printf("%d\n", p);
}
return 0;
}
E. Stamp
Description
有两个字符串 \(S\) 和 \(T\)，还有一个长度为 \(N\) 的仅由字符 # 构成的字符串 \(X\)。
现在可以执行若干次操作，每次可以选择字符串 \(X\) 中连续的 \(M\) 段覆盖为 \(T\)。
求：是否能通过若干次操作，使得 \(X\) 和 \(S\) 相等。
Solution
考虑一个覆盖时间的序列（钦定每一次覆盖记录在其右端点上），发现对于当前点 \(p\)：
只有 \([p,p+m-1]\) 这一段区间会影响该点的取值，考虑爆搜，对于当前位置p，只需要考虑 \([p-m+1,p]\) 这一段长度为m的时间序列，枚举当前一个新的位置的相对时间排名，确定下来 \([p-m+1,p]\) 的相对时间顺序，于是位置 \(p-m+1\) 的值会被 \([p-m+1,p]\) 中时间值最大的点覆盖掉，再判断 \(p-m+1\) 的值是否与 \(S\) 串对应位置相等即可。
考虑优化：当前状态包含当前位置 \(p\)，和前面的时间序列 \(st\)，若之前已经走到过 <p,st> 这样一个状态，那当前就没必要继续往下搜了。
Code
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int n, m;
int gethash(int now, int stat[5]) {
int hsh = now;
for (int i = 0; i < m - 1; i++) hsh = hsh * m + stat[i];
return hsh;
}
char s[200055];
char t[55];
bool search(int now, int stat[5]) {
int hsh = gethash(now, stat);
if (mp.find(hsh) != mp.end()) return false;
mp[hsh] = 1;
if (now == n + 1) {
char x[6];
for (int j = 1; j < m; j++) {
for (int k = 0; k < m - 1; k++) {
if (stat[k] == j) {
for (int l = 2; l <= m - k; l++) {
x[l] = t[l + k];
}
}
}
}
for (int i = 2; i <= m; i++) if (s[n + i - m] != x[i]) return false;
return true;
}
for (int i = 1; i <= m; i++) {
int new_stat[5];
new_stat[0] = i;
for (int j = 1; j < m; j++) {
new_stat[j] = stat[j - 1];
if (stat[j - 1] >= i) ++new_stat[j];
}
bool flag = true;
for (int j = 0; j < m; j++) {
if (new_stat[j] == m) {
if (s[now - m + 1] != t[j + 1]) flag = false;
}
}
if (!flag) continue;
for (int j = 0; j < m - 1; j++) {
if (new_stat[j] > new_stat[m - 1]) --new_stat[j];
}
if (search(now + 1, new_stat)) return true;
}
return false;
}
int stat[5];
int main() {
cin >> n >> m;
scanf("%s%s", s + 1, t + 1);
if (s[1] != t[1]) {
puts("No");
return 0;
}
for (int i = 0; i < 5; i++) stat[i] = m - i - 1;
if (search(m + 1, stat)) {
printf("Yes");
return 0;
}
printf("No");
return 0;
}
F. Colored Ball
Description
有 \(N\) 个箱子，编号为 \(1 \sim N\)。每个箱子初始有一个小球，颜色为 \(C_i\)。
现在有 \(Q\) 次询问，每次输入一个二元组 \((a,b)\)，表示将编号为 \(a\) 的箱子里的所有小球移动到箱子 \(b\) 后，询问箱子 \(b\) 中有多少种不同颜色的小球。
Solution
这道题用 set 的暴力模拟法，时间复杂度约为 \(O(n ^ 2 \times \log n)\)，肯定超时。
可以加上优化：set 的启发式合并。
即每次将小的箱子移动到大的箱子里面，这样花费的时间会大大减少，时间复杂度达到了 \(O(n)\)。
只需要在代码中加入一句话：
if (st[x].size() > st[y].size()) swap(st[x], st[y]);
这样就实现了启发式合并，可以通过。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, q, a[N], x, y;
unordered_set<int> st[N];
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
st[i].insert(a[i]);
}
while (q--) {
scanf("%d%d", &x, &y);
if (st[x].size() > st[y].size()) swap(st[x], st[y]);
while (st[x].size()) {
int t = *st[x].begin();
st[x].erase(t);
st[y].insert(t);
}
printf("%d\n", (int)st[y].size());
}
return 0;
}