三角回文数

问题描述

对于正整数 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;}//按保质期从高到低进行排序@Overridepublic 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>() {@Overridepublic 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的物品个数+1nums[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$ 的数列，A1,A2,⋯ANA_1,A_2, \\cdots A_NA1​,A2​,⋯AN​，如果其中一段连续的子序列 Ai,Ai+1,⋯Aj(i≤j)A_i,A_{i+1}, \\cdots A_j(i \\le j)Ai​,Ai+1​,⋯Aj​(i≤j) 之和是 $K$ 的倍数，我们就称这个区间 $[i,j]$ 是 $K$ 倍区间。

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

输入格式

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

以下 $N$ 行每行包含一个整数 AiA_iAi​(1≤Ai≤105)(1 \\le A_i \\le 10^5)(1≤Ai​≤105)。

输出格式

输出一个整数，代表 $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);}
}