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

题目描述

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

小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i\times W_i$ 的方格组成的长方形。

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

1. 形状是正方形，边长是整数。

2. 大小相同。

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

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

输入格式

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

以下 $N$ 行每行包含两个整数 $H_i$ 和 $W_i$。$(1\le H_i,W_i\le 10^5)$。

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

输出格式

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

样例 #1

样例输入 #1

2 10  
6 5  
5 6

样例输出 #1

2

提示

蓝桥杯 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$ 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

20200202

样例输出 #1

20211202
21211212

提示

对于所有评测用例，$10000101\le N\le 92200229$，保证 $N$ 是一个合法日期的 $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;
    }
}