编辑

【省赛B组】2017年第八届蓝桥杯(解法通用)

2019-11-20 2019-11-29 54 2 ● 蓝桥杯 Hoji

觉得博主总结的赛题的还不错,可以去gihub,那里是对总结的宏观介绍,不奢求star,感觉有用stat一下也无妨.


001 购物单

题目

小明刚刚找到工作,老板人很好,只是老板夫人很爱购物。
老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦,但又不好推辞。

这不,XX大促销又来了!老板夫人开出了长长的购物单,都是有打折优惠的。
小明也有个怪癖,不到万不得已,从不刷卡,直接现金搞定。
现在小明很心烦,请你帮他计算一下,需要从取款机上取多少现金,才能搞定这次购物。

取款机只能提供100元面额的纸币。小明想尽可能少取些现金,够用就行了。
你的任务是计算出,小明最少需要取多少现金。

以下是让人头疼的购物单,为了保护隐私,物品名称被隐藏了。

**** 180.90 88折 **** 10.25 65折 **** 56.14 9折 ...

需要说明的是,88折指的是按标价的88%计算,而8折是按80%计算,余者类推。特别地,半价是按50%计算。请提交小明要从取款机上提取的金额,单位是元。答案是一个整数,类似4300的样子,结尾必然是00,不要填写任何多余的内容。

题解

public class Main {
  public static void main(String[] args) {
    double res = 0 + 180.90 * 0.88 + 10.25 * 0.65 + 56.14 * 0.9
      + 104.65 * 0.9 + 100.30 * 0.88 + 297.15 * 0.5 + 26.75 * 0.65
      + 130.62 * 0.5 + 240.28 * 0.58 + 270.62 * 0.8 + 115.87 * 0.88
      + 247.34 * 0.95 + 73.21 * 0.9 + 101.00 * 0.5 + 79.54 * 0.5
      + 278.44 * 0.7 + 199.26 * 0.5 + 12.97 * 0.9 + 166.30 * 0.78
      + 125.50 * 0.58 + 84.98 * 0.9 + 113.35 * 0.68 + 166.57 * 0.5
      + 42.56 * 0.9 + 81.90 * 0.95 + 131.78 * 0.8 + 255.89 * 0.78
      + 109.17 * 0.9 + 146.69 * 0.68 + 139.33 * 0.65 + 141.16 * 0.78
      + 154.74 * 0.8 + 59.42 * 0.8 + 85.44 * 0.68 + 293.70 * 0.88
      + 261.79 * 0.65 + 11.30 * 0.88 + 268.27 * 0.58 + 128.29 * 0.88
      + 251.03 * 0.8 + 208.39 * 0.75 + 128.88 * 0.75 + 62.06 * 0.9
      + 225.87 * 0.75 + 12.89 * 0.75 + 34.28 * 0.75 + 62.16 * 0.58
      + 129.12 * 0.5 + 218.37 * 0.5 + 289.69 * 0.8;
    System.out.println(res);
    int r = (int) res;
    r = r%100 != 0 ? r-r%100+100 : r;
    System.out.println(r);
  }
}

答案: 5200


002 纸牌三角形

题目

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形(A按1计算)。要求每个边的和相等。下图就是一种排法。

   A
  9 6
 4   8
3 7 5 2

这样的排法可能会有很多。如果考虑旋转、镜像后相同的算同一种,一共有多少种不同的排法呢? 请你计算并提交该数字。

题解

这是一道全排列问题(有关排列组合可以参考 -> 我的这篇博客),事先约定:

data[0]==1,data[1]==9,data[2]==6,data[3]==4,data[4]==8,data[5]==3,data[6]==7,data[7]==5,data[8]==2

求出每一种排列组合,看是否满足条件:(left == right) && (left == hemline )

  • left:左斜边
  • right:右斜边
  • hemline:底边

旋转: 旋转就是将三角形以顶点为轴转动,一共三个顶点,可以旋转两次 镜像:也就是形状对称,如下图案就和样例形状对称。一共3条边,所以可以镜像3次。 除以6知道吗: 每次镜像得到的图形都可以旋转两次 -> 2*3

   A
  6 9
 8   4
2 5 7 3  
/**
 * @Author: Hoji(PAN先森)
 * @Date: 11/20/2019 4:30 PM
 * @个人博客:https://www.hoji.site
 */
public class Main {
  private static int ans=0;
  private static int left=0, right=0, hemline=0;
  private static void swap(int[] arr, int i, int j) {
    int t=arr[i];
    arr[i]=arr[j];
    arr[j]=t;
  }

  private static void f(int[] data, int start) {
    if(start == data.length) {
      left = data[0]+data[1]+data[3]+data[5];
      right = data[0]+data[2]+data[4]+data[8];
      hemline  = data[5]+data[6]+data[7]+data[8];
      if((left == right) && (left == hemline )) ++ans;
    }
    else
      for (int i = start; i < data.length; i++) {
      swap(data, i, start);
      f(data, start+1);
      swap(data, i, start);
    }
  }
  public static void main(String[] args) {
    int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    f(data, 0);
    System.out.println(ans/6);
  }
}

答案:144


002 等差素数(C语言)

2,3,5,7,11,13,…. 是素数序列。 类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。 上边的数列公差为30,长度为6。2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。 求:长度为10的等差素数列,其公差最小值是多少?

说明一下

  • if (primes[i+tolerance*count] != 1),逻辑就是从i==2,tolerrance==1开始查找
  • 如果是素数(primes[aPrime])且是等差的(an = a1+(n-1)*d),那么count++
/**
 * @Author: Hoji(PAN先森)
 * @Date: 11/21/2019 9:25 PM
 * @个人博客:https://www.hoji.site
 */
public class Main {
  private static int[] primes = new int[1000000];
  private static boolean isPrime(int i) {
    for(int j = 2; j < i; j++)
    if(i%j==0)  return false;
    return true;
  }
  private static void init() {
    for (int i=2; i<1000000; i++)
    if(isPrime(i)) primes[i]=1;   //是素数则将其标记为1,不是自然为0,注:只是标记,素数的值还是i
  }
  /**
   * tolerance:公差
   */
  public static void main(String[] args) {
    init();
    //1、公差最多不差过1000,因为素数是递增的,而公差如果超过1000,那么素数的范围会超过100000
    for (int tolerance = 1; tolerance < 10000; tolerance++) {
      for (int i = 2; i < 100000; i++) {
        int count;
        for (count=0; count < 10; count++)
        if (primes[i+tolerance*count] != 1) break;
        if(count == 10)   { System.out.println(tolerance); return;}
      }
    }
  }
}

这题用java暴力破解时间很久,


003 承压计算

题目

X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。每块金属原料的外形、尺寸完全一致,但重量不同。金属材料被严格地堆放成金字塔形。


004 魔方状态

题目

二阶魔方就是只有2层的魔方,只由8个小块组成。

魔方

小明很淘气,他只喜欢3种颜色,所有把家里的二阶魔方重新涂了颜色,如下:

前面:橙色
右面:绿色
上面:黄色
左面:绿色
下面:橙色
后面:黄色

请你计算一下,这样的魔方被打乱后,一共有多少种不同的状态。如果两个状态经过魔方的整体旋转后,各个面的颜色都一致,则认为是同一状态。


005 取数位

题目

求1个整数的第k位数字有很多种方法。以下的方法就是一种。对于题目中的测试数据,应该打印5。

/**
 * @Author: Hoji(PAN先森)
 * @Description: 求1个整数的第k位数字有很多种方法。
 * @Date: 11/20/2019 9:18 PM
 * @个人博客:https://www.hoji.site
 */
public class Main {
  static int len(int x){
    if(x<10) return 1;
    return len(x/10)+1;
  }
  static int f(int x, int k){
    if(len(x)-k==0) return x%10;
    return f(x/10, k); //____? ——> return f(?, ?);____;
  }
  public static void main(String[] args) {
    int x = 23513;
    System.out.println(f(x, 3));
  }
}

答案

递归程序,首先想到的应该是返回自身函数 f(?,?),然后再补充参数

f(x/10, k);

006 最大公共子串

题目

最大公共子串长度问题就是:求两个串的所有子串中能够匹配上的最大长度是多少。比如:"abcdkkk" 和 "baabcdadabc",可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。

/**
 * @Author: Hoji(PAN先森)
 * @Date: 11/20/2019 9:29 PM
 * @个人博客:https://www.hoji.site
 */
public class Main {
  static int f(String s1, String s2)  {
    char[] c1 = s1.toCharArray();
    char[] c2 = s2.toCharArray();
    int[][] a = new int[c1.length+1][c2.length+1];

    int max = 0;
    for(int i=1; i<a.length; i++)
    for(int j=1; j<a[i].length; j++)
    if(c1[i-1]==c2[j-1]) {
      a[i][j] = a[i-1][j-1]+1; //______a[i-1][j-1]+1;____________;
      if(a[i][j] > max)
      max = a[i][j];
    }
    return max;
  }
  public static void main(String[] args){
    System.out.println(f("abc", "abcd"));  //3
  }
}

矩阵一般都是找各个方格之间的关系,这里就是前一个方格与后一个方格的关系 -> a[i][j] = a[i-1][j-1]+1;

答案

a[i-1][j-1]+1;

007 日期问题

题目

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采用日/月/年的。更加麻烦的是,年份也都省略了前两位,使得文献上的一个日期,存在很多可能的日期与其对应。

比如02/03/04,可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期,你能帮助小明判断有哪些可能的日期对其对应吗?一个日期,格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)

【输出】

02/03/04  

【输出】

2002-03-04  
2004-02-03  
2004-03-02  
输出若干个不相同的日期,每个日期一行,格式是"yyyy-MM-dd"。多个日期按从早到晚排列。  

题解

/**
 * @Author: Hoji(PAN先森)
 * @Date: 11/20/2019 9:43 PM
 * @个人博客:https://www.hoji.site
 */
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
  private static boolean isLeep(int year) {
    return (year%4==0 && year%100!=0) || year%400==0;
  }
  /**
   * @param a:默许a为年
   * @param b:默许b为月
   * @param c:默许c为日
   * 不满足1、2、3其一,那么return "";
   */
  private static String f(int a, int b, int c) {
    //1、判断年是否符合范围
    if(a >= 0 && a <= 59) a+=2000;
    else if(a >= 60 && a <= 99) a+=1900;
    else return "";
    //2、判断基本的月日范围是否合法
    if(b < 1 || b > 12) return "";
    if(c < 1 || c > 31) return "";
    //3、处理月份对应的天数问题
    boolean isLeep = isLeep(a);
    switch (b) {
      case 2:
      //如果b是2月,并且当年是闰年,那么c不应该超出29天,其余只需判断30天的月份,因为31天的月份已判断完毕
      if (isLeep && c > 29) return "";
      if (!isLeep && c > 28)return "";
      break;
      case 4: if(c > 30)  return ""; break;
      case 6: if(c > 30)  return ""; break;
      case 9: if(c > 30)  return ""; break;
      case 11:if(c > 30)  return ""; break;
      default: break;
    }
    String sa = a+"";
    String sb = b+"";
    String sc = c+"";
    
    if(sb.length()==1) sb="0"+sb;
    if(sc.length()==1) sc="0"+sc;

    return sa+"-"+sb+"-"+sc;
  }
  
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    String date = s.nextLine();
    int a = (date.charAt(0)-'0')*10 + date.charAt(1)-'0';
    int b = (date.charAt(3)-'0')*10 + date.charAt(4)-'0';
    int c = (date.charAt(6)-'0')*10 + date.charAt(7)-'0';
    String case1 = f(a, b, c);
    String case2 = f(c, a, b);
    String case3 = f(c, b, a);
    TreeSet<String> set = new TreeSet<String>();
    if(case1!+null) set.add(case1);
    if(case2!=null) set.add(case2);
    if(case3!=null) set.add(case3);
    for(String s1 : set)
      System.out.println(s1);
  }
}

008 包子凑数

略...


009 分巧克力

一、题目描述

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力,其中第 i 块是 Hi x Wi 的方格组成的长方形。

为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:

  1. 形状是正方形,边长是整数
  2. 大小相同

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,请计算出最大的边长是多少.

【输入】
第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 
输入保证每位小朋友至少能获得一块1x1的巧克力。   

【输出】
输出切出的正方形巧克力最大可能的边长。

样例输入:	
2 10  
6 5  
5 6  
样例输出:
2

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms

二、题解

(1)暴力破解(超时)

暴力破解的大致思路:

  • 首先,初始化题目的输入要求(N,K,以及存储 N 行的巧克力信息 H[i],W[j] 的数组 H[],W[]
  • 在 10W 次循环中,巧克力首先从边长 lenOfEdge == 1 开始切割,进入 check() 方法,该方法的作用就是计算已确定分割边长的巧克力的分割数是否够小朋友们吃 (count > K)
  • 如果可以切割后的巧克力 count 数量多于小朋友的数量 K,那么继续寻找分割长度大于前一次分割长度并且 count > K 的分割长度.
/**
 * @Author: Hoji(PAN先森)
 * @Date: 11/21/2019 11:56 AM
 * @个人博客:https://www.hoji.site
 */
import java.util.Scanner;
public class Main {
  private static int[] H = new int[100000];
  private static int[] W = new int[100000];
  private static int N, K;  //N: 巧克力的数量,K:小朋友的人数

  private static boolean check(int lenOfEdge) {
    int count=0;
    for (int i = 0; i < N ; i++)
      count += (H[i]/lenOfEdge)*(W[i]/lenOfEdge);//从边长(lenOfEdge)为1开始计算N块巧克力共能分成多少块
    return count > K;
  }

  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    N = s.nextInt();
    K = s.nextInt();
    for (int i = 0; i < N; i++) {
      H[i] = s.nextInt();
      W[i] = s.nextInt();
    }
    int count=0, ans;
    for (int lenOfEdge=1; lenOfEdge < 100000; ++lenOfEdge) {
      //如果出现分割后产生的巧克力数不够时,那么前一个分割方法产生的就是最大的边长
      if(check(lenOfEdge)) ans=lenOfEdge;
      else break;
    }
    System.out.println(ans);
  }
}

答案:2;输入数据:2 10 \n 6 5 \n 5 6


(2)二分优化

大致思路:

  • 从中间找,如果 check(mid) == true,证明在 mid 处可以找到满足条件的分割长度,那么缩小查找范围置 [mid+1, right]
  • 如果 check(mid) == false,证明在 l ~ mid 都找不到合适的分割数目满足小朋友的数目 K,这证明分割长度太大了以至于分割后的巧克力数 count 少了,那么也要缩小范围至 [l, mid-1]

把 for 循环改成如下代码即可,注意点:

在二分查找中,选取 mid 的方法一般为 (left+right)。如果使用的编程语言会有整数溢出的情况 (如 C++,Java),可用 left + (right−left)/2 代替前者。

  • left+right;:可能会超过 int 而溢出,于是提出了如下办法:
  • int middle = left + (right - left)/2;:这样防止溢出,等价于:
  • int middle = left + (right - left) >> 1
int l=1, r=100000, mid=(l+r)/2;
while(l < r) {
  mid = l + (r-l)/2;
  if (check(mid)) { l=mid+1; }
  else r=mid-1;
}
System.out.println(l);

总结

题目考察点
001 购物单Excel、最后的那步得到整数最后两位数
002 纸牌三角形旋转、镜像的定义 + 排列组合
003 承压计算(待完成...)略...
004 魔方状态(待完成...)略... (可能会用到 搜索)
005 取数位整数的取余、除法
006 最大公共子串dp,寻找结果矩阵元素的关系
007 日期问题字符串处理、日期的运算、闰年、字符加减法、TreeSet 的基本使用
008 包子凑数(待完成...)扩展
009 分巧克力暴力枚举 / 二分枚举
010k倍区间(待完成...)前缀和 + 组合数学

倘若小文于你有益,欢迎
  • 如果您的提问博主没能及时回复,通过分享文章获得援助,何尝不是一种查缺补漏的好做法
  • 版权声明:本文为博主原创文章,遵循CC 4.0 BY版权协议
  • 文章转载:请在文末添加原文章地址,这也是尊重他人劳动成果的一点体现,谢谢您的配合!
  • 评论信息 (注:评论收到回复后,会以邮箱的方式提醒您;您的邮箱不会显示到页面中)

    验证码信息 看不清?点击图片进行切换!
    精彩随处可见 更多精彩内容
    作者: 浏览 61 评论 1 赞 1 2020-01-15
    作者: 浏览 62 评论 1 赞 1 2019-11-29
    作者: 浏览 83 评论 1 赞 1 2019-11-29
    作者: 浏览 54 评论 1 赞 1 2019-11-29
    作者: 浏览 52 评论 1 赞 1 2019-11-29
    目录