2023.10.13 恒生电子 笔试

1.记忆化搜索就可以了

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
vector<int>a;
int dp[N][2][4];
int dfs(int u,int col,int k)
{
	int &res=dp[u][(col==-1?0:1)][k];
	if(res!=-1)return res;
    
    if(u==(int)a.size()-1)
    {
        if(col!=-1)return a[u];
        return 0;
    }
	if(col!=-1)
    {
        res=max(dfs(u+1,-1,k)+a[u],dfs(u+1,col,k));
    }
	else 
    {
        if(k)res=max(dfs(u+1,a[u],k-1)-a[u],dfs(u+1,col,k));
        else res=dfs(u+1,col,k);
    }
	
	return res;
}
void solve()
{
	memset(dp,-1,sizeof dp);
	cout<<dfs(0,-1,3)<<endl;	
	return ;
}
int main()
{
	int x;
	while(cin>>x)
    {
        a.push_back(x);
        char c;
        if(cin>>c)continue;
        else break;
    }
    //cout<<a.size()<<endl;
	solve();
	return 0;
}

2.求范围内质数和的平方根

我的做法就是筛质数，然后求根号就可以了。但是不知道为什么只能过0.8

我最开始觉得可能是精度问题，但是手写开根号以后，还是只能过0.8 而且中间调试精度以后确实可以过的更多。不知道为什么

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
long long sum;
bool st[N];
void solve()
{
	int n;cin>>n;
	vector<int>p;
	for(int i=2;i<=n;i++)
	{
		if(!st[i])sum+=i;
		
		for(int j=0;j<(int)p.size()&&1ll*p[j]*i<=n;j++)
		{
			st[p[j]*i]=true;
			if(i%p[j]==0)break;
		}
	}
	cout<<fixed<<setprecision(4)<<sqrt(sum)<<endl;
	return ;
}
int main()
{
	
	solve();
	return 0;
}