蓝桥杯真题6

左手的ㄟ右手 2024-03-24 17:10 90阅读 0赞

### 三角回文数 ###

### 问题描述 ###

对于正整数 n, 如果存在正整数 k 使得 n=1+2+3+⋯+k=k(k+1)/2, 则 n 称为三角数。例如, 66066 是一个三角数, 因为 66066=1+2+3+⋯+363 。

如果一个整数从左到右读出所有数位上的数字, 与从右到左读出所有数位 上的数字是一样的, 则称这个数为回文数。例如, 66066 是一个回文数, 8778 也是一个回文数。

如果一个整数 n 既是三角数又是回文数, 我们称它为三角回文数。例如 66066 是三角回文数。

请问, 第一个大于 20220514 的三角回文数是多少?

### 答案提交 ###

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

运行限制  
最大运行时间：1s  
最大运行内存: 256M

### 分析 ###

直接暴力枚举即可，判断是否回文和是否是三角数

### 代码实现 ###

package com.zxy.exam;
    
    public class _三角回文数 {
        
        public static void main(String[] args) {
        
            int i = 20220514;
            while(true){
        
                if(isHUIWEN(i) && isSANJIAO(i)){
        
                    System.out.println(i);
                    break;
                }
                i++;
            }
        }
        public static boolean isSANJIAO(int n){
        
            int k = (int)Math.sqrt(2*n)-1;
            while(k*(k+1)<= 2*n){
        
                if(k*(k+1)==2*n){
        
                    return true;
                }
                k++;
            }
            return false;
        }
        public static boolean isHUIWEN(int n){
        
            char[] a = (n+"").toCharArray();
            int l = 0;
            int r = a.length-1;
            while(l <= r){
        
                if(a[l]!=a[r]) return false;
                l++;
                r--;
            }
    
            return true;
        }
    }

### 题目描述 ###

小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。

一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 xx 天的巧克力。

### 输入格式 ###

输入的第一行包含两个整数 xx，nn，分别表示需要吃巧克力的天数和巧克力的种类数。

接下来 nn 行描述货架上的巧克力，其中第 ii 行包含三个整数 aiai，bibi，cici，表示第 ii 种巧克力的单价为 aiai，保质期还剩 bibi 天（从现在开始的 bibi 天可以吃），数量为 cici。

### 输出格式 ###

输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 xx 天的购买方案，输出 −1−1。

### 输入输出样例 ###

输入 \#1

10 3  
1 6 5  
2 7 3  
3 10 10  
输出 \#1

18  
说明/提示

### 【样例说明】 ###

一种最佳的方案是第 11 种买 55 块，第 22 种买 22 块，第 33 种买 33 块。前 55 天吃第 11 种，第 66、77 天吃第 22 种，第 88 至 1010 天吃第 33 种。

### 代码与思路 ###

import java.io.*;
    import java.util.*;
    public class 巧克力_优先队列 {
        
        static PrintWriter out = new PrintWriter(System.out);
        static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in = new StreamTokenizer(ins);
     
     
        static class Node implements Comparable<Node> {
        
            int id;
            int price_a;
            int day_b;
            int number_c;
     
            Node(int id, int price_a, int day_b, int number_c) {
        
                this.id = id;
                this.price_a = price_a;
                this.day_b = day_b;
                this.number_c = number_c;
            }
     
            //按保质期从高到低进行排序
            @Override
            public int compareTo(Node o) {
        
                if (o.day_b > this.day_b) {
        
                    return 1;
                } else {
        
                    return -1;
                }
            }
        }
        static class Node1  {
        
            int id;
            int price_a;
            int day_b;
            int number_c;
     
            Node1(int id, int price_a, int day_b, int number_c) {
        
                this.id = id;
                this.price_a = price_a;
                this.day_b = day_b;
                this.number_c = number_c;
            }
        }
     
        public static void main(String[] args) throws IOException {
        
            String[] sp = ins.readLine().split(" ");
            int x = Integer.parseInt(sp[0]);
            int n = Integer.parseInt(sp[1]);
            Node[] nodes = new Node[n];
            int[] nums = new int[n];
            long ans = 0;
            for (int i = 0; i < n; i++) {
        
                String[] sp1 = ins.readLine().split(" ");
                nodes[i] = new Node(i, Integer.parseInt(sp1[0]), Integer.parseInt(sp1[1]), Integer.parseInt(sp1[2]));
            }
            //按保质期从高到低进行排序
            Arrays.sort(nodes);
            int j = 0;
    //        Prio<Node1> priority_queue = new LinkedList<>();
            PriorityQueue<Node1>priority_queue=new PriorityQueue<>(
                    new Comparator<Node1>() {
        
                        @Override
                        public int compare(Node1 o1, Node1 o2) {
        
                            return o1.price_a-o2.price_a;
                        }
                    }
            );
            for (int i = x; i >= 1; i--) {
        
                while (j < n && nodes[j].day_b >= i) {
        
                    priority_queue.offer(new Node1(nodes[j].id,nodes[j].price_a,nodes[j].day_b,nodes[j].number_c));
                    j++;
                }
                //如果出现空队列表示没有选择了
                if (priority_queue.size() == 0) {
        
                    out.println(ans);
                    out.println(-1);
                    out.flush();
                    return;
                }
                Node1 node = priority_queue.peek();
                //表示当前id的物品个数+1
                nums[node.id]++;
    //            System.out.println("id："+node.id+"价格："+node.price_a+"购买数量："+nums[node.id]);
                //加上当前物品的价格
                ans += node.price_a;
                //表示当前物品全部选完了
                if (node.number_c == nums[node.id]) {
        
    //                System.out.println("物品id:"+node.id+"出队");
                    //当前种类的物品已经全部选完了，所以当前物品出队
                    priority_queue.poll();
                }
            }
            out.println(ans);
            out.flush();
        }
    }

## \[蓝桥杯 2017 省 B\] k 倍区间 ##

### 题目描述 ###

给定一个长度为  N N N 的数列， A 1 , A 2 , ⋯ A N A\_1,A\_2, \\cdots A\_N A1,A2,⋯AN，如果其中一段连续的子序列  A i , A i + 1 , ⋯ A j ( i ≤ j ) A\_i,A\_\{i+1\}, \\cdots A\_j(i \\le j) Ai,Ai\+1,⋯Aj(i≤j) 之和是  K K K 的倍数，我们就称这个区间  \[ i , j \] \[i,j\] \[i,j\] 是  K K K 倍区间。

你能求出数列中总共有多少个  K K K 倍区间吗？

### 输入格式 ###

第一行包含两个整数  N N N 和  K K K ( 1 ≤ N , K ≤ 1 0 5 ) (1 \\le N,K \\le 10^5) (1≤N,K≤105)。

以下  N N N 行每行包含一个整数  A i A\_i Ai ( 1 ≤ A i ≤ 1 0 5 ) (1 \\le A\_i \\le 10^5) (1≤Ai≤105)。

### 输出格式 ###

输出一个整数，代表  K K K 倍区间的数目。

### 样例 \#1 ###

#### 样例输入 \#1 ####

5 2
    1  
    2  
    3  
    4  
    5

#### 样例输出 \#1 ####

### 提示 ###

时限 2 秒, 256M。蓝桥杯 2017 年第八届

### 分析 ###

题目很简单，我的第一反应就是暴力，直接双重循环枚举左右区间

import java.util.*;
    public class Main{
        
        static int res;
        public static void main(String[] args){
        
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int k = scan.nextInt();
            int[] a = new int[n+1];
            for(int i = 0;i<n;i++){
        
                a[i]=scan.nextInt();
            }
            for(int i = 0;i<n;i++){
        
                int q = 0;
                for(int j=i;j<n;j++){
        
                    q+=a[j];
                    if(q%k==0) res++;
                }
            }
            System.out.println(res);
        }
    }

代码没啥问题，但会超时，

我们考虑优化，区间和问题，自然想到的就是前缀和，借此可以优化一维，但是如果就仅仅优化这个还是不够的，依旧会超时，这我们就不得不思考一种新的方法来判断是否满足K倍区间，根据**同余定理** ，因此有如下思路

已知a<b，suma，sumb分别为a，b的前缀和（从序列第一个数到它自身的所有数之和），且suma%k=x，sumb%k=x。那么可得（sumb-suma）%k=0。即由b-a产生的区间c，一定为一个k倍区间

那么我们就可以将前缀和模k的值为0，1，2…k-1的区间数分别求出来，然后分别计算。

import java.util.Scanner;
    
    public class Main {
        
        // 后面用不到原数列，所以只存储前缀和
        public static int[] sum = new int[100005];
        // 用来统计相同余数的的个数
        public static long[] remainder = new long[100005];
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            long ans = 0;
            // 前0项和是0，注意余数为0开始就出现一次
            remainder[0] = 1;
            int n = sc.nextInt();
            int k = sc.nextInt();
            for (int i = 1; i <= n; i++) {
        
                int num = sc.nextInt();
                sum[i] = sum[i - 1] + num;
                remainder[sum[i] % k]++;
            }
            sc.close();
            for (int i = 0; i < k; i++)
                ans += (remainder[i] * (remainder[i] - 1)) >> 1;
            System.out.println(ans);
        }
    }