题目描述
https://codeforces.com/contest/1497/problem/E2
Solution
原题等价于将所有数字按照出现奇数次的质因子分类，同类的不能出现在同一段
我们令 $f[i][j]$ 表示前 $i$ 个数改 $j$ 次最少分几段，注意到 $f[][j]$ 是单调不升的
所以 $f[i][j]$ 只需要找一个最小的 $k$ 且 $[k+1,i]$ 是合法段就行了，注意到对于每个 $j$ 这个东西随着 $i$ 增加，$k$ 也是单调的
所以我们可以直接维护这个 $k$，时间复杂度 $O(nk)$
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define maxn 200010
#define maxm 10000010
#define maxk 21
#define INF 1000000000
using namespace std;
int n, k, id[maxn];
int pri[maxm], a[maxm]; bool isp[maxm];
void init_isp(int n) {
int cnt = 0;
for (int i = 2; i <= n; ++i) {
if (!isp[i]) pri[++cnt] = i, a[i] = i;
for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = 1; a[i * pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
}
map<vector<int>, int> mp; int top;
int cnt[maxn][maxk], f[maxn][maxk], sum[maxk], p[maxk];
void work() {
cin >> n >> k; mp.clear(); top = 0;
for (int i = 1; i <= n; ++i) {
int x; vector<int> A; cin >> x;
while (x > 1) {
int y = a[x], s = 0;
while (x % y == 0) x /= y, ++s;
if (s & 1) A.push_back(y);
} sort(A.begin(), A.end());
if (mp.find(A) == mp.end()) mp[A] = ++top;
id[i] = mp[A];
}
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= k; ++j) f[i][j] = INF, cnt[i][j] = 0;
for (int i = 0; i <= k; ++i) sum[i] = 0, p[i] = 1;
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= ::k; ++j) {
if (++cnt[id[i]][j] > 1) ++sum[j];
while (sum[j] > j) {
if (--cnt[id[p[j]]][j] >= 1) --sum[j];
++p[j];
}
}
for (int j = 0; j <= ::k; ++j)
for (int k = 0; k <= j; ++k)
f[i][j] = min(f[i][j], f[p[k] - 1][j - k] + 1);
}
cout << *min_element(f[n], f[n] + k + 1) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T; init_isp(10000000);
while (T--) work();
return 0;
}
|