第十届蓝桥杯省赛真题_蓝桥杯计算思维真题

前五道结果填空，后五道编程题

目录

前五道结果填空，后五道编程题

A:组队

B:不同子串

C:数列求值

D:数的分解

 E:迷宫

F:特别数的和

输入描述

输出描述

输入输出样例

G:外卖店优先级

输入描述

输出描述

输入输出样例

H:人物相关性分析

I:后缀表达式

J:灵能传输

---

A:组队

作为篮球队教练，你需要从以下名单中选出 1号位至 5 号位各一名球员，组成球队的首发阵容。

每位球员担任 1号位至 5号位时的评分如下表所示。请你计算首发阵容 1号位至 5 号位的评分之和最大可能是多少？

 

可以用肉眼看计算，或者暴力的查找一下，答案就是460

B:不同子串

一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成的串。例如，字符串 aaab有非空子串 a, b, aa, ab, aaa, aab, aaab，一共 7 个。注意在计算时，只算本质不同的串的个数。

请问，字符串 0100110001010001 有多少个不同的非空子串？

这个的话，也是直接暴力，把所有的子串都找出来，而且TreeSet是不会添加重复结构的，所以就直接利用，得出长度即是答案100

 
String str="0100110001010001";
Set<String> set=new TreeSet<>();
int length=str.length();
for(int i=0;i<length;i++) {
	for(int j=i+1;j<=length;j++) {
		String str2=str.substring(i, j);
//注意这个函数 左闭右开  而且当start与end相同的时候是一个空
		System.out.println("str2----"+str2);
		set.add(str2);
	}
}
/*
for(String s:set) {//看一下所有的结构
	System.out.println(s);
}*/
System.out.println(set.size());

C:数列求值

给定数列 1,1,1,3,5,9,17,⋯从第 4项开始，每项都是前 3 项的和。

求第 20190324 项的最后 444 位数字。

这道题。。题意就是题意。。。只不过想要计算到20190324确实是一个非常非常大的数，一般情况下都是计算不到的，得出的不会是我们想要的结果。通过题意可以知道，我们只需要后4位，而且是求和，就意味着前面的任何数字对后面都没有什么影响，所有只要后四位参与运算就行了

	int a1=1;
        int a2=1;
        int a3=1;
        int a=0;
        for(int i=4;i<=20190324;i++){
          a=(a1+a2+a3)%10000;
          a1=a2;
          a2=a3;
          a3=a;
          ;
 
        }
        
        System.out.println(a);
        System.out.println("4659");

D:数的分解

把 2019分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2和 4，一共有多少种不同的分解方法？

注意交换 333 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。

这道题的话，要保证三个数和为2019，并且不含‘2’‘4’，都比较好实现，唯一关键的一点是要保持没有因为顺序而导致的重复，思路在代码。

public static void main(String[] args) {
	int count=0;
	for(int i=1;i<2018;i++) {
		for(int j=i+1;j<1009;j++) {//让i和j之间保持没有顺序重复
			int p=2019-i-j;
			if(p>j&&panduan(i)&&panduan(j)&&panduan(p)) {
				//需要让p大于j 可以保证没有p和j的顺序导致的重复
				count++;
				}
				
				
			}
		}
		System.out.println(count);
}
	//检查是否有数字2 和 4
public static boolean panduan(int num) {
	String str=""+num;
	boolean flag1= str.contains("2");
	boolean flag2= str.contains("4");
	if(flag1||flag2) {//有一个包含就会返回false
		return false;
	}else {
		return true;
	}
	
}

 E:迷宫

F:特别数的和

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入描述

输入格式：

输入一行包含两个整数 n（1≤n≤10^4）。

输出描述

输出一行，包含一个整数，表示满足条件的数的和。

输入输出样例

示例

输入

40

输出

574

难度又从峰值掉下来了，本题也是暴力直接做

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
		int n=scan.nextInt();
		int count=0;
		for(int i=1;i<=n;i++) {
			if(panduan(i)) {
				count+=i;
				
			}
		}
		System.out.println(count);
		
        scan.close();
	}
	//是否包含2 0 1 9
	public static boolean panduan(int num) {
		String str=""+num;
		if(str.contains("2")||str.contains("0")||str.contains("1")||str.contains("9")) {
			return true;
		}
		
		return false;
		
	}

G:外卖店优先级

"饱了么"外卖系统中维护着 N家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T时刻时有多少外卖店在优 先缓存中?

输入描述

第一行包含 3 个整数 N,M,T。

以下 M 行每行包含两个整数 ts,id，表示 ts时刻编号 id的外卖店收到一个订单。

其中，1≤N,M,T≤105，1≤ts≤T，1≤id≤N

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

输出

1

样例解释：

6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6， 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。

这道题也是差不多暴力的情况，主要的问题是怎么去存储数据使用数据，但是有点耗时间了，如果都用int[]的话应该也能做int[][]，逻辑都在代码里

public static void main(String[] args) {
	        Scanner scan = new Scanner(System.in);
	        int N=scan.nextInt();//N家店
	        int M=scan.nextInt();//M条信息
		int T=scan.nextInt();//T个时刻
		int count=0;
		//key 家店的情况
		Map<Integer,ArrayList<Integer>> map=new HashMap<>();
		for(int i=1;i<=M;i++) {//记录M条信息
			int ts=scan.nextInt();//时刻
			int id=scan.nextInt();//店id
			if(map.containsKey(id)) {//如果已有这家店的记录
				map.get(id).add(ts);//允许重复
				
			}else {//如果没有这个店的记录的话 需要初始化一下
				ArrayList<Integer> list=new ArrayList<>();
				list.add(ts);
				map.put(id, list);
			}
		}
		//System.out.println(map);//检查信息是否正确
		int num=0;//记录最终结果
		for(Integer dian:map.keySet()) {//遍历所有店
			int[] jilu=new int[T+1];//用于记录一家店所有时刻的情况
			for(int i=0;i<map.get(dian).size();i++) {
				Integer t=map.get(dian).get(i);
				jilu[t]+=1;//包括记录一个时刻有多个订单的情况
			}
			int jishu=0;//优先级数
			boolean flag=false;//是否是优先
			for(int i:jilu) {
				if(i>0) {//有订单
					jishu+=2*i;
					if(jishu>5) {
						flag=true;
					}
				}else {//没有
					jishu--;
					if(jishu<=3) {
						flag=false;
					}
					if(jishu<0) {//不能减到0以下
						jishu=0;
					}
				}
			}
			if(flag) {
				num++;
			}
			
		}
		System.out.println(num);
		
        scan.close();
	}
 

（代码贴到这里都tab都岔开的厉害）

H:人物相关性分析

I:后缀表达式

给定 N个加号、M 个减号以及 N+M+1 个整数 A_1,A_2,··· ,A_{N+M+1}小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1个整数凑出的合法的 后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用 1 2 3 + -，则 "2 3 + 1 -" 这个后缀表达式结果是 4，是最大的。

输入描述

第一行包含两个整数 N,M

第二行包含 N+M+1 个整数 A_1,A_2,··· ,A_{N+M+1}。

其中，0≤N,M≤105，−109≤Ai≤1090。

输出描述

输出一个整，代表答案。

输入输出样例

示例

输入

1 1
1 2 3

输出

4

这道题主要的难点在判断各种组成的情况，数据的情况，安排的情况。。。。后缀表达式只是一个添头了。。。。后缀表达式可以看力扣150题。

 public static void main(String[] args) {
        int m,n;
        Scanner scanner=new Scanner(System.in);
        m=scanner.nextInt();
        n=scanner.nextInt();
        boolean x=false,y=false;//判断正负数是否存在
        int length=m+n+1;
        int[] a=new int[length];
        a[0]=scanner.nextInt();//第一个数
        int max=a[0];
        int min=a[0];
        if(a[0]>0) x=true;
        else if(a[0]<0) y=true;
        for(int i=1;i<length;i++) {
            a[i]=scanner.nextInt();
            if(min>a[i]) min=a[i];
            if(max<a[i]) max=a[i];
            if(a[i]>0) x=true;
            else if(a[i]<0) y=true;
        }
        long num=0;
        if(n==0) {//-号个数为0，所有数之和
            for(int i=0;i<length;i++)
                num+=a[i];
        }
        else if(m==0) {//+号个数为0
            if(x&&y) {//正负数都存在
                for(int i=0;i<length;i++)
                num+=Math.abs(a[i]);
            }
            else if(x&&!y) {//全正数
                for(int i=0;i<length;i++)
                    num+=a[i];
                num=num-2*min;
            }
            else if(!x&&y) {//全负数
                for(int i=0;i<length;i++)
                    num-=a[i];
                num=num+2*max;
            }
        }
        else {//有+、-号
            if(x&&y) {//正负数都存在
                for(int i=0;i<length;i++)
                num+=Math.abs(a[i]);
            }
            else if(x&&!y) {//全正数
                for(int i=0;i<length;i++)
                    num+=a[i];
                num=num-2*min;
            }
            else if(!x&&y) {//全负数
                for(int i=0;i<length;i++)
                    num-=a[i];
                num=num+2*max;
            }
        }
        System.out.println(num);
    }

J:灵能传输