CF1497E2 Square-free division (hard version)

某模拟赛 T2，自己做法是

\operatorname{O}(n \cdot k)

时间复杂度，发现题解是

\operatorname{O}(n \cdot k ^ 2)

时间复杂度的，且原题题解区中没有

\operatorname{O}(n \cdot k)

做法，意识到爆标，遂来写题解。

首先，发现可以把每个数的平方因子去掉，之后即可通过比较两数是否相等来判断两数之积是否为完全平方数。

于是，可以设置动规状态为

dp_{i,j}

表示以第

i

个数为结尾，修改了

j

次的最小段数。我们发现这个状态无法转移，所以我们可以再记录一个值

st_{i,j}

表示

dp_{i,j}

最小时，最后一个段的开头的下标最大是多少。发现做法正确，愉快爆标。

code

CPP

#include<bits/stdc++.h>
using namespace std;
#define V 10000005
#define N 200005
int n, k, p[670000], a[N], bok[V], dp[N][25], st[N][25];
bool book[V];
inline void init() {
	for(int i = 2; i < V; ++i) {
		if(!book[i]) p[++p[0]] = i;
		for(int j = 1; j <= p[0] && 1ll * p[j] * i < V; ++j) {
			book[p[j] * i] = 1;
			if(!(i % p[j])) break;
		}
	}
}
int main() {
	//freopen("seq.in", "r", stdin);
	//freopen("seq.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	init();
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> k;
		for(int i = 1; i <= n; ++i) {
			a[i] = 1;
			int now;
			cin >> now;
			for(int j = 1; book[now]; ++j) {
				if(!(now % p[j])) {
					bool aa = 0;
					while(!(now % p[j])) aa = !aa, now /= p[j];
					if(aa) a[i] *= p[j];
				}
			}
			if(now) a[i] *= now;
			int lst = bok[a[i]];
			for(int j = k; ~j; --j) dp[i][j] = dp[i - 1][j] + 1, st[i][j] = i;
			for(int j = 0; j <= k; ++j) {
				if(lst < st[i - 1][j]) {
					if(dp[i - 1][j] < dp[i][j]) dp[i][j] = dp[i - 1][j], st[i][j] = st[i - 1][j];
					else if(dp[i - 1][j] == dp[i][j]) st[i][j] = max(st[i - 1][j], st[i][j]);
				} else {
					if(dp[i - 1][j] < dp[i][j + 1]) dp[i][j + 1] = dp[i - 1][j], st[i][j + 1] = st[i - 1][j];
					else if(dp[i - 1][j] == dp[i][j + 1]) st[i][j + 1] = max(st[i - 1][j], st[i][j + 1]);
				}
			}
			//cout << i << "  " << lst << "  " << a[i] << endl;
			//for(int j = 0; j <= k; ++j) cout << j << "  " << dp[i][j] << "  " << st[i][j] << endl;
			bok[a[i]] = i;
		}
		for(int i = n; i; --i) bok[a[i]] = 0;
		int ans = 0x7fffffff;
		for(int i = k; ~i; --i) if(st[n][i]) ans = min(ans, dp[n][i]);
		printf("%d\n", ans);
	}
	return 0;
}

CF1497E2 Square-free division (hard version)

文章操作

code

相关推荐

评论

CF1497E2 Square-free division (hard version)