蓝桥杯
共识：代码提交题 没有思路优先想暴力 没有暴力思路先跳 去看后面的 （暴力都写不出来那就没办法咯）
2019蓝桥杯
2.不同字串：
3.数列求值
package lanqiaobei;import java.util.Scanner;public class yanhuisanjiao {public static void main(String[] args) {Scanner input=new Scanner(System.in);int a=1;int b=1;int c=1;//试了一下long也能爆，还是取摸吧//前面三项已经有了，从第四项开始for(int i=4;i<=20190324;i++){int temp=((a+b+c)%10000);a=b;b=c;//依次往后移c=temp;}System.out.println(c);}}
4.数的分解：
7.外卖优先级
算法思路：
由分析可知，如果我们可以建立一张店铺订单数量和时刻相关联的表，则可以很清楚的计算各时刻各店铺的优先级数。因而我们可以借助二维数组orderTable（店铺id为行，时刻t为列）来表示该表，然后遍历该数组并逐个计算各时刻下各店铺的优先级数，如果符合条件则加入map中并以店铺id为key值，若不符合条件则将其移出，最后查看map中有多少项，即可。
具体编码
public class waimaiyouxianji {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int shops = input.nextInt();//店铺数量
int orders = input.nextInt();//订单数量
int time = input.nextInt();//T时刻
int[][] orderTable = new int[shops+1][time+1];//存储各店铺各时刻的订单数量
int[] shopCounts = new int[shops+1];//T时刻，店铺的优先级数
HashMap<Integer,Integer> shopMap = new HashMap();//作为优先缓存
for (int i = 0; i < orders; i++) {
int ts = input.nextInt();//订单时刻
int id = input.nextInt();//接收订单的店铺
if(ts <= time){//在T时刻表中的订单状态
orderTable[id][ts]++;
}
}
for (int i = 1; i <= shops; i++) {
for (int j = 1; j <= time; j++) {
if(orderTable[i][j] == 0){
shopCounts[i] = Math.max(0,shopCounts[i] - 1);//当店铺i在j时刻，无订单且优先级数不为零时自减1
}else{
shopCounts[i] += orderTable[i][j] * 2;//当店铺i在j时刻，有订单则将此时刻该店铺的订单数量×2
}
//判断优先级数，确定是否加入优先缓存
if(shopCounts[i] > 5){//当店铺优先级数首次大于5时将其加入优先缓存中
shopMap.put(i,1);
}else if(shopCounts[i] <= 3 && shopMap.containsKey(i)){//当店铺已经加入到优先缓存且优先级数小于等于3时，剔除出去
shopMap.remove(i);
}
}
}
System.out.println(shopMap.size());//此时map的大小即为优先缓存中的店铺数量
}
}
8.人物相关性格分析
题目描述：
题解：
package lanqiaobei;
import java.util.Scanner;
public class renwuxiangguangxinggefenxi {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int k=sc.nextInt();
sc.nextLine();//？
String str=sc.nextLine();
//分割语句存放到words中
String[] words=str.split("\\s|\\.");
//System.out.println(Arrays.toString(words));
int[] wordslength=new int[words.length];
for (int i = 0; i < wordslength.length; i++) {
//将分割后每一个单词的长度存放到wordslength中
wordslength[i]=words[i].length();
}
int num=0;
//Alice---Bob
for (int i = 0; i < words.length; i++) {
//如果找到Alice
if(words[i].equals("Alice")){
for (int j = i+1; j < words.length; j++) {
//因为Alice后有一个空格而j从Alice后面一个单词开始所以sum=1
int sum=1;
if(words[j].equals("Bob")){
//将Alice和Bob之间的长度累加给sum
for (int l = i+1; l < j; l++) {
//每个长度+1是因为中间有空格或者.
sum+=wordslength[l]+1;
}
if(sum<k){
num++;
}
}
}
}
}
//Bob---Alice
//将上面代码cv一下判断条件Alice和Bob调换一下
for (int i = 0; i < words.length; i++) {
if(words[i].equals("Bob")){
for (int j = i+1; j < words.length; j++) {
int sum=1;
if(words[j].equals("Alice")){
for (int l = i+1; l < j; l++) {
sum+=wordslength[l]+1;
}
if(sum<k){
num++;
}
}
}
}
}
System.out.println(num);
}
}
9.后缀表达式
题目描述：
算法思路
在求解该题时，我们应该清楚一点，后缀表达式与前缀表达式在计算过程中是可以存在括号“（）”的。明确这一点后，我们就可以很清楚的找到结果最大的值，此值即为所有数值之和减去最小数值的两倍。举个例子帮大家理解一下：a+b-(c-d-e) = a+b-c+d+e = a+b+c+d+e-2*c，如果此时c为a、b、c、d、e中的最小值，那么此时的a+b-(c-d-e)显然为a、b、c、d、e与＋、-各组合结果中的最大结果。
题解：
package lanqiaobei;
import java.math.BigInteger;
import java.util.Scanner;
/*后缀表达式*/
public class houzhuibiaodashi {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();//n个加号
int m = input.nextInt();//m个减号
BigInteger sum = new BigInteger("0");//全部数值之和
BigInteger min = new BigInteger("1000000000");//定义一个最小变量，用于保存数值中最小的那个值
for (int i = 0; i < n+m+1; i++) {
BigInteger temp = new BigInteger(input.next());
sum = sum.add(temp);//求和
if(min.compareTo(temp) == 1){//min > temp，则修改min值
min = temp;
}
}
System.out.println(sum.subtract(min.multiply(new BigInteger("2"))));//全部数值之和减去2倍的最小数值
}
}
5.迷宫（题型需要练）
题目描述：
使用集合框架：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class migong {
public static void main(String args[]) {
// BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
migong migong = new migong();
migong.receiveData();
migong.bfs();
migong.print(migong.getPath());
}
// 坐标类
class P {
int x;
int y;
P(int x, int y) {
this.x = x;
this.y = y;
}
}
final int INF = 100000000;// 一个足够大的数，表示未访问
char[][] maze = new char[3][];// 表示迷宫的字符串数组
int N = 3, M = 3;
int sx = 0, sy = 0;// 起点坐标
int gx = 2, gy = 2;// 终点坐标
P[][] prev = new P[3][3];// 坐标x,y在路径上的前驱（前一个坐标）prev[x][y]
int[][] d = new int[3][3];// 到各个位置的最短距离的数组
int dx[] = { 1, 0, 0, -1 }, dy[] = { 0, -1, 1, 0 };// D,L,R,U 下，左，右，上 移动方向
// 接受数据
void receiveData() {
Scanner reader = new Scanner(System.in);
for (int i = 0; i < N; i++) {
maze[i] = reader.nextLine().toCharArray();
}
}
// 求从(sx,sy)到(gx,gy)的最短路径
void bfs() {
Queue<P> queue = new LinkedList<P>();
for (int i = 0; i < 3; i++) {// 初始化为INF
Arrays.fill(d[i], INF);
}
// 将起点加入队列，并将其最短距离设为0
queue.offer(new P(sx, sy));
d[sx][sy] = 0;
// 不断循环直到队列为空
while (!queue.isEmpty()) {
P p = queue.poll();// 取出队首元素并且再队列中删除此元素
if (p.x == gx && p.y == gy)
break;// 如果是终点，结束循环
// 四个方向的循环
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i], ny = p.y + dy[i];// 移动后的位置记为nx,ny
// 判断是否可以移动以及是否被访问过（d[nx][ny] == INF表示未被访问）
if (0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '1' && d[nx][ny] == INF) {
// 可以移动则加入队列，并且该坐标的最短距离为p的最短距离+1，该坐标的前驱为p
queue.offer(new P(nx, ny));
d[nx][ny] = d[p.x][p.y] + 1;
prev[nx][ny] = p;
}
}
// return d[gx][gy]; 如果要求最短路径长度，d[gx][gy]就是最短路径长度
}
}
// 到顶点t的最短路
ArrayList<P> getPath() {
P t = new P(gx, gy);
ArrayList<P> path = new ArrayList<P>();
for (; t != null; t = prev[t.x][t.y])
path.add(t); // 不断沿着t = prev[t.x][t.y]走直到t=起点
Collections.reverse(path);// 这样得到的是t到起点的顺序，所以翻转之
return path;
}
void print(ArrayList<P> path) {
P t = new P(sx, sy);
for (int i = 0; i < path.size(); i++) {
int xL = path.get(i).x - t.x, yL = path.get(i).y - t.y;// 求出移动方向
for (int j = 0; j < 4; j++) {
if (xL == dx[j] && yL == dy[j]) {// 方向匹配则输出
switch (j) {
case 0:
System.out.print('D');
break;
case 1:
System.out.print('L');
break;
case 2:
System.out.print('R');
break;
case 3:
System.out.print('U');
break;
}
}
}
t = path.get(i);
}
}
}
6.特别数的和
10.灵能传输（未写）
2020蓝桥杯
斐波那契数列的最大公约数
题目描述：
题解：为了防止数字越界 因此选取BigInteger 其可以取到无线大的数 因此不存在越界 重难点：熟记api
package lanqiaobei;
import java.math.BigDecimal;
import java.math.BigInteger;
import static java.awt.Event.F1;
/*斐波那契数列最大公约数*/
public class array {
public static void main(String[] args) {
BigInteger arr[] = new BigInteger[2021]; // int long型数据均会爆数组
arr[0] = BigInteger.ZERO;
arr[1] = arr[2] = BigInteger.ONE;
for (int i = 3; i <= 2020; i++) {
arr[i] = arr[i - 1].add(arr[i - 2]);
}
System.out.println(arr[520]);
System.out.println(arr[2020]);
System.out.println(arr[2020].gcd(arr[520]));
}
public static BigInteger gcd(BigInteger a, BigInteger b) {
return b.equals(BigInteger.ZERO) ? a : gcd(b, a.mod(b));
}
}
合并检测
题目描述：
方法一：
假设A国有n个人，感染者有n/100
每k个人一组，共n/k组，共用n/k瓶试剂
按照最坏的情况，每多出一个感染者就多用k瓶试剂，
因此共用n/k+(n/100)*k瓶试剂
n是定值，
所以求(1/k+k/100)最小
由于a+b>=2√ab
当且仅当a = b时，取等号
即1/k=k/100时，取得最小值
解得k = 10
方法二：
思路：假设法，假设A国只有100个人，然后k=1....100,求k在不同数字下耗费的最少
重点在于假设法
package lanqiaobei;
/*分组检测*/
public class sortCheck {
public static void main(String[] args) {
int min = 999990;
int ans = -1;
for (int i = 1; i <= 100; i++) { // i个人一块测
int temp;
if (100 % i != 0) {
temp = 100 / i + i + 1;
} else {
temp = 100 / i + i;
}
if (min > temp) {
min = temp;
ans = i;
}
}
System.out.println(ans);
}
}
分配口罩
题目描述：
思路：全排列
package lanqiaobei;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
public class 分配口罩 {
public static int res=Integer.MAX_VALUE;
public static int num[]={9090400, 8499400, 5926800, 8547000, 4958200,
4422600, 5751200, 4175600, 6309600, 5865200,
6604400, 4635000, 10663400, 8087200, 4554000
};
public static void main(String[] args){
dfs(0, 0, 0);
System.out.println(res);
}
public static void dfs(int k,int sum1,int sum2 ) {
if(k==15) {
res=res<Math.abs(sum1-sum2)?res:Math.abs(sum1-sum2);
return;
}
dfs(k+1, sum1+num[k], sum2);
dfs(k+1, sum1, sum2+num[k]);
}
}
这道题的核心，全排列+数字越界问题+深度优先搜索
分类计数（ac）
题目描述：
编码：
package lanqiaobei;
import java.util.Scanner;
public class Sortjishu {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int big=0;
int small=0;
int shuzi=0;
for (int i=0;i<s.length();i++){
if (s.charAt(i)>='a'&&s.charAt(i)<='z'){ //97-122
small++;
}
if (s.charAt(i)>='A'&&s.charAt(i)<='Z'){ // 65-90
big++;
}
if (s.charAt(i)>='0'&&s.charAt(i)<='9'){ //48-57
shuzi++;
}
}
System.out.println(big);
System.out.println(small);
System.out.println(shuzi);
}
}
这道题的核心：不用写出字符对应的asci码 直接用‘字符’来表示
八次求和
题目描述：
思路：
这个题想不出来可以混分，至少n属于（1-x）的情况是可以计算出来的 代码形式 if（n等于1）return x； if（n==2）return x；....
em…感觉这题有点歧义 因为没打括号
题解一：公式法
import java.math.BigInteger;
import java.util.Scanner;
public class sumForEight {
/*八次方求和*/
static long MOD = 123456789;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(get(n));
}
static BigInteger get(int m) {
//以下为公式：
//(1^8+2^8+3^8+...+n^8) = (10n^9+45n^8+60n^7-42n^5+20n^3-3n)/90
BigInteger n = BigInteger.valueOf(m); //记住api
BigInteger result = BigInteger.ZERO;
result = result.add(BigInteger.valueOf(10L).multiply(n.pow(9)));//记住api n.pow(9)表示n的9次方
result = result.add(BigInteger.valueOf(45L).multiply(n.pow(8)));
result = result.add(BigInteger.valueOf(60L).multiply(n.pow(7)));
result = result.subtract(BigInteger.valueOf(42L).multiply(n.pow(5)));//记住减法api
result = result.add(BigInteger.valueOf(20L).multiply(n.pow(3)));
result = result.subtract(BigInteger.valueOf(3L).multiply(n));
result = result.divide(BigInteger.valueOf(90L)); //记住除法api
result = result.mod(BigInteger.valueOf(123456789L));
return result;
}
}
题解二：熟练使用BigInteger各种方法
import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;
/*八次方求和*/
public class sumForEigth2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BigInteger Bigmod = BigInteger.valueOf(123456789);
BigInteger Bigsum = BigInteger.valueOf(0);
int n=sc.nextInt();
for(int i=1;i<=n;i++){
BigInteger c = BigInteger.valueOf(i);
Bigsum=Bigsum.add(c.multiply(c).multiply(c).multiply(c).multiply(c)
.multiply(c).multiply(c).multiply(c));
}
BigInteger sum = Bigsum.mod(Bigmod);
System.out.println(sum);
}
}
字符串编码（ac）
题目描述：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class StringEncord {
/*123242526-->LCXYZ*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] word = new char[27]; //将26个字母存储起来
for(int i=1;i<word.length;i++){
word[i]=(char)('A'+i-1);//注意点 char本身也需要加（）
}
List<Character> list = new ArrayList<>();
String s = sc.nextLine();
int n = s.length();
for (int i=0;i<n;){
char c = s.charAt(i);
if (c>='3'){
String s1 = c + "";
list.add(word[Integer.valueOf(s1)]);
i++;
}else if (c=='2'&&(i+1)<n&&s.charAt(i+1)<='6'){
char c1 = s.charAt(i+1);
String s1 = c + ""+c1;
list.add(word[Integer.valueOf(s1)]);
i=i+2;
}else if (c=='1'&&(i+1)<n){
char c1 = s.charAt(i+1);
String s1 = c + ""+c1;
list.add(word[Integer.valueOf(s1)]);
i=i+2;
}else {
String s1 = c + "";
list.add(word[Integer.valueOf(s1)]);
i++;
}
}
System.out.println(list);
}
}
/*
* ABCDEFGHIJKLMNOPQRSTUVWXYZ
*/
BST 插入节点问题
题目描述
题解：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class BST {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] parent = new int[n];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < n; i++) {
parent[i] = sc.nextInt();
map.put(i+1, sc.nextInt());
}
ArrayList<Integer> childs = new ArrayList<Integer>();
int rootWeight = map.get(1);
int kWeight = map.get(k);
for(int i = 0; i < parent.length; i++) {
if(k == parent[i]) childs.add(map.get(i+1));
}
// 1.parents不存在的节点就是叶子节点，叶子节点的答案是无穷大
if(childs.size() == 0) {
System.out.println("叶子节点");
System.out.println(-1);
return;
}
// 2. 已经有左右孩子，答案是0
else if(childs.size() == 2) {
System.out.println("已经有左右孩子了");
System.out.println(0);
return;
}
// 3. 在右子树：k节点有左无右时为-1;在左子树：k几点有右无左为-1
else if(childs.size() == 1 && (kWeight > rootWeight && childs.get(0) < kWeight) || (kWeight < rootWeight && childs.get(0) > kWeight)) {
System.out.println(-1);
return;
}
else {
int fatherWeight = map.get(parent[k-1]);
System.out.println(Math.abs(kWeight-fatherWeight)-1);
return;
}
}
}
网络分析（还没写）
2018蓝桥杯
复数幂（以小推大思维没有被建立起来）
题目描述
解题思路:
因为123456的幂次方，所以是一个大数，大数问题选择BigInteger和BigDecial（专门用来解决大数问题，前者用来解决大数整数，后置用来解决大数浮点数）
package 复数幂;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
BigInteger c = BigInteger.valueOf(2);
BigInteger d = BigInteger.valueOf(3);
BigInteger a = BigInteger.valueOf(2);
BigInteger b = BigInteger.valueOf(3);
//(a+bi)*(c+di) = (a*c - b*d) + (a*d + b*c)i
for(int i=1;i<2;i++) {
BigInteger A = a.multiply(c).subtract(b.multiply(d));//实部
BigInteger B = a.multiply(d).add(b.multiply(c));//虚部
a=A;//如果不设置临时变量，后面b的值会出错
b=B;
}
System.out.println(a.toString()+"+"+b.toString()+"i");
}else {
System.out.println(a.toString()+b.toString()+"i");
}
/* System.out.println(a.toString()+b.toString()+"i");*/
}
}
递增三元组（菜鸡多想想暴力）
题目描述：
题解：
反思一下：刚开始看这题的时候居然没想到用暴力for来解决，可能是写了太多不用暴力解决的题目，思维被固化了。蓝桥杯比赛的时候，看完题目记得优先往暴力for上靠，不要管时间空间复杂度，能通过多少用例拿多少分。
暴力题解: 只有75分
package 递增三元组;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int count=0; //用来计数
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();//每个数组的个数
int a[]=new int[n];
int b[]=new int[n];
int c[]=new int[n];
//初始化每个数组的值
for (int i=0;i<n;i++){
a[i]=scanner.nextInt();
}
for (int i=0;i<n;i++){
b[i]=scanner.nextInt();
}
for (int i=0;i<n;i++){
c[i]=scanner.nextInt();
}
//暴力法 三层for来解决 计数
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (a[i]>=b[j]){
continue;
}
for (int z=0;z<n;z++){
if (a[i]<b[j]&&b[j]<c[z]){
count++;
}
}
}
}
System.out.println(count);
}
}
优化： 只有87分
package 递增三元组;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
long count=0; //用来计数 要设置成long的 因为count可能很大
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();//每个数组的个数
int a[]=new int[n];
int b[]=new int[n];
int c[]=new int[n];
//初始化每个数组的值
for (int i=0;i<n;i++){
a[i]=scanner.nextInt();
}
for (int i=0;i<n;i++){
b[i]=scanner.nextInt();
}
for (int i=0;i<n;i++){
c[i]=scanner.nextInt();
}
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
int p=0;
int q=0;
for (int i=0;i<n;i++){
while (p<n&&a[p]<b[i])p++;
while (q<n&&c[q]<=b[i])q++;
count=count+p*(n-q);
}
System.out.println(count);
}
}
螺旋折线：
题目描述：
解题思路：做一条对角线，利用等差队列来算
package 螺旋折线;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
// 以 右下角 对角线上的点 为 参照点，测算给定的点到参照点要走的距离
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(System.in);
long X = sc.nextLong(), Y = sc.nextLong();
long d = 0; // 距离 举例最右下角的距离
long n = 0; // 第几圈
if (Y > 0 && Math.abs(X) <= Y) { // 点在上面的横线上
n = Y; // 等差数列有多少项? Y项
d = (Y - X) + (2 * Y); // X的最大值是Y,第一、四象限的距离---2Y
} else if (X > 0 && Math.abs(Y) <= X) { // 点在最右边的横线上
n = X;
d = Y + X;
} else if (Y <= 0 && X >= Y - 1 && X <= -Y) { // 点在最下边的横线上
n = -Y; //2
d = -(-Y - X);//-4
} else if (X < 0 && Y >= X + 1 && Y <= -X) { // 点在最左边的横线上
n = -X - 1;
d = -(Y - X - 1 - 2 * X - 1);
}
System.out.println(sum(2, 2 * n, 2) - d);
}
/**
* 等差数列求和
*
* @param a0 首项
* @param n 项数
* @param d 公差
* @return
*/
private static long sum(long a0, long n, int d) {
return n*a0+d*n*(n-1)/2;
}
}
2017蓝桥杯
1.购物单（ac）
解法：excel或者计算器
2.纸牌三角形（蛮难的）
题目描述：
思路：全排列
代码：
public class Solution {
static int count = 0;
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
dfs(arr, 0);
System.out.println(count / 6);
}
// 全排列
public static void dfs(int[] arr, int index) {
if (index == arr.length) {
// 已经够成一个了
int col = arr[0] + arr[1] + arr[3] + arr[5];
int row = arr[5] + arr[6] + arr[7] + arr[8];
int xie = arr[0] + arr[2] + arr[4] + arr[8];
if (col > 0 && col == row && row == xie) {
count++;
}
return;
}
for (int i = index; i < arr.length; i++) {
swap(arr, index, i);
dfs(arr, index + 1);
swap(arr, index, i);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
3.承重计数（半ac。拿不到分，但是可以拿到分）
题目描述
package 承压计算;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//30行30列的数组
double a[][]=new double [30][30];
//如果上面定义的数组类型为Double 不显示初始化的因为是引用类型 不赋值就是null 不是0了 而double就是0.0
// System.out.println(a[29][29]);
for(int i=0;i<29;i++) {
for(int j=0;j<=i;j++) {
a[i][j]=scanner.nextDouble();
}
}
//为了让最后一行得到值 不为null
/*for (int i=0;i<30;i++){
a[29][i]=0.0;
}*/
//类似杨辉三角
for(int i=1;i<=29;i++) {
for(int j=0;j<=i;j++) {
if(j==0) {
a[i][j]=a[i-1][j]/2+a[i][j];
}else if(j>0&&j<i) {
a[i][j]=a[i-1][j-1]/2+a[i-1][j]/2+a[i][j];
}else {
a[i][j]=a[i-1][j-1]/2+a[i][j];
}
}
}
double max=0.0;
double min=Double.MAX_VALUE;
//遍历最后一层 去一个最大的即可
for(int i=0;i<=29;i++) {
if(a[29][i]>max) {
max=a[29][i];
}
if(a[29][i]<min) {
min=a[29][i];
}
}
System.out.println(max);
System.out.println(min);
System.out.println((2086458231 * max)/ min);
}
}
5.取数位（ac）
题目描述
答案：f(x/10, k)
思路分析：
因为是补全代码，所以就大胆试嘛，示例中给的例子是x=23513，但这题无论x等于什么，貌似影响不太大。因此我们取x=13，k=1或者2来调试。这样一试，马上就能猜到答案了。再让x取一些较大的数和不同的k，发现都满足。因此答案就是f(x/10, k)
6.最长公共子串（ac）
7.日期问题（感觉写的出来，但是看了答案。该死）
题目描述
思路分析以及对api的分析
编码：
package quanpailie;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static HashSet<Integer> set = new HashSet<Integer>(); //去重
public static List<Integer> list =new ArrayList<Integer>();
public static void f(String year,String mon,String day)
{
int y = Integer.parseInt(year); //记住这个 0x会变成x
int m = Integer.parseInt(mon);
int d = Integer.parseInt(day);
if(y<=59)
{
y+=2000;
}else {
y+=1900;
}
//如果是闰年 2月
if(y/4==0&&m==2&&d<=29) {
set.add(Integer.parseInt(""+y+mon+day));
}
//平年二月
if(y/4!=0&&m==2&&d<=28) {
set.add(Integer.parseInt(""+y+mon+day));
}
//大月
if((m==1||m==3||m==5||m==7||m==8||m==10||m==12)&&d<=31) {
set.add(Integer.parseInt(""+y+mon+day));
}
//小月
if((m==4||m==6||m==9||m==11)&&d<=30) {
set.add(Integer.parseInt(""+y+mon+day));
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
String[] s =str.split("/");
f(s[0],s[1],s[2]);
f(s[2],s[0],s[1]);
f(s[2],s[1],s[0]);
list.addAll(set);
for(int i=0;i<list.size();i++)
{
String ans = ""+list.get(i);
System.out.println(ans.substring(0, 4)+"-"+ans.substring(4,6)+"-"+ans.substring(6,8));
}
}
}
8.包子凑数（dp问题，不太好想）
题目描述：
思路分析
先从他给的案例分析，分别是【4,5】和【4,6】，【4,6】的话一定拼不出来基数，因此有无穷个，同理都为偶数也肯定是无穷个。
package 包子凑数;
import java.util.Scanner;
public class 蓝桥杯_包子凑数 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int g=0;
boolean []dp=new boolean[10000];
dp[0]=true;
int[] a = new int[101];//因为n为[1-100]
for(int i=1;i<=n;i++) {
a[i] = sc.nextInt();
// 求所有ai的最大公约数
if(g==1) {
g=a[i];
}else {
g=gcd(a[i],g);
}
for(int j=0;j<10000-a[i];j++) {//貌似等于也不影响
if(dp[j]==true) {
dp[a[i]+j]=true;
}
}
}
if(g!=1) { //奇奇 偶偶都会使得g=1 都是无穷
System.out.println("INF");
return;
}
int num=0;
for(int i=0;i<10000;i++) {
if(dp[i]!=true) {
num++;
}
}
System.out.println(num);
}
//判断最大公约数
static int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
}
9.分巧克力（二分写不出来）
题目描述：
思路分析：
解法一暴力法（推荐）
package 分巧克力;
import java.util.Scanner;
//代码提交题 没有思路优先想暴力 没有暴力思路先跳 去看后面的 （暴力都写不出来那就没办法咯）
class Main{
public static void main(String[] args) {
int n, k;
int[] h = new int[100000];
int[] w = new int[100000];
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
for (int i = 0; i < n; ++i) {
h[i] = sc.nextInt();
w[i] = sc.nextInt();
}
int len =100000;
int count=0;
//记录边长
int bian=0;
for (;len>0;len--){
count=0;
//每个巧克力块，都按照len来切割
for (int i = 0; i < n; ++i) {
count += (h[i] / len) * (w[i] / len);
}
if (count>=k){
bian=len;
break;
}
}
System.out.println(bian);
}
}
解法二：二分优化法
package 分巧克力;
import java.util.Scanner;
//代码提交题 没有思路优先想暴力 没有暴力思路先跳 去看后面的 （暴力都写不出来那就没办法咯）
class Main{
public static void main(String[] args) {
int n, k;
int[] h = new int[100000];
int[] w = new int[100000];
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
for (int i = 0; i < n; ++i) {
h[i] = sc.nextInt();
w[i] = sc.nextInt();
}
int r = 100001;
int l = 1;
int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
int cnt = 0;
//每个巧克力块，都按照len来切割
for (int i = 0; i < n; ++i) {
cnt += (h[i] / mid) * (w[i] / mid);
}
if (cnt >= k) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
System.out.println(ans);
}
}
10.k倍区间（暴力思维建立起来了不错不错）
题目描述
思路：暴力，写完测试案例，除了案例外 再多测两个 防止偶然性代码白写不得分 拿了28分
package k倍区间;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int []nums=new int[n+1];
long count=0;
long sum=0;
for(int i=1;i<=n;i++){
nums[i] = scanner.nextInt();
}
//暴力for
for(int i=1;i<=n;i++) {
for(int j=i;j<=n;j++) {
if(i==j&&nums[i]%k==0) {
count++;
}else if(i==j&&nums[i]%k!=0){
}
else {
int s=i;
while(s<=j) {
sum+=nums[s] ;
s++;
}
if(sum%k==0) {
count++;
}sum=0;
}
}
}System.out.println(count);
}
}
思路二：前缀和 通过率还是28分
import java.util.Scanner;
public class _10k倍区间 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int k = input.nextInt();
int[] a = new int[n+1];
//前缀和数组
int qian []=new int[n+1];
for(int i=1;i<=n;i++){
a[i] = input.nextInt();
qian[i]=qian[i-1]+a[i];
}
int count = 0;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if((qian[j]-qian[i-1])%k==0)
count++;
}
}
System.out.println(count);
}
}
2021蓝桥杯
8.杨辉三角形
题目描述：
不要写成dp[10000][10000]，因为超出内存限制了，一个测试用例都过不了的
思路：用个二维数组将杨辉三角的所有值按顺序装进去 于是乎写出下面的代码 下面的代码只能拿30 改成dp[7000][7000]（230的内存）能拿40（改成100也能拿40分，占用内存23）,具体暴力多少适当就好，不要太大否则容易gg
package 杨辉三角形;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//存数据
int dp[][]=new int[60][60];
dp[0][0]=1;
dp[1][0]=1;
dp[1][1]=1;
int count=0;
//行
for(int i=2;i<60;i++) {
//列
for(int j=0;j<=i;j++) {
if(j==0) {
dp[i][j]=dp[i-1][j];
}else if(j==i) {
dp[i][j]=dp[i-1][j-1];
}else {
dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
}
}
}
//遍历找值
for(int i=0;i<60;i++) {
for(int j=0;j<=i;j++) {
if(dp[i][j]==n) {
System.out.println(count+1);
return;
}else {
count++;
}
}
}
}
}
满分题解（想不出来）
package 杨辉三角形;
import java.util.Scanner;
/*杨辉三角形满分题解*/
public class Main100 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long n = scan.nextLong();//输入值，查找
long[] arr =new long[44722];
arr[0]=1;
long k=1L;//k来定义位置
if (n == 1) {
System.out.println(1);
return;
}
for (int i = 1;i<447225; i++) {
for (int j = i; j>=1; j--) {
arr[j] += arr[j - 1];//换行后，用自己进行运算，减少内存
if (arr[j] == n) {
System.out.println(k + i-j + 1);
return;//如果找到了就结束
}
}
k+=(i+1);
}
System.out.println(((1 + n) * n / 2) + 2);
}
}
4.货物摆放（看答案的自己没写出来）
题目描述：
思路：
求约数，组成的L、W、H必然是n的约数，我们把n的约数全求出来，然后暴力三层for来组合，如若等于n，则+1。
细节点：n有16位数，int最多10位，long有19位，因此选择用long来存储。
package 货物摆放;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
public static void main(String[] args) {
long n=2021041820210418L;
//求出所有约数
List<Long> list=new ArrayList<Long>();
for(long i=1;(i*i)<=n;i++) {
if(n%i==0) {
list.add(i);
if(n/i!=i) {
list.add(n/i);
}
}
}
System.out.println(list);
int count=0;
//遍历
for(int a=0;a<list.size();a++) {
for(int b=0;b<list.size();b++) {
for(int c=0;c<list.size();c++) {
if(list.get(a )*list.get(b)*list.get(c)==n) {
count++;
}
}
}
}
System.out.println(count);}
}
6.时间显示
问题描述：
思路：
因为ms数不超过10的18次方，因此可以用long来存储，由于不记录ms数，我们可以通过/1000将ms删去。
package 时间显示;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws ParseException {
Scanner scanner = new Scanner(System.in);
long tt = scanner.nextLong();
//将毫秒转为秒 因为ms可以不显示
tt/=1000;
long ss=tt%60;
tt=tt/60;
long mm=tt%60;
tt/=60;
long hh=tt%24;
//数字格式化输出 记下来
System.out.println(String.format("%02d", hh)+":"+String.format("%02d", mm)+":"+String.format("%02d", ss)); S
}
}
7.最少砝码（算法题，找规律也很重要，数感也很重要）
题目描述：
思路：选大不选小 最后发现都得是3的倍数
(7条消息) 第十二届蓝桥杯省赛JavaB组 试题 G: 最少砝码小小风0的博客-CSDN博客最少砝码java
package 最少砝码;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int count=0;
int sum=0;
while(sum<n) {
sum+=Math.pow(3, count);
count++;
}
System.out.println(count);
}
}
9.双向排序（拿了60分）
题目描述：
思路:暴力骗分 不要看是第九题就怕 能拿多少分拿多少分
代码:
package 双向排序;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//接收序列的长度和操作次数
int length = sc.nextInt();
int count = sc.nextInt();
int end=length-1;
//初始化序列
int[] arr = new int[length];
for(int i = 0; i < arr.length; i++) {
arr[i] = i+1;
}
for(int i=0;i<count;i++) {
int p=sc.nextInt();
int index=sc.nextInt();
//如果是升序
if(p==1) {
//对0到index进行升序 有直接api 舒服啊啊啊啊 被坑了：这玩意左闭右开
Arrays.sort(arr,index-1,length);
/*
* for(int b=0;b<length;b++) { System.out.println(arr[b]); }
*/
}else {
int s=index-1;
//对index-length进行降序
//这步很关键
Arrays.sort(arr,0,index);
for(int j=0;j<=(index-1)/2;j++) {
int temp= arr[j];
arr[j]=arr[s];
arr[s]=temp;
s--;
}
/*
* for(int x=0;x<length;x++) { System.out.println(arr[x]); }
*/
}
}
//注意细节点 第一遍的时候，可是用了换行符喔 并且""里面忘记加了空格
for(int i=0;i<length;i++) {
System.out.print(arr[i]+" ");
}
}
}
若有收获，就点个赞吧
0 人点赞
