【Java版oj】day32淘宝网店、斐波那契凤尾

布满荆棘的人生 2024-03-23 11:20 45阅读 0赞

**目录**

一、淘宝网店

（1）原题再现

（2）问题分析

（3）完整代码

二、斐波那契凤尾

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、淘宝网店 ##
> 
> ### （1）原题再现 ###
> 
> [淘宝网店\_\_牛客网][Link 1] 
> 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
> 
> ### （2）问题分析 ###
> 
> 这道题我的思路是这样的：首先开始年和结束年不一定是一个完整的年。所以我们需要把开始年和结束年单独剔除计算。
> 
> 对于开始年和结束年这种可能不是完整的一年，我们还需要判断是不是同一个月，如果是同一个月，就用结束日减去开始日则算出天数；如果不是同一个月则把开始月和结束月单独计算。开始月是用这个的总天数减去开始月的日期，结束月就是结束月的日期。
> 
> 中间完整的一年，判断每一年是否闰年，如果是闰年，就计算1月1日到12月31日这段时间的收益。
> 
> 代码中有详细标注，这道题就是写起来有点费时，但是难度不大。
> 
> ### （3）完整代码 ###
> 
> import java.util.*;
> 
> /*
> * 淘宝网店
> */
> public class Main {
> 	public static void main(String[] args) {
> 		Scanner sc=new Scanner(System.in);
> 		while(sc.hasNextInt()) {
> 			int fromYear=sc.nextInt();
> 			int fromMonth=sc.nextInt();
> 			int fromDay=sc.nextInt();
> 			int toYear=sc.nextInt();
> 			int toMonth=sc.nextInt();
> 			int toDay=sc.nextInt();
> 			
> 			Set<Integer>set=new HashSet<>();//添加素数方便查找
> 			set.add(2);set.add(3);set.add(5);
> 			set.add(7);set.add(11);
> 			int money=0;
> 			int day=0;
> 			if(fromYear==toYear) {
> 				if(fromMonth==toMonth) {
> 					money=sameMonth(fromDay, fromMonth, fromYear, toDay, toMonth, toYear, set);
> 				}else {
> 					money=sameYear(fromDay, fromMonth, fromYear, toDay, toMonth, toYear, set);
> 				}
> 			}else {//不同年
> 				money+=sameYear(fromDay, fromMonth, fromYear, 31, 12, fromYear, set);//第一年
> 				money+=sameYear(1, 1, toYear, toDay, toMonth, toYear, set);//最后一年
> 				int temp=fromYear+1;
> 				while( temp<toYear){
> 					money+=sameYear(1, 1, temp, 31, 12, temp, set);
> 					temp++;
> 				}
> 				
> 			}
> 			System.out.println(money);
> 			
> 		}
> 	}
> 	//是否是闰年
> 	public static boolean isLeapYear(int year) {
> 		return (year%4==0&&year%100!=0)||year%400==0;
> 	}
> //计算某个月多少天
> 	public static int manyDay(int year,int month) {
> 		switch(month) {
> 		case 1:case 3:case 5 :
> 		case 7:case 8: case 10:case 12:return 31;
> 		case 4:case 6:case 9:case 11:return 30;
> 		default:
> 			if(isLeapYear(year)==true) {
> 				return 29;
> 			}
> 			else {
> 				return 28;
> 			}
> 		}
> 	}
> 	//同年不同月
> 	public static int sameYear(int fromDay,int fromMonth,int fromYear,int toDay,int toMonth,int toYear,Set<Integer>set) {
> 		int money=0;
> 		int day=0;
> 		day=manyDay(fromYear, fromMonth)-fromDay+1;//初始月的天数,包括初始日期
> 		if(set.contains(fromMonth)) {//是否是素月
> 			money+=day*1;
> 		}else {
> 			money+=day*2;
> 		}
> 		day=toDay;//结束月的天数
> 		if(set.contains(toMonth)) {
> 			money+=day*1;
> 		}else {
> 			money+=day*2;
> 		}
> 		
> 		//中间月
> 		for(int i=fromMonth+1;i<toMonth;i++) {
> 			day=manyDay(fromYear, i);
> 			if(set.contains(i)) {
> 				money+=day*1;
> 			}else {
> 				money+=day*2;
> 			}
> 		}
> 		return money;
> 	}
> 	//同年同月
> 	public static int sameMonth(int fromDay,int fromMonth,int fromYear,int toDay,int toMonth,int toYear,Set<Integer>set) {
> 		int money=0;
> 		int day=0;
> 		day=toDay-fromDay+1;//初始月的天数,包括初始日期
> 		if(set.contains(fromMonth)) {//是否是素月
> 			money+=day*1;
> 		}else {
> 			money+=day*2;
> 		}
> 		return money;
> 	}
> }
> 
> ![61637e10d2964af7b5b3e09f199cc7a5.png][]

> ## 二、斐波那契凤尾 ##
> 
> ### （1）原题再现 ###
> 
> [斐波那契凤尾\_\_牛客网][Link 2] 
> 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
> 
> ### （2）问题分析 ###
> 
> 这道题两个注意点。
> 
> 第一点不能超过数据范围，所以我们在进行加法的时候根据题目要求直接取最后六位，因为是加法，所以取六位相加和所有数相加的结果后六位是没有影响的。
> 
> 第二点不能超过运行时间，运行时间很小，肯定不能用递归。所以用一个数组直接保存所有需要的斐波那契数。因为是循环输入，如果我们每次在循环里面都建立一个数组，最后总时间就会发生超时错误。所有我们在输入循环外面建一个数组即可。
> 
> ### （3）完整代码 ###
> 
> import java.util.*;
> /*
> *斐波那契凤尾
> */
> public class Main {
> public static long[] fibs = new long[100001];
> public static void main(String[] args) {
> Scanner sc = new Scanner(System.in);
> 
> //生成fib
> fibs[0] = 1;
> fibs[1] = 1;
> int flag = 0;
> for (int i = 2; i < fibs.length; i++) {
> long ret = fibs[i - 1] + fibs[i - 2];
> fibs[i] = ret % 1000000;
> if (flag == 0 && ret >= 1000000) flag = i;
> }
> 
> while (sc.hasNextInt()) {
> int n = sc.nextInt();
> if (n < flag) System.out.println(fibs[n]);
> else System.out.printf("%06d\n", fibs[n]);
> }
> }
> }
> 
> ![08f4b34d953b4963b87a81071a003d74.png][]

##  ##

--------------------

![0528c1bee7fd4ba88b10920ce70ad6ae.png][]

[Link 1]: https://ac.nowcoder.com/questionTerminal/754921e9c98b43d1b2d70c227b844101?commentTags=C%2FC%2B%2B
[61637e10d2964af7b5b3e09f199cc7a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/28c1e1b369fa4ac798218564c2905cef.png
[Link 2]: https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb
[08f4b34d953b4963b87a81071a003d74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/591d729e4ee144fba135144f434dd5ee.png
[0528c1bee7fd4ba88b10920ce70ad6ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/75185c92a92d4cfa8602ecf06a292b4c.png