- 浏览: 196915 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
大致题意: 科普文一篇,文章80%都是无用信息,因为都是常识,但是又不得不看,因为有20%是常人不知道的历史常识。 定义: Goog month : 该月第一个工作日为星期一的月份 Luckly month: 该月最后一个工作日为星期五的月份 问: 给定一个Gregorian Calendar格里高公历的 时间闭区间(就是包括端点的年月了) 【开始年、月】~【结束年、月】 在这个时间区间内,有多少个Goog month,有多少个Luckly month 文章要点: Gregorian Calendar格里高公历 就是现在广泛使用公历(西历),下面简称GC GC的起始日期为 1年1月1号,该日为星期六 GC平年有365天,闰年366天(2月多1天) GC有12个月,各月的天数和现在的使用的西历一致 GC在1582年之前(不包括1582),若该年份能被4整除,则为闰年 GC在1582年之后(包括1582),判断闰年的标准(满足下面随便一个): (1) 能被4整除,但不能被100整除; (2) 能被400整除。 由于历史原因,GC规定1700年无条件为闰年 由于历史原因,GC规定1752年9月3日~13日共11天不存在,即1752年9月只有19天 GC一星期有7天,排序为Sun,Mon,Tue,Wed,Thu,Fri,Sat,和现在的星期一致,其中Mon到Fri为工作日,Sun和Sat为休息日 解题思路: 直接模拟就OK了,水题 先做一个判断闰年的函数 leap() 输入时间区间的 起始年sy月sm 和 终止年ey月em 后 先计算1年1月到sy年sm-1月(若sm=1,则计算到sy-1年12月)的天数day 注意此时day的天数刚好计算到sm-1月的最后一天 若day+1,则恰好进入所输入的时间区间【开始年、月】~【结束年、月】的第一天 计算day时要注意: (1) 1582年前后闰年判断标准改变了 (2) 1700无条件闰年 (3) 1752年9月少了11天 判断第day天是星期几: 由于1年1月1号为星期六,一星期有7天, 因此 (day+5)%7就能计算第day天是星期几。 不能直接day%7,day%7就是默认1年1月1号为星期日,至于为什么要先+5,这个不难推导,读者自己想想就明白了 判断某月是不是Good month和Luckly month: 计算天数day后,令day++,进入sm的1号 此时判断sm的1号是不是为Good month,使用上面给出计算第day天是星期几的方法,若 1号为星期日(0)、星期六(6)或星期一(1),则该月为Good month 从sm月开始,把天数day逐月递增,逐月判断该月是否为Good month,判断方法都是一样的。 不难发现,若第k月为Good month,则第k-1月必定为Luckly month,因此两个计数器同时增加即可。 注意3点: (1) 边界:若sm为Good month,计数器good++,但计数器luck不变,因为sm-1月不在时间区间内。 若计算到em为Good month,则计数器luck++,good不变,因为day一开始就+1了,当day逐月递增到em时,实则day此时为第em+1月的1号,此时判断的是em+1月是否为Good month,若是,则第em月为Luckly month,但em+1月在时间区间内,不计入计数器 (2) 逐月递增时,若到达1752年9月,要 减11天 (3) 闰年平年的月份天数不同 代码如下: #include<iostream>
using namespace std;
int Month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; //平年月
int Lmonth[13]={0,31,29,31,30,31,30,31,31,30,31,30,31}; //闰年月
enum week{Sun,Mon,Tue,Wed,Thu,Fri,Sat}; //星期
bool leap(int year); //判断year是否为闰年
int ComputeDay(int y,int m); //计算从第1年1月1日到第y年m-1月的总天数+1 (即只包括第m个月的第一天)
int main(int i,int j,int* pm)
{
int test;
cin>>test;
for(int t=0;t<test;t++)
{
int ys,ms,ye,me;
cin>>ys>>ms>>ye>>me;
int luck=0,good=0;
int day=ComputeDay(ys,ms);
if(((day+5)%7<=Mon) || ((day+5)%7==Sat)) //计算起始ys年ms月1号为星期几,判断是否为good month
good++; //1年1月1号是星期六,而原本默认是星期日,因此+5调整
/*计算从ys年ms+1开始 到ye-1年的月份是否为good month*/
for(i=ys;i<ye;i++)
{
if(leap(i))
pm=Lmonth;
else
pm=Month;
if(i==ys)
j=ms;
else
j=1;
for(;j<=12;j++)
{
day+=*(pm+j);
if(i==1752 && j==9)
day-=11;
//由于day开始时+1缘故,当j时,计算的是第j+1月是否为good month
if(((day+5)%7<=Mon) || ((day+5)%7==Sat)) //计算j+1月1号为星期几,判断是否为good month
{
good++;
luck++; //当j+1月为good month,j月必为luck month
}
}
}
/*计算第ye年的good month*/
if(leap(i))
pm=Lmonth;
else
pm=Month;
if(i==ys) //若ye==ys
j=ms;
else
j=1;
for(;j<=me;j++)
{
day+=*(pm+j);
if(i==1752 && j==9)
day-=11;
//由于day开始时+1缘故,当j时,计算的是第j+1月是否为good month
if(((day+5)%7<=Mon) || ((day+5)%7==Sat)) //计算j+1月1号为星期几,判断是否为good month
{
if(j!=me)
good++;
luck++; //当j+1月为good month,j月必为luck month
}
}
cout<<luck<<' '<<good<<endl;
}
return 0;
}
bool leap(int year) //判断year是否为闰年
{
if(year<1582)
return !(year%4); //当year<1582时,只要能被4整除就是闰年
else
{
if(year==1700) //当year=1700时,历史原因,无条件为闰年
return true;
if((!(year%4)&&(year%100)) || !(year%400)) //当year>=1582时,能被4整除且不被100整除为闰年
return true; //或能被400整除时为闰年
}
return false;
}
int ComputeDay(int y,int m) //计算从第1年1月1日到第y年m-1月的总天数+1 (即只包括第m个月的第一天)
{ //"+1"是为了使从当月末变为下月初
int i,j,day=1;
for(i=1;i<y;i++)
if(leap(i))
day+=366;
else
day+=365;
for(j=1;j<m;j++)
if(leap(i))
day+=Lmonth[j];
else
day+=Month[j];
if(y>1752)
day-=11;
else if(y==1752 && m>9)
day-=11;
return day;
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 789虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 786选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 812题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 948题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 934字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1398题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 977大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1572题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2673是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1207在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 776从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2351题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1062题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3007
2012-05-14 10:21 949大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 963题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2117大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1590题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1225题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 895题意:Ted今年100岁,给出n对他家族的关系:“父 ... -
poj 1656
2012-04-19 10:07 1094题目要求:一道纯的模拟题目。 直接上代码: ...
相关推荐
北大POJ3393-Lucky and Good Months by Gregorian Calendar 解题报告+AC代码
包含15类的POJ推荐50题,可全面复习或学习算法。 除此外还包含三种级别的水平(初级、中级、高级)应掌握的算法及数据结构及... (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码