【2019.7.22 NOIP模拟赛 T1】麦克斯韦妖（demon）（质因数分解+DP）

ゝ一世哀愁。 2021-10-29 11:16 210阅读 0赞

### 暴力\\(DP\\) ###

先考虑暴力\\(DP\\)该怎么写。

因为每个序列之后是否能加上新的节点只与其结尾有关，因此我们设\\(f\_i\\)为以\\(i\\)为结尾的最长序列长度。

每次枚举一个前置状态，判断是否合法之后进行转移。

### 优化\\(DP\\) ###

上面做法的瓶颈在于，判断是否合法需要大量时间。

则有一个比较巧妙的做法。

首先对于每一个数\\(a\_i\\)，\\(\\sqrt \{max\_\{x=1\}^na\_x\}\\)范围内的某一质数\\(j\\)，我们求出\\(p\_\{i,j\}\\)表示\\(a\_i\\)是否含有质因数\\(j\\)。

然后，再对与每一个数\\(a\_i\\)，我们用\\(s\_i\\)存下其大于\\(\\sqrt\{max\_\{x=1\}^na\_x\}\\)的质因数，若没有则\\(s\_i=1\\)。

那么，我们可以用\\(g\_x\\)表示所有的\\(a\_i\\)含有质因数\\(x\\)的\\(f\_i\\)的最大值，用\\(Mx\_x\\)表示所有的\\(s\_i=x\\)的\\(f\_i\\)的最大值\\((x!=1)\\)，然后记下\\(MP\\)和\\(MP\\\_\\)分别表示\\(Mx\_x\\)的最大值和次大值所对应的\\(x\\)。

转移时我们可以从所有当前\\(a\_i\\)不含的质数所对应的\\(g\\)转移，然后若\\(s\_i=MP\\)，则从\\(Mx\_\{MP\\\_\}\\)转移，否则从\\(Mx\_\{MP\}\\)转移。

具体实现时我们可以把\\(g\_x\\)中\\(x\\)的定义改为第\\(x\\)个质数。

### 代码 ###

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 100000 #define M 1000000 #define SM 1000 #define Gmax(x,y) (x<(y)&&(x=(y))) using namespace std; int n,a[N+5]; class FastIO { private: #define FS 100000 #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++) #define tn (x<<3)+(x<<1) #define D isdigit(c=tc()) char c,*A,*B,FI[FS]; public: I FastIO() {A=B=FI;} Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);} Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);} }F; template<int SZ> class LinearSiever//线性筛筛质数 { public: int Pt,P[SZ+5]; I LinearSiever() { RI i,j;for(i=2;i<=SZ;++i) for(!P[i]&&(P[++Pt]=i), j=1;j<=Pt&&1LL*i*P[j]<=SZ;++j) if(P[i*P[j]]=1,!(i%P[j])) break; } }; class PrimeSolver { private: int f[N+5],g[SM+5],Mx[M+5],s[N+5],p[N+5][SM+5];LinearSiever<SM> P; I void Init(CI x)//初始化，质因数分解预处理每个数 { RI i;for(s[x]=a[x],i=1;i<=P.Pt;++i) { if(s[x]%P.P[i]) continue;p[x][i]=1; W(!(s[x]%P.P[i])) s[x]/=P.P[i]; } } public: I void Solve() { RI i,j,MP=0,MP_=0,ans=0;for(i=1;i<=n;++i)//DP { for(Init(i),f[i]=0,j=1;j<=P.Pt;++j) !p[i][j]&&Gmax(f[i],g[j]+1);//从当前a[i]不含的质数转移 MP^s[i]?Gmax(f[i],Mx[MP]+1):Gmax(f[i],Mx[MP_]+1);//从Mx处转移 for(j=1;j<=P.Pt;++j) p[i][j]&&Gmax(g[j],f[i]);if(s[i]==1||f[i]<=Mx[s[i]]) continue;//更新g值 Mx[s[i]]=f[i],MP^s[i]&&(Mx[MP]<f[i]?(MP_=MP,MP=s[i]):Mx[MP_]<f[i]&&(MP_=s[i]));//更新Mx值，并更新MP和MP_ } for(i=1;i<=n;++i) Gmax(ans,f[i]);printf("%d",ans);//统计并输出答案 } }S; int main() { freopen("demon.in","r",stdin),freopen("demon.out","w",stdout); RI i;for(F.read(n),i=1;i<=n;++i) F.read(a[i]);return S.Solve(),0; }

转载于:https://www.cnblogs.com/chenxiaoran666/p/Contest20190722T1.html