一看数据范围dp基本无解,除非你有o(n)或者o(logn)的优化。
第一个难点是怎么判断两个数是不是矛盾,这个思想和https://www.cnblogs.com/liyishui2003/p/15304751.html契合
都是在除掉最大平方因子后hash,因为我们只关心奇数或者偶数次,那么01就够了。
第二个点是怎么得到答案,对于当前一个合法的序列,接下来的新数a,可以加入,也可以自成一组。
题解都说贪心直接加啦。
yy了一下贪心的证明:
第一条线段说的是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转移啦..虽然实质一样。
记录很弱的李一水,还活着。