Square division

爱被打了一巴掌 2022-08-28 08:52 170阅读 0赞

# [Problem - E1 - Codeforces][] #

![在这里插入图片描述][fabfb0eacd514406a6859f6729b7e77c.png]

# 思路：尺取的做法 #

## 参考代码 ##

#include<iostream>
    #include<algorithm>
    #include<map>
    using namespace std;
    const int N = 1e7 + 10;
    int primes[N], cnt;
    bool not_prime[N];
    int n, k;
    int a[N];
    int ans = 0;
    void get_prime(int n) {
    	for (int i = 2; i <= n; i++) {
    		if (!not_prime[i])primes[cnt++] = i;
    		for (int j = 0; primes[j] <= n / i; j++) {
    			not_prime[primes[j] * i] = true;
    			if (i % primes[j] == 0)break;
    		}
    	}
    }
    int get(int n)
    {
    	int res = 1;
    	for (int i = 0; primes[i] * primes[i] <= n; i++)
    	{
    		int t = primes[i], u = 0;
    		while (n % t == 0)n /= t, u++;
    		if (u & 1)res *= t;
    	}
    	if (n != 1)res *= n;
    	return res;
    }
    int main()
    {
    	get_prime(N - 2);
    	int T;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%d%d", &n, &k);
    		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    		map<int, int> mp;
    		ans = 1;
    		for (int i = 1; i <= n; i++)
    		{
    			int t = get(a[i]);
    			if (mp[t]) {
    				mp.clear();
    				ans++;
    			}
    			mp[t]++;
    		}
    		printf("%d\n", ans);
    	}
    	return 0;
    }

# [Problem - E2 - Codeforces][] #

题解：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55m96Iq36aao_size_20_color_FFFFFF_t_70_g_se_x_16]

## 参考代码 ##

#include<iostream>
    #include<algorithm>
    #include<map>
    using namespace std;
    const int INF = 1e9;
    const int N = 1e7 + 10;
    int primes[N], cnt;
    bool not_prime[N];
    int n, k;
    int a[N];
    int ans = 0;
    int dp[213456][23], L[213456][23];
    int vis[N];
    void get_prime(int n) {
    	for (int i = 2; i <= n; i++) {
    		if (!not_prime[i])primes[cnt++] = i;
    		for (int j = 0; primes[j] <= n / i; j++) {
    			not_prime[primes[j] * i] = true;
    			if (i % primes[j] == 0)break;
    		}
    	}
    }
    int get(int n)
    {
    	int res = 1;
    	for (int i = 0; primes[i] * primes[i] <= n; i++)
    	{
    		int t = primes[i], u = 0;
    		while (n % t == 0)n /= t, u++;
    		if (u & 1)res *= t;
    	}
    	if (n != 1)res *= n;
    	return res;
    }
    
    int main()
    {
    	get_prime(N - 2);
    	int T;
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%d%d", &n, &k);
    		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    		for (int i = 1; i <= n; i++)a[i] = get(a[i]);
    	
    
    
    		for (int ci = 0; ci <= k; ci++)//尺取操作
    		{
    			int p = 1; 
    			for (int i = 1,s=0; i <= n; i++)
    			{
    				vis[a[i]]++;
    				if (vis[a[i]]>1)s++;
    				while (s > ci) {
    					if (vis[a[p]] > 1)s--;
    					vis[a[p++]]--;
    				}
    
    				L[i][ci] = p;
    			}
    			for (int i = 1; i <= n; i++)vis[a[i]] = 0;
    		}
    
    
    		for (int i = 1; i <= n; i++)for (int t = 0; t <= k; t++)dp[i][t] = INF;
    		for (int t = 0; t <= k; t++)dp[0][t] = 0;
    	
    		for(int i=1;i<=n;i++)
    			for (int j = 0; j <= k; j++) 
    				for (int t = 0; t <= j; t++) 
    					dp[i][j] = min(dp[i][j], dp[L[i][t] - 1][j - t] + 1);
    
    	
    		printf("%d\n", dp[n][k]);
    	}
    	return 0;
    }

; j++)  
for (int t = 0; t <= j; t++)  
dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[L\[i\]\[t\] - 1\]\[j - t\] + 1);

printf("%d\n", dp[n][k]);
    }
    return 0;

[Problem - E1 - Codeforces]: https://codeforces.com/contest/1497/problem/E1
[fabfb0eacd514406a6859f6729b7e77c.png]: /images/20220828/75dfbc8090e3404487c22047550b9d11.png
[Problem - E2 - Codeforces]: https://codeforces.com/contest/1497/problem/E2
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55m96Iq36aao_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ed0273caff544efb91fc7f25d1cb46d7.png