第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物

举报
红目香薰 发表于 2023/02/21 18:39:32 2023/02/21
【摘要】 ​ ​编辑第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物目录第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物前言关于数学的疑问算法训练 礼物C语言C++语言Java语言Python语言总结第六届——第十三届省赛题解第六届——第十二届国赛题解前言        这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都...

​

 ​编辑

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物

目录

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物

前言

关于数学的疑问

算法训练 礼物

C语言

C++语言

Java语言

Python语言

总结

第六届——第十三届省赛题解

第六届——第十二届国赛题解


前言

        这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。

关于数学的疑问

蓝桥杯中涉及到的数学说多不多，说少也不少，这里罗列了一下能用到的，其中红色的是【大学C组】会使用到的

1、简单数学(基础运算)

2、位运算

3、线性代数

4、离散数学(组合数学)

5、初等数论(整数的性质)

6、概率论

7、几何

虽然看到了线性代数、离散数学、初等数论，但是对于C组来说不会考的太复杂，会基础就好。

算法训练 礼物

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　JiaoShou在爱琳大陆的旅行完毕，即将回家，为了纪念这次旅行，他决定带回一些礼物给好朋友。
　　在走出了怪物森林以后，JiaoShou看到了排成一排的N个石子。
　　这些石子很漂亮，JiaoShou决定以此为礼物。
　　但是这N个石子被施加了一种特殊的魔法。
　　如果要取走石子，必须按照以下的规则去取。
　　每次必须取连续的2*K个石子，并且满足前K个石子的重量和小于等于S，后K个石子的重量和小于等于S。
　　由于时间紧迫，Jiaoshou只能取一次。
　　现在JiaoShou找到了聪明的你，问他最多可以带走多少个石子。

输入格式

　　第一行两个整数N、S。
　　第二行N个整数，用空格隔开，表示每个石子的重量。

输出格式

　　第一行输出一个数表示JiaoShou最多能取走多少个石子。

样列输入

8 3
1 1 1 1 1 1 1 1

样列输出

6

样列解释

任意选择连续的6个1即可。

数据规模和约定

　　对于20%的数据：N<=1000
　　对于70%的数据：N<=100,000
　　对于100%的数据：N<=1000,000，S<=10^12，每个石子的重量小于等于10^9，且非负

题解：

C语言

#include<stdio.h> 
long long maxlen=0;//最大石子个数的一半
long long n,s;
long long arr[1000005];
long long sum[1000005];
int main(){ 
	scanf("%lld%lld",&n,&s);
	int i;
	for(i=1;i<=n;i++){
		scanf("%lld",&arr[i]);
		sum[i]=arr[i]+sum[i-1];
	}
	maxlen=1;
	 i=1;//起始石子的编号
	while(i<=n&&i+maxlen*2-1<=n){
		if(sum[i+maxlen-1]-sum[i-1]<=s&&sum[i+2*maxlen-1]-sum[i+maxlen-1]<=s)
		maxlen++;
		else
		i++;
	}
	maxlen--;
	printf("%lld",maxlen*2);
	return 0;
}

C++语言

#include<stdio.h> 
long long maxlen=0;//最大石子个数的一半
long long n,s;
long long arr[1000005];
long long sum[1000005];
int main(){ 
	scanf("%lld%lld",&n,&s);
	int i;
	for(i=1;i<=n;i++){
		scanf("%lld",&arr[i]);
		sum[i]=arr[i]+sum[i-1];
	}
	maxlen=1;
	 i=1;//起始石子的编号
	while(i<=n&&i+maxlen*2-1<=n){
		if(sum[i+maxlen-1]-sum[i-1]<=s&&sum[i+2*maxlen-1]-sum[i+maxlen-1]<=s)
		maxlen++;
		else
		i++;
	}
	maxlen--;
	printf("%lld",maxlen*2);
	return 0;
}

Java语言

在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。只是相对的录入速度快于Scanner这样在整体运算的过程中可以适当节约时间。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;

public class Main
{
    private static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    private static StreamTokenizer tokenizer = new StreamTokenizer(br);
    private static Integer nextInt()
    {
        try {
            tokenizer.nextToken();
            if(tokenizer.ttype == StreamTokenizer.TT_EOF)
            {
                return null;
            }
            if(tokenizer.ttype == StreamTokenizer.TT_NUMBER)
            {
                return (int)tokenizer.nval;
            }
            if(tokenizer.ttype == StreamTokenizer.TT_WORD)
            {
                return Integer.valueOf(tokenizer.sval);
            }
        }catch (IOException e)
        {
            e.printStackTrace();
        }
        return null;
    }
    private static Long nextLong()
    {
        try {
            tokenizer.nextToken();
            if(tokenizer.ttype == StreamTokenizer.TT_EOF)
            {
                return null;
            }
            if(tokenizer.ttype == StreamTokenizer.TT_NUMBER)
            {
                return (long)tokenizer.nval;
            }
            if(tokenizer.ttype == StreamTokenizer.TT_WORD)
            {
                return Long.valueOf(tokenizer.sval);
            }
        }catch (IOException e)
        {
            e.printStackTrace();
        }
        return null;
    }
    public static void main(String[] args)
    {
        int N=nextInt();
        long S=nextLong();
        long total=0;
        long[] sum=new long[N+1];
        sum[0]=0;
        for(int i=1;i<=N;i++)
        {
            int temp=nextInt();
            total+=temp;
            sum[i]=total;
        }
        int mid;
        int left=1,right= N/2;
        int ans=0;
        while (left<=right)
        {
            mid=(left+right)/2;
            boolean hasAns=false;
            for(int i=mid;i<=N-mid;i++){
                if(sum[i]-sum[i-mid]<=S&&sum[i+mid]-sum[i]<=S){//当答案存在时 返回true
                    ans=mid*2;
                    hasAns=true;
                    break;
                }
            }
            if(hasAns)
            {
                left=mid+1;
            }
            else
            {
                right=mid-1;
            }
        }
        System.out.println(ans);
    }
}

Python语言

相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。

def main():
    nums=list(map(int,input().split()))
    n,s=nums[0],nums[1]
    weights=list(map(int,input().split()))
    if n==1:
        print(1)
        return
    left=0
    right=1
    res=0
    sum1=weights[0]
    sum2=weights[1]
    while right<n:
        if sum1<=s and sum2<=s:
            if res<right-left:
                res=right-left
            if right+2>=n:
                break
            sum1 += weights[(left + right) // 2 + 1]
            sum2 -= weights[(left + right) // 2 + 1]
            right+=2
            sum2+=weights[right]+weights[right-1]
        else:
            left+=1
            right+=1
            if right==n:
                break
            sum1+=weights[(left+right)//2]
            sum1-=weights[left-1]
            sum2-=weights[(left+right)//2]
            sum2+=weights[right]
    print(res+1)
if __name__=="__main__":
    main()

总结

没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。

第六届——第十三届省赛题解

所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。

第六届Java省赛C组 https://laoshifu.blog.csdn.net/article/details/123284163
第七届Java省赛C组 https://laoshifu.blog.csdn.net/article/details/123285783
第八届Java省赛C组 https://laoshifu.blog.csdn.net/article/details/123302677
第九届Java省赛C组 https://laoshifu.blog.csdn.net/article/details/123303285
第十届Java省赛C组 https://laoshifu.blog.csdn.net/article/details/123319090
第十一届Java省赛C组 https://laoshifu.blog.csdn.net/article/details/123320205
第十二届Java省赛C组第一套 https://laoshifu.blog.csdn.net/article/details/123413141
第十二届Java省赛C组第二套 https://laoshifu.blog.csdn.net/article/details/123413271
第十三届Java省赛C组 https://laoshifu.blog.csdn.net/article/details/128891276

第六届——第十二届国赛题解

所有题目均有题解，部分第10题非最优解，至少跑20%数据。

第六届Java国赛C组 https://laoshifu.blog.csdn.net/article/details/123440705
第七届Java国赛C组 https://laoshifu.blog.csdn.net/article/details/123442982
第八届Java国赛C组 https://laoshifu.blog.csdn.net/article/details/123443626
第九届Java国赛C组 https://laoshifu.blog.csdn.net/article/details/123443908
第十届Java国赛C组 https://laoshifu.blog.csdn.net/article/details/123444946
第十一届Java国赛C组 https://laoshifu.blog.csdn.net/article/details/123445601
第十二届Java国赛C组 https://laoshifu.blog.csdn.net/article/details/123446589

​

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
人工智能 数据结构 机器学习
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入