蓝桥杯第 1 场小白入门赛

本文介绍: 我们可以发现无论左右结果不会变的那么也就是我们这个结果是不受操作所影响的，所以我们选择最优的操作直接从左到右即可，注意数据范围很大所以我们考虑要使用__int128来处理。我们需要构造的数字最大，由于数位已经告诉我们，所以明显的有一个贪心的策略：从最高位置开始从最大的数开始遍历是否可以填可以填减去看下一位即可。我们可以知道和是一个概率dp，依照题目意思我们定义状态为当前为x是期望为dp[x](x==i)我们有一个错误的想法就是找出最大的质数x然后直接求长度x的即可，为什么是错误的呢？

1.蘑菇炸弹

1.蘑菇炸弹

我们直接依照题目在中间位置的数进行模拟即可

void solve(){
   
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    
    int ans=0;
    for(int i=2;i<n;i++){
        if(a[i]>=a[i-1]+a[i+1]) ans++;
    }
    
    cout<<ans<<endl;
    return ;
}

2.构造数字

我们需要构造的数字最大，由于数位已经告诉我们，所以明显的有一个贪心的策略：从最高位置开始从最大的数开始遍历是否可以填可以填减去看下一位即可

void solve(){
   
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
    	for(int j=9;j>=0;j--){
    		if(m>=j){
    			cout<<j;
    			m-=j;
    			break;
    		}
    	}	
    }
    return ;
}

3.小蓝的金牌梦

我们有一个错误的想法就是找出最大的质数x然后直接求长度x的即可，为什么是错误的呢？因为题目中的元素带有负数，所以我们要求出所有满足的来比较最大值，我们可以考虑使用线性筛来求出所有的质数然后前缀和来求解即可

vector<int> primes;
int cnt;

void solve(){
   
    cin>>n;
    
    vector<LL> a(n+5);
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    
    auto get = [&](){
    	vector<bool> st(n+5);
    	for(int i=2;i<=n;i++){
    		if(!st[i]){
    			primes.push_back(i);
    			cnt++;
    		}
    		for(int j=0;primes[j]<=n/i;j++){
    			st[i*primes[j]]=true;
    			if(i%primes[j]==0) break;
    		}
    	}
    };
    
    get();
    LL ans=-1e18;// 注意初始化防止过小
   	for(int i=1;i<=n;i++){
   		for(auto&v:primes){
   			if(i<v) break;
   			ans=max(ans,a[i]-a[i-v]);
   		}
   	}
   	
   	cout<<ans<<endl;
    return ;
}

4.合并石子加强版

首先我们不要直接先入为主认为是区间dp，区间dp的时间复杂度一般是 $n^3$ 也不现实，我们接着找是不是具有什么性质找最简模型

a b c ->

1: 先左后右 a*b+(a+b)*c = a*b+a*c+b*c

2: 先右后左 b*c+(b+c)*a = a*b+a*c+b*c

我们可以发现无论左右结果不会变的那么也就是我们这个结果是不受操作所影响的，所以我们选择最优的操作直接从左到右即可，注意数据范围很大所以我们考虑要使用__int128来处理

void solve(){
   
    cin>>n;
    
    vector<LL> a(n+5);
    
    __int128 res=0;
    
    for(int i=1;i<=n;i++) cin>>a[i];
    
    LL pre=a[1];
    for(int i=2;i<=n;i++){
    	res+=a[i]*pre;
    	pre+=a[i];
    }
    
    function<void(__int128)> print = [&](__int128 res){
    	if(res>9) print(res/10);
    	putchar(res%10+'0');
    };
    
    print(res);
    return ;
}

5.简单的LIS问题

题目意思很简单修改一个数然后为 $0-10^{100}$ 然后求最长上升子序列，我们可以发现数据范围是

3e3可以使用 $n^2$ 的 $LIS$ 接着就是找一个数修改我们明显的可以划分为前面和后面来区别，所以

我们求一个前面的最长上升子序列，倒着求一个最长下降子序列拼接，接着考虑单独的最长子序列操作，对于上升子序列把后面的一个数改成比自己大即可，对于改前面的数就需要注意是不是>0(题目特殊限制)

void solve(){
   
    cin>>n;
    vector<int> a(n+5),dp1(n+5,1),dp2(n+5,1);
    
    for(int i=1;i<=n;i++) cin>>a[i];
    
    for(int i=1;i<=n;i++)
    	for(int j=1;j<i;j++)
    		if(a[j]<a[i]) dp1[i]=max(dp1[i],dp1[j]+1);
    
    for(int i=n;i>=1;i--)
    	for(int j=n;j>i;j--)
    		if(a[i]<a[j]) dp2[i]=max(dp2[i],dp2[j]+1);
    
    int ans=dp1[n];
    for(int i=1;i<=n;i++){
    	for(int j=i+2;j<=n;j++){
    		if(a[i]<=a[j]-2){
    			ans=max(ans,dp1[i]+dp2[j]+1);
    		}
    	}
    	if(i!=n) ans=max(ans,dp1[i]+1);
    	if(i!=1 && a[i]!=0) ans=max(ans,dp2[i]+1);
    }
    
    cout<<ans<<endl;
    	
    
    return ;
}

考虑提升数据范围就使用nlogn同时需要存在来这个时候的最大或者最小值以及数量

void solve(){
   
    cin>>n;
    
    vector<int> a(n),A(n),B(n),cp(n),cl(n);
    
    for(auto&v:a) cin>>v;
   
    vector<int> pre,last;
    
    for(int i=0;i<n;i++){
        int v=a[i];
        if(pre.empty()||v>pre.back()) pre.push_back(v);
        else pre[lower_bound(pre.begin(),pre.end(),v)-pre.begin()]=v;
        A[i]=pre.back();// 表示到这个点的时候的最大值是多少
        cp[i]=pre.size();// 表示到这个点的时候最长上升子序列的长度都是多少
    }
    
    reverse(a.begin(),a.end());
    
    int ans=pre.size();
    
    for(int i=0;i<n;i++){
        int v=a[i];
        if(last.empty()||v<last.back()) last.push_back(v);
        else last[lower_bound(last.begin(),last.end(),v,greater<int>())-last.begin()]=v;
        B[n-i-1]=last.back();//表示到这个点的最小值是多少
        cl[n-i-1]=last.size();// 表示这个点的长度是多少
    }
    
    
    for(int i=0;i<n-1;i++){
        if(i && A[i-1]<=B[i+1]-2){
            ans=max(ans,cp[i-1]+cl[i+1]+1);
        }
        ans=max(ans,cp[i]+1);
        if(i && B[i]!=0) ans=max(ans,cl[i]+1);
    }
    
    cout<<ans<<endl;
    return ;
}

6.期望次数

我们可以知道和是一个概率dp，依照题目意思我们定义状态为当前为x是期望为dp[x](x==i)

1.当i>=m 时 dp[i]=0;

2.当i<m时 $dp[i]=1+frac{sum_{j=1}^{n} a_j * dp[i*j](i*j<m))}{sum}$

进行变形之后得到答案 $dp[i]=frac{(sum+sum_{j=1}^{n}a_j*dp[i*j](i*j<m)))}{sum-a[1]}$

其中sum是 $a_i$ 之和，接着就可以按照公式倒着递推即可(注意逆元之类的操作)

LL qmi(LL a,LL b,LL p){
	LL res=1;
	while(b){
		if(b&1) res=res*a%p;
		b>>=1;
		a=a*a%p;
	}
	return res;
}

LL inv(LL x){
	return qmi(x,mod-2,mod);
}

void solve(){
   
    cin>>n>>m;
    vector<LL> dp(m);
    vector<int> a(n);
    LL sum=0;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    for(int i=m-1;i>=1;i--){
    	for(int j=2;j<=n&&i*j<m;j++){
    		dp[i]+=a[j]*dp[i*j];
    		dp[i]%=mod;
    	}
    	(dp[i]+=sum)%mod;
    	dp[i]=dp[i]*inv(sum-a[1])%mod;
    } 
    cout<<dp[1]<<endl;
    return ;
}

原文地址:https://blog.csdn.net/qq_73575281/article/details/135942967

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_65295.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。