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

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

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


前言

       这段时间我会把蓝桥杯官网上的所有非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个月回忆一下你真正的认真刷过题吗,如果你真的用尽所有的精力去努力了,那么我相信你最终的成绩一定会让你满意的,加油。


相关文章
|
6月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
107 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1007 印章
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1007 印章
62 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1006 拿金币
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1006 拿金币
66 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1004 无聊的逗
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1004 无聊的逗
90 0
|
6月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
79 1
|
6月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
82 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
83 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
89 0
|
6月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
91 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
91 0