小信的装备RE30

问题讨论区 普及段
41

i*i<=q

42

i \times i \le q

43

是不是sqrt比i*i<=n慢啊？

44

写后者

45
  1. sqrt 有精度问题
  2. sqrt 作为函数慢一些（吧）
46

我旁边的

47 
#include <bits/stdc++.h>
#define s i*prime[j]
using namespace std;
map<int,int> mp;
map<int,int> vis;
int prime[10000001],dp[10000001];// dp[i]->当前选的是i的因数且可选,最多能选多少个数
int main(){
	freopen("item.in","r",stdin);
	freopen("item.out","w",stdout);
	int n,pmaxn=0;
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		mp[x]++;
		pmaxn=max(pmaxn,x);
	}
	int p=0;
    vis[0]=1;
    vis[1]=1;
    for(int i=2;i*i<=n;i++){
        if(vis[i]==0){
            for(int j=i+i;j<=n;j+=i){
                vis[j]=1;
            }
        }
    }
    for(int i=1;i<=pmaxn;i++){
      if(vis[i]==0){
        prime[++p]=i;
      }
    }
	for(int i=1;i<=pmaxn;i++){
		dp[i]+=mp[i];
		for(int j=1;s<=pmaxn&&j<=p;j++){
			dp[s]=max(dp[s],dp[i]);
		}
	}
	int maxn=0;
	for(int i=1;i<=pmaxn;i++){
		if(mp[i]!=0){
			maxn=max(maxn,dp[i]);
		}
	}
	printf("%d",maxn);
}
/*
6
1 4 2 8 5 7

1 2 3 2 2 4
1 2 4 5 7 8
*/

所以埃拉托斯尼筛法最优咋写啊？？？

@董子豪

48

j<=n \to j*j<=n

49

节省很多时间

1 个赞
50

有没有可能是RE

#include <bits/stdc++.h>
#define s i*prime[j]
using namespace std;
map<int,int> mp;
map<int,int> vis;
int prime[10000001],dp[10000001];// dp[i]->当前选的是i的因数且可选,最多能选多少个数
int main(){
	freopen("item.in","r",stdin);
	freopen("item.out","w",stdout);
	int n,pmaxn=0;
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		mp[x]++;
		pmaxn=max(pmaxn,x);
	}
	int p=0;
    vis[0]=1;
    vis[1]=1;
    for(int i=2;i*i<=n;i++){
        if(vis[i]==0){
            for(int j=i+i;j*j<=n;j+=i){
                vis[j]=1;
            }
        }
    }
    for(int i=1;i<=pmaxn;i++){
      if(vis[i]==0){
        prime[++p]=i;
      }
    }
	for(int i=1;i<=pmaxn;i++){
		dp[i]+=mp[i];
		for(int j=1;s<=pmaxn&&j<=p;j++){
			dp[s]=max(dp[s],dp[i]);
		}
	}
	int maxn=0;
	for(int i=1;i<=pmaxn;i++){
		if(mp[i]!=0){
			maxn=max(maxn,dp[i]);
		}
	}
	printf("%d",maxn);
}
/*
6
1 4 2 8 5 7

1 2 3 2 2 4
1 2 4 5 7 8
*/

我是不是得删数组？？？

51

bzd

52

帮我也看看吧

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int n,ans=0;
vector<int> a;
map<int,int> mp;
int f[10000005];
int main(){
//	freopen("item.in","r",stdin);
//	freopen("item.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		a.push_back(x);
		mp[x]=i+1;
		f[x]=1;
	}
	sort(a.begin(),a.end());
	for(int i=0;i<n;i++){
		int cnt=1;
		for(int j=1;j*j<=a[i];j++)
			if(a[i]%j==0){
				if(mp.find(j)!=mp.end())
					cnt=max(cnt,f[j]+1);
				else if(mp.find(a[i]/j)!=mp.end()&&j*j!=a[i])	
					cnt=max(cnt,f[a[i]/j]+1);				
			}
		f[a[i]]=cnt;	
	}	
	for(int i=0;i<n;i++)
		ans=max(ans,f[a[i]]);
	printf("%d",ans);
	return 0;
}
53

我！！！

54

乐qwq

55

A了吗