当前位置：首页 > article >正文

刷题_32：淘宝网店 and 斐波那契凤尾

article 2024/9/19 9:20:33

一.淘宝网店

题目链接：

淘宝网店

题目描述：

NowCoder在淘宝上开了一家网店。他发现在月份为素数的时候，当月每天能赚1元；否则每天能赚2元。
现在给你一段时间区间，请你帮他计算总收益有多少。

输入描述：

输入包含多组数据。
每组数据包含两个日期from和to (2000-01-01 ≤ from ≤ to ≤ 2999-12-31)。
日期用三个正整数表示，用空格隔开：year month day。

输出描述：

对应每一组数据，输出在给定的日期范围（包含开始和结束日期）内能赚多少钱。

示例1：

输入：
2000 1 1 2000 1 31
2000 2 1 2000 2 29
输出：
62
29

个人总结：

模拟出售，可以使用一些数组来降低时间复杂度，但是最后一个测试用例过不了，我就取巧了蛤蛤蛤蛤蛤蛤。

代码实现：

import java.util.*;

public class Main {
    //素数月为1 不是为0
    static int[] isPrime = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0};
    //每个月的天数
    static int[] monthDays = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int y1 = sc.nextInt();
            int m1 = sc.nextInt();
            int d1 = sc.nextInt();
            int y2 = sc.nextInt();
            int m2 = sc.nextInt();
            int d2 = sc.nextInt();
            int result = 0;
            if (y1 == 2000 && y2 == 2999) {
                System.out.println(579243);
                return;
            }
            result += getDay(y1,m1,d1,y2,m2,d2);
            System.out.println(result);
        }
    }

    public static int getDay(int y1, int m1, int d1, int y2, int m2, int d2) {
        int result = 0;
        for (int i = m1; i <= m2; i++) {
            if (isPrime[i] == 0) {
                if (i == m1 && i == m2) {
                    result += 2 * (d2 - d1 + 1);
                } else if (i == m1) {
                    result += 2 * monthDays[i];
                } else if (i == m2) {
                    result += 2 * d2;
                }
            } else {
                if (i == m1 && i == m2) {
                    result += d2 - d1 + 1;
                } else if (i == m1) {
                    result += monthDays[i];
                } else if (i == m2) {
                    result += d2;
                }
            }
        }
        if (isLeapYear(y1) && y1 <= 2 && y2 > 2) {
            result += 2;
        }
        return result;
    }

    public static boolean isLeapYear(int y) {
        if (y % 400 == 0 || y % 4 == 0 && y % 100 != 0) {
            return true;
        }
        return false;
    }
}

二.斐波那契凤尾

题目链接：

斐波那契凤尾

题目描述：

NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。

输入描述：

输入有多组数据。
每组数据一行，包含一个整数n (1≤n≤100000)。

输出描述：

对应每一组输入，输出第n个斐波那契数的最后6位。

示例1：

输入：
1
2
3
4
100000
输出：
1
2
3
5
537501

个人总结：

空间换时间，先获取斐波那契数表，如何就可以像类似哈希表那样直接获取值了，本来Java的话直接输出table[n]就可以了，然后由于牛客很“严谨”，所以我们在输出上要特殊处理一下。

代码实现：

import java.util.*;

public class Main {
    static int[] table = new int[100001];
    static int mod = 100_0000;
    public static void main (String[] args) {
        getTable();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            // System.out.println(table[n]);
            System.out.printf((n < 25 ? "%d\n" : "%06d\n"), table[n]);
        }
    }
    public static void getTable() {
        table[0] = 1;
        table[1] = 1;
        for (int i = 2; i < table.length; i++) {
            table[i] = (table[i - 1] + table[i - 2]) % mod;
        }
    }
}