CF1497E1 Square-free division (easy version) 一点点贪心+map

一看数据范围dp基本无解,除非你有o(n)或者o(logn)的优化。

第一个难点是怎么判断两个数是不是矛盾,这个思想和https://www.cnblogs.com/liyishui2003/p/15304751.html契合

都是在除掉最大平方因子后hash,因为我们只关心奇数或者偶数次,那么01就够了。

第二个点是怎么得到答案,对于当前一个合法的序列,接下来的新数a,可以加入,也可以自成一组。

题解都说贪心直接加啦。

yy了一下贪心的证明:

CF1497E1 Square-free division (easy version) 一点点贪心+map

第一条线段说的是a在可以加入时却自成一组的情况(没考虑不可以加入,不可以加入就只能自成一组了,讨论啥)

在接下来某一个点必会遇到一个数b,当b加入后序列就不合法了。

那么b只能新开了。

同时的,有a到b前的那个数,这一序列都是合法的。

假设我们刚才a加入了,那么有两种情况,这个数列继续增长,直到在a和b之间遇到困难;

或者一路增长到了b前,到b被卡了。

对于第二种情况,显然这时贪心使a加进去就是最优的,因为我们只放了一根新的小黑木棍隔开。

对于第一种情况,还分两类:

序列在a和b中间被卡了以后,我们在这里放一根小黑木棍。

那么b可能是和第二段中绿色部分冲突,也可能是和第三段中的绿色部分冲突

对于第二段,我们贪心没有使答案变坏,依然保持了最优解。

对于第三段,我们放的小黑木棍还是更少。

 证毕~

#include<bits/stdc++.h>
using namespace std;
int t,n,k,num[200005],dp[200005],g[200005];
unordered_map<int,int>Hash;
int solve(int x)
{
	for(int i=2;;i++)
	{
		int even=i*i;
		while(x>=even&&x%even==0)
		{
			x/=even;
		}
		if(x<even)
		{
			break;
		}
	}
	return x;
}
int main( )
{
/*
3
5 0
18 6 2 4 1
5 0
6 8 1 24 8
1 0
1
*/

 //freopen("918.in","r",stdin);

   cin>>t;
   while(t--)
   {
   	Hash.clear();
   	cin>>n>>k;
   	for(int i=1;i<=n;i++)
   	{
   	  	cin>>num[i];
   	  	int x=solve(num[i]);
   	  	num[i]=x;
		if(Hash[x]==0)
   	  	{
   	  		Hash[x]=i;
		}
	}
	
	dp[1]=1;
	g[1]=1;
	
	for(int i=2;i<=n;i++)
	 {
	 	int id=g[i-1];
	 	int near=Hash[num[i]];
	 	if(id>near||near==i)//当当前最大段没有出现相同个数,或者当前值是第一次出现 
	 	{
	 	  g[i]=g[i-1];
		  dp[i]=dp[i-1];
		  Hash[num[i]]=i;	
		}
		else {
			g[i]=i;
			dp[i]=dp[i-1]+1;
			Hash[num[i]]=i;
		}
	 }
	 cout<<dp[n]<<endl;
	/*
	dp(i)=dp(i-1)+1;
	g[i]=i;
	
	else dp(i)=dp(i-1);
	farther=g[i-1]
	*/ 
   }
}

  虽然是贪心但我想的时候是用dp转移啦..虽然实质一样。

       记录很弱的李一水,还活着。

上一篇:在控制台打印佛祖图片


下一篇:codeforces1445C Division(唯一分解定理)