GMOJ.1002【USACO题库】1.1.3 Friday the Thirteenth黑色星期五

题目描述

13号又是星期五是一个不寻常的日子吗?
13号在星期五比在其他日少吗?为了回答这个问题,写一个程序来计算在n年里13
日落在星期一,星期二…星期日的次数.这个测试从1900年1月1日到
1900+n-1年12月31日.n是一个非负数且不大于400.
这里有一些你要知道的:

  1. 1900年1月1日是星期一.
  2. 4,6,11和9月有30天.其他月份除了2月有31天.闰年2月有29天,平年2月有28天.
  3. 年份可以被4整除的为闰年(1992=4*498 所以 1992年是闰年,但是1990年不是闰年)
  4. 以上规则不适合于世纪年.可以被400整除的世纪年为闰年,否则为平年.所以,1700,1800,1900和2100年是平年,而2000年是闰年.
    请不要预先算好数据!

输入

一个整数n.

输出

七个在一行且相分开的整数,它们代表13日是星期六,星期日,星期一…星期五的次数.

样例输入

20

样例输出

36 33 34 33 35 35 34

这题有坑!!!

  1. 1900年1月1日是星期一(不是六)
  2. 先输出星期六!!!
  3. 到1900+n-1年12月31日!!!

看完题目,感觉心中有千万只*奔腾而过…

不是照样做对了吗

经过一番思考 乱搞 , 我想出了一种思路:

穷(bào)举(lì)大法好啊!!!

思路:
从当天起,一日一日判断日期,逢13累加。(简单粗暴)

Code:

#include<bits/stdc++.h>
using namespace std;

const int yue[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
int n=1900,nn,month=1,dayj=1,week=1,ryear;
int day[8];

bool pd(int x)                                //判断闰年
{
	if((x % 100 == 0 && x % 400 == 0) || (x % 100 != 0 && x % 4 == 0))
		return true;
	return false;
}

int main()
{
	freopen("friday.in","r",stdin);
	freopen("friday.out","w",stdout);
	
	cin>>nn;
	while(1)      //穷举
	{
		if(n == 1900+nn && month == 1 && dayj == 1)
		{
			break;
		}
		
		ryear = pd(n) ? 1 : 0;
		dayj++;
		week++;
		
		if(dayj > yue[ryear][month])            //归1
		{
			dayj=1;
			month++;
		}
		if(month > 12)
		{
			month=1;
			n++;
		}
		if(week > 7)
		{
			week=1;
		}
		if(dayj == 13)
		{
			day[week]++;
		}
	}
	
	cout<<day[6]<<" "<<day[7]<<" "<<day[1]<<" "<<day[2]<<" "<<day[3]<<" "<<day[4]<<" "<<day[5]<<endl;  //输出
	return 0;
}

谁都别走,后面还有!

然鹅,这种方法太无脑了。
急需优化!

思路2:
一月一月地累加,并算出下个月的十三号是周几。

公式:闰年加上 day13=day13%7+1 ,然后(闰平年一样) day13=(day13+month[j]-1)%7+1。

Code2:

#include<bits/stdc++.h>
using namespace std;

const int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int n,day13=6;
int day[8];

int main()
{
	freopen("friday.in","r",stdin);
	freopen("friday.out","w",stdout);
	
    cin>>n;
    for(int i=1900;i<=1900+n-1;i++)
	{
        for(int j=1;j<=12;j++)
		{
            day[day13]++;
            if(j == 2 && i % 4 == 0 && (i % 100 != 0 || i % 400 == 0))       //判断闰年
                day13=day13%7+1;                  //公式
            day13=(day13+month[j]-1)%7+1; //公式
        }
    }
    
    cout<<day[6]<<" "<<day[7]<<" "<<day[1]<<" "<<day[2]<<" "<<day[3]<<" "<<day[4]<<" "<<day[5]<<endl;
    return 0;
}

我看谁敢走,还没完!

传说有一种推算星期几的公式,叫“蔡勒公式”!

蔡勒(Zeller)公式,是一个计算星期的公式,随便给一个日期,就能用这个公式推算出是星期几。
1582年10月4日后:w = (d + 1+ 2m+3(m+1)/5+y+y/4-y/100+y/400)%7;
1582年10月4日前:w = (d+1+2m+3(m+1)/5+y+y/4+5) % 7;

w:星期; w对7取模得:0-星期日,1-星期一,2-星期二,3-星期三,4-星期四,5-星期五,6-星期六
c:世纪(注:一般情况下,在公式中取值为已经过的世纪数,也就是年份除以一百的结果,而非正在进行的世纪,也就是现在常用的年份除以一百加一;不过如果年份是公元前的年份且非整百数的话,c应该等于所在世纪的编号,如公元前253年,是公元前3世纪,c就等于-3)
y:年(一般情况下是后两位数,如果是公元前的年份且非整百数,y应该等于cMOD100+100)
m:月(m大于等于3,小于等于14,即在蔡勒公式中,某年的1、2月要看作上一年的13、14月来计算,比如2003年1月1日要看作2002年的13月1日来计算)
d:日
[ ]代表取整,即只要整数部分。
不过,蔡勒公式只适合于1582年(中国明朝万历十年)10月15日之后的情形。罗马教皇格里高利十三世在1582年组织了一批天文学家,根据哥白尼日心说计算出来的数据,对儒略历作了修改。将1582年10月5日到14日之间的10天宣布撤销,继10月4日之后为10月15日。

以上内容来自百度百科。

这么说,我们只需将Code2修改一点就可以了!

Code3:

#include<bits/stdc++.h>
using namespace std;

int n;
int day[8];
int month[13][2]={{0, 0},{31, 31},{28, 29},{31, 31},{30, 30},{31, 31},{30, 30},{31, 31},{31, 31},{30, 30},{31, 31},{30, 30},{31, 31}};

bool pd(int x)
{
	if((x % 100 == 0 && x % 400 == 0) || (x % 100 != 0 && x % 4 == 0))
		return true;
	return false;
}
  
int main()
{
	freopen("friday.in","r",stdin);
	freopen("friday.out","w",stdout);
	
    cin>>n;
    for(int i=0;i<n;i++)
	{
        int days=0,t=pd(1900+i),n=1900+i;
        for(int j=1;j<=12;j++)
        {
            int d=days+13;
            day[((n-1)+(n-1)/4-(n-1)/100+(n-1)/400+d)%7]++;                                    //公式
            days+=month[j][t];
        }
    }
    cout<<day[6]<<" "<<day[0]<<" "<<day[1]<<" "<<day[2]<<" "<<day[3]<<" "<<day[4]<<" "<<day[5]<<endl;
    return 0;
}

然后,就真的没有然后了。

难道没人注意month有三种写法?

上一篇:梳排序算法


下一篇:如何通过C#开发一个媒体播放器(下)