蓝桥杯真题6 左手的ㄟ右手 2024-03-24 17:10 24阅读 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 #### 6 ### 提示 ### 时限 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); } }
还没有评论,来说两句吧...