526互联

CodeForces 1497E2 Square-free division (hard version)

发布时间 2023-12-06 10:12:24作者: zltzlt

洛谷传送门

CF 传送门

感觉和 CF1889C2 Doremy's Drying Plan (Hard Version) 有异曲同工之妙。

显然去除每个数的平方因子后，两个数相乘为完全平方数当且仅当它们相等。

考虑若确定了分段方案，那么修改次数就是，每一段重复出现的数的个数。

那么我们设 \(f_{i, j}\) 为 \([1, i]\) 修改了 \(j\) 次的最小分段次数。然后我们枚举上一个分段点 \(k\)，那么有 \(f_{i, j} \gets f_{k, j - g(k + 1, i)} + 1\)，其中 \(g(l, r)\) 为 \([l, r]\) 中重复出现的数的个数。

显然对于一个 \(j\)，\(f_{\ast, j}\) 单调不降，那么我们可以找到 \(\forall p \in [0, m]\)，使得 \(g(k + 1, i) = p\) 的 \(k\) 的最小值，然后直接从这个 \(k\) 转移过来。

时间复杂度就是 \(O(nk^2)\)。去除平方因子我写了 \(O(n \sqrt{V})\)，也能过。

code 
// Problem: E2. Square-Free Division (hard version)
// Contest: Codeforces - Codeforces Round 708 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1497/E2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;
const int maxm = 3300;
const int N = 3200;

int n, m, a[maxn], pr[maxm], tot, b[maxm], f[maxn][22];
bool vis[maxm];

inline void init() {
	for (int i = 2; i <= N; ++i) {
		if (!vis[i]) {
			pr[++tot] = i;
			b[tot] = i * i;
		}
		for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {
			vis[i * pr[j]] = 1;
			if (i % pr[j] == 0) {
				break;
			}
		}
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		for (int j = 1; j <= tot && b[j] <= a[i]; ++j) {
			while (a[i] % b[j] == 0) {
				a[i] /= b[j];
			}
		}
	}
	map<int, int> mp;
	set<int> S;
	S.insert(0);
	for (int i = 1; i <= n; ++i) {
		if (mp.find(a[i]) != mp.end()) {
			S.insert(mp[a[i]]);
		}
		mp[a[i]] = i;
		auto it = S.end();
		vector<int> vc;
		do {
			vc.pb(*(--it));
		} while (it != S.begin() && (int)vc.size() <= m);
		for (int j = 0; j <= m; ++j) {
			f[i][j] = 1e9;
		}
		for (int j = 0; j < (int)vc.size(); ++j) {
			for (int k = j; k <= m; ++k) {
				f[i][k] = min(f[i][k], f[vc[j]][k - j] + 1);
			}
		}
	}
	printf("%d\n", *min_element(f[n], f[n] + m + 1));
}

int main() {
	init();
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}