题目大意
给定一个字符串,只包含 0
,1
,?
,三种字符,其中 ?
可以为 \(0\) 和 \(1\) 种的任意一个数。
对于一个 \(x(1 \le x \le n)\),要求出最多有多少个没有交集的字串,使得每个字串里只有 \(0\) 或 \(1\),并且长度为 \(k\),且 \(1 \le k \le n\),其中 ?
要替换成 \(0\) 或 \(1\)。
思路
不难想到可以先用双指针求出一个 \(len_i\) 数组,表示从 \(i\) 往后最长的一段连续序列的长度,要么只包含 0
和 ?
,要么只有 1
和 ?
。
不妨先枚举一个 \(k\),表示现在的
接下来就是重点了,维护一个 \(fa\) 数组,\(fa_i\) 表示从 \(i\) 开始往后的第一个满足 \(len_{fa_i} \ge k\) 的数的下标,可以用并查集来维护,即\(fa_i\) 就是一个只保存头节点的指针,每次的 \(find\) 操作都相当于更新 \(fa\) 数组的值,其中 \(find\) 函数必须写成路径压缩的形式。
- 更新 \(fa\) 数组
一开始,所有的 \(fa_i\) 都等于 \(i\),\(fa_{n + 1} = n + 1\),\(n + 1\) 表示无解。
很明显,如果 \(len_i\) 都小于 \(k\),则一定无法选 \([i, i + len_i - 1]\) 这个区间,所以如果当前枚举到 \(k\),就要将 \(len_i = k - 1\) 的数的 \(fa_i\) 更新成 \(i + 1\),意思为排除掉自身,往后的第一个满足条件的下标。
比如 \(??01?11\) 这组数据的 \(len\) 数组为:\(3\ 2\ 1\ 4\ 3\ 2\ 1\),\(fa\) 数组为:\(1\ 2\ 3\ 4\ 5\ 6\ 7\)。假设当前的 \(k\) 等于 \(2\),则需要将 \(len_i = 1\) 的数字更新,所以 \(fa\) 数组会更新为 \(1\ 2\ 4\ 4\ 5\ 6\ 8\),那下标为 \(3\) 的数为例:虽然不能确定 \(3 + 1 = 4\) 这个下标是否合法,但是确可以根据 \(fa_{fa_3}\) 即 \(fa_4\) 进行递归,找到最早的一个合法的下标,这个递归行为即为 \(find\) 函数。
再举个例子,\(101101110\),这组数据的 \(len\) 数组为:\(1\ 1\ 2\ 1\ 1\ 3\ 2\ 1\ 1\),\(fa\) 数组为:\(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\)。假设当前的 \(k\) 等于 \(2\),则需要将 \(len_i = 1\) 的数字更新,所以 \(fa\) 数组会更新为 \(2\ 3\ 3\ 5\ 6\ 6\ 7\ 9\ 10\),以下标为 \(1\) 的数为例,虽然 \(fa_1\) 被更新为了 \(2\),但是 \(len_2\) 也是不合法的,但是 \(fa_2\) 还可以继续递归至 \(fa_{fa_2}\) 即 \(fa_3\),发现 \(fa_3 = 3\),即找到了一个合法的下标。
- 计算答案
显然,答案需要从 \(j = 1\) 开始枚举,每一次找到最早的一个合法下标,即 \(j = find(j)\),并将答案加上一,将 \(j\) 加上 \(k\)。
代码
#include <bits/stdc++.h>
using namespace std;const int N = 1000010;
int n, sum0[N], sum1[N], fa[N], len[N], num[N], res[N];
string s;bool chk(int l, int r) {return (sum1[r] - sum1[l - 1] == 0) || (sum0[r] - sum0[l - 1] == 0);
}bool cmp(int x, int y) {return len[x] < len[y];
}int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int m;cin >> n >> m >> s; s = " " + s;for (int i = 1; i <= n; i++)sum0[i] = sum0[i-1] + (s[i] == '0'),sum1[i] = sum1[i-1] + (s[i] == '1');for (int i = 1; i <= n; i++) {len[i] = max(0, len[i - 1] - 1);while (i + len[i] <= n && chk(i, i + len[i])) len[i]++;}for (int i = 1; i <= n; i++) fa[i] = num[i] = i;fa[n + 1] = n + 1;sort(num + 1, num + n + 1, cmp);int j = 1;for (int i = 1; i <= n; i++) {while (j <= n && len[num[j]] < i)fa[num[j++]] = num[j] + 1;int t = 1;while (1) {t = find(t);if (t >= n + 1) break;res[i]++;t += i;}}for (int i = 1; i <= n; i++)cout << res[i] << " ";return 0;
}
个人总结
考场的思虑
没有想到可以用链表的方式来解决,并且用并查集的方法来维护次操作。
怎么改进
多做题,积累一些常见的套路,并熟悉一些算法之间的互相转化和维护