时间限制:2000ms
单点时限:1000ms
内存限制:256MB
给定两个日期,计算这两个日期之间有多少个2月29日(包括起始日期)。
只有闰年有2月29日,满足以下一个条件的年份为闰年:
1. 年份能被4整除但不能被100整除
2. 年份能被400整除
第一行为一个整数T,表示数据组数。
之后每组数据包含两行。每一行格式为"month day, year",表示一个日期。month为{"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"}中的一个字符串。day与year为两个数字。
数据保证给定的日期合法且第一个日期早于或等于第二个日期。
对于每组数据输出一行,形如"Case #X: Y"。X为数据组数,从1开始,Y为答案。
1 ≤ T ≤ 550
小数据:
2000 ≤ year ≤ 3000
大数据:
2000 ≤ year ≤ 2×109
样例输入
4
January 12, 2012
March 19, 2012
August 12, 2899
August 12, 2901
August 12, 2000
August 12, 2005
February 29, 2004
February 29, 2012
样例输出
Case #1: 1
Case #2: 0
Case #3: 1
Case #4: 3
这道题,过小数据再简单不过了,但是要过大数据的话,还是有一点考验人的:
我们这里只需要注意这几点就可以做了:
如何求任意一个时间段的闰年数?
方法有很多,但是要说到高效率的话,用这个还是不错的, year/4 -year/100 +year/400 ;
但是由于还是要找到最近的闰年年份才能算简化这道题、代码如下
代码:
1 //#define _CRT_SECURE_NO_WARNINGS
2 //#define LOCAL
3
4 #include<iostream>
5 #include<string>
6 #include<stdio.h>
7 #include<stdlib.h>
8 #include<string.h>
9 #include<algorithm>
10
11 #define __int int
12
13
14
15 using namespace std;
16
17 const char month[13][15] = {
18
19 "$$$","January", "February",
20 "March", "April", "May",
21 "June", "July", "August",
22 "September", "October",
23 "November", "December"
24 };
25
26 struct Mydate {
27
28 __int year;
29 char month[15];
30 int mon;
31 int day;
32
33 };
34
35 //判断是否是闰年
36 bool isprimer(__int year) {
37
38 if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
39 return true; //闰年
40 return false; //不是闰年
41 }
42
43 //输入接口
44 void input(Mydate & ins) {
45
46 ins.mon = 0; //初始化
47 scanf("%s %d,%d", &ins.month, &ins.day, &ins.year);
48 }
49
50 //将月份转化为数字部分
51 void change(Mydate &aa) {
52
53 for (int i = 1; i < 13; i++) {
54 if (strcmp(month[i], aa.month) == 0) {
55 aa.mon = i;
56 return;
57 }
58 }
59 }
60
61 //计算年份与年份间有多少个闰年
62 __int work(const Mydate &star, const Mydate &_end) {
63
64 //找到开始年份最近的一个闰年
65 __int fir_pr = -1, las_pr = -1, res = 0;
66 __int num_start, num_end;
67 for (__int var = star.year ; var <= _end.year ; var++) {
68 if (isprimer(var)) {
69 fir_pr = var;
70 break;
71 }
72 }
73
74 for (__int var = _end.year; var >= star.year; var--) {
75 if (isprimer(var)) {
76 las_pr = var;
77 break;
78 }
79 }
80
81 if (fir_pr >=star.year && las_pr>=star.year ) {
82
83 num_start = (fir_pr / 4 - fir_pr / 100 + fir_pr / 400);
84 num_end = (las_pr / 4 - las_pr / 100 + las_pr / 400);
85
86 res =(num_end - num_start )+1; //年份间的闰年数
87
88 if ( fir_pr == star.year ) {
89 if (star.mon > 2) res-- ;
90 }
91
92 if ( las_pr == _end.year ) {
93 if (_end.mon < 2 ||(_end.mon == 2 && _end.day <29) ) res-- ;
94 }
95 }
96 return res;
97 }
98
99 int main() {
100
101 Mydate _start, _end;
102 int _case, cnt = 1;
103 #ifdef LOCAL
104 freopen("test.in", "r", stdin);
105 #endif
106 scanf("%d", &_case);
107 //输入部分
108 for (cnt = 1; cnt <= _case; cnt++) {
109
110 input(_start), input(_end);
111 change(_start), change(_end);
112 __int res = work(_start, _end);
113 printf("Case #%d: %d\n", cnt, res);
114
115 }
116
117
118 return 0;
119 }