蓝桥杯真题4

迷南。 2024-03-24 12:37 62阅读 0赞

## \[蓝桥杯 2017 省 AB\] 分巧克力 ##

### 题目描述 ###

儿童节那天有  K K K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有  N N N 块巧克力，其中第  i i i 块是  H i × W i H\_i \\times W\_i Hi×Wi 的方格组成的长方形。

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

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

例如一块  6 × 5 6 \\times 5 6×5 的巧克力可以切出  6 6 6 块  2 × 2 2 \\times 2 2×2 的巧克力或者  2 2 2 块  3 × 3 3 \\times 3 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小  H i H\_i Hi 计算出最大的边长是多少么？

### 输入格式 ###

第一行包含两个整数  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 行每行包含两个整数  H i H\_i Hi 和  W i W\_i Wi。 ( 1 ≤ H i , W i ≤ 1 0 5 ) (1 \\le H\_i,W\_i \\le 10^5) (1≤Hi,Wi≤105)。

输入保证每位小朋友至少能获得一块  1 × 1 1 \\times 1 1×1 的巧克力。

### 输出格式 ###

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

### 样例 \#1 ###

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

2 10  
    6 5  
    5 6

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

### 提示 ###

蓝桥杯 2022 省赛 A 组 I 题。

### 分析 ###

题目意思：要把N 块巧克力切成边长完全一样的正方形小块，至少K块，求切成的巧克力块的最大边长  
对于一块巧克力而言，长为H ，宽为W ，若想切成边长为X 的正方形小块，可以切H/x \* W/x 块  
我们发现，可以切成的块数与最终切成个一个个正方形的边长是成反比的，也就是存在单调性，因此可以用二分来解决这个问题

可以大幅提高效率，毕竟二分搜索的效率要远远高于枚举，而判断这一操作，可以根据是否能够切够k块来判断。

import java.util.*;
    public class Main{
        
        static int N = 100010;
        static int[] h = new int[N];
        static int[] w = new int[N];
        static int n;
        static int k;
        public static void main(String[] args){
        
            Scanner scan = new Scanner(System.in);
            n = scan.nextInt();
            k = scan.nextInt();
            for(int i = 0;i<n; i++){
        
                h[i]=scan.nextInt();
                w[i]=scan.nextInt();
            }
            int l = 1; r = N;
            while(l<r){
        
                int mid = l + r + 1 >> 1;
                if(count(mid)) l = mid;
                else r = mid - 1;
            }
            System.out.println(l);
        } 
        public static boolean count(int m){
        
            int res = 0;
            for(int i = 0;i < n; i++){
        
                res += (h[i]/m) * (w[i]/m);
            }
            if(res >= k) return true;
            return false;
        }
    }

## \[蓝桥杯 2020 省 AB2\] 回文日期 ##

### 题目描述 ###

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 `yyyymmdd` 的格式写成一个  8 8 8 位数是 `20200202`，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 `20200202` 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：`20211202` 即 2021 年 12 月 2 日。

也有人表示 `20200202` 并不仅仅是一个回文日期，还是一个 `ABABBABA` 型的回文日期。对此小明也不认同，因为大约  100 100 100 年后就能遇到下一个 `ABABBABA` 型的回文日期：`21211212` 即 2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 `ABABBABA` 型的回文日期各是哪一天。

### 输入格式 ###

输入包含一个八位整数  N N N，表示日期。

### 输出格式 ###

输出两行，每行  1 1 1 个八位数。第一行表示下一个回文日期，第二行表示下  
一个 `ABABBABA` 型的回文日期。

### 样例 \#1 ###

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

20200202

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

20211202
    21211212

### 提示 ###

对于所有评测用例， 10000101 ≤ N ≤ 92200229 10000101 \\le N \\le 92200229 10000101≤N≤92200229，保证  N N N 是一个合法日期的  8 8 8 位数表示。

蓝桥杯 2020 第二轮省赛 A 组 G 题（B 组 G 题）。

### 分析 ###

题意十分简单明确，我们直接枚举即可，遍历从输入日期开始的所有回文数，检查是否合法（满足正确日期），在此基础上找到满足 `ABABBABA` 型的回文日期分别输出即可。

### 代码实现 ###

import java.util.Scanner;
    
    public class Main {
        
        static int[] days = {
        0,31,28,31,30,31,30,31,31,30,31,30,31};
        public static void main(String[] args) {
        
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int flag = 0;
            for (int i = n+1; ; i++) {
        
                if (checked1(i)){
        //检测是否回文
                    if (flag == 0){
        
                        System.out.println(i);
                        flag = 1;
                    }
                    if (checked2(i)){
        //检测是否符合格式
                        System.out.println(i);
                        break;
                    }
                }
    
            }
        }
    
        private static boolean checked2(int i) {
        
            char[] a = (i+"").toCharArray();
            if (a[0]==a[2]&&a[1]==a[3]&&a[0]!=a[3]){
        
                //利用已是回文，简化条件
                return true;
            }
            return false;
        }
    
        private static boolean checked1(int i) {
        
    
            char[] a = (i+"").toCharArray();
            int l = 0;
            int r = a.length-1;
            while(l <= r){
        
                if (a[l]!=a[r]){
        
                    return false;
                }
                l++;
                r--;
            }
            if (!isDate(i)){
        
                return false;
            }
            return true;
        }
        private static boolean isDate(int i){
        
            int y = i / 10000;//年
            int m = (i /100) % 100;//月
            int d = i % 100;//日
            if (m <= 0 || m > 12) return false;
            if (d == 0 || m != 2 && d > days[m]) return false;
            if (m == 2){
        
                int leap = 0;
                if (y % 100 != 0 && y % 4 == 0 || y % 400 == 0){
        
                    leap = 1;
                }
                if (d>days[m]+leap) return false;
            }
            return true;
        }
    }