USACO Friday the Thirteenth —

USACO Friday the Thirteenth ——水题

题目链接：http://cerberus.delos.com:790/usacoprob2?a=EYxUgMg3whp&S=friday

题目大意：

　　意思比较简单。求1900年到1900+N年的每个月的13号落在了星期几。输出13号落在一个星期的每一天的次数。

题目思路：

　　方法一：

　　有个蔡勒公式：

　　　　 $w = \left(y+[\frac {y}{4}] + [\frac {c}{4}] - 2c + [\frac{26(m+1)} {10}] + d-1 \right) \mod 7$

这个公式可以根据某天的日期，算出这一天是星期几，套用一下就行了。

公式中的符號含義如下：

w：星期(计算所得的数值对应的星期：0-星期日; 1-星期一; 2-星期二; 3-星期三; 4-星期四; 5-星期五; 6-星期六)
c：世纪减1(即年份前两位数)
y：年（即年份后两位数）
m：月（m的取值範圍為3至14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月來計算，比如2003年 1月1日要看作2002年的13月1日來計算）
d：日
[　]：稱作高斯符號，代表取整，即只要整數部份。
mod：‎‎同餘‎（這裡代表括號裡的答案除以7後的餘數）

——选自维基百科

 1 /*
 2 ID: zypz457
 3 LANG: C++
 4 TASK: friday
 5  */
 6 #include <iostream>
 7 #include <cstring>
 8 #include <cstdio>
 9 #include <cstdlib>
10 #include <cmath>
11 using namespace std;
12 int n;
13 int cnt[7];
14 int cal(int y, int m, int d) {
15   int month = m, c;
16   if (month == 1) {
17     month = 13; y--;
18   } else if (month == 2) {
19     month = 14; y--;
20   } else {month = m;}
21   m = month;
22   c = y/100; y = y%100;
23   int ans = (y + y/4 + floor(c/4) -2*c + floor(26*(m+1)/10) + d - 1);
24   ans = (ans%7 + 7) % 7;
25   return ans;
26 }
27 void solve() {
28   scanf("%d", &n);
29   memset(cnt, 0, sizeof(cnt));
30   int y, j, i, month, ans;
31   for (i = 0; i < n; ++i) {
32     y = i + 1900;
33     for (j = 1; j <= 12; ++j) {
34       ans = cal(y, j, 13);
35       cnt[ans]++;
36     }
37   }
38   printf("%d ", cnt[6]);
39   for (i = 0; i < 5; ++i) printf("%d ", cnt[i]);
40   printf("%d\n", cnt[5]);
41 }
42 int main(void) {
43   freopen("friday.in", "r", stdin);
44   freopen("friday.out", "w", stdout);
45   solve();
46   return 0;
47 }

方法二：

　　参考：http://www.cnblogs.com/whatthefy/archive/2013/05/15/3080905.html 反而比较简单，直接暴力。因为最多400年，400×366在整型范围之内。

 1 /*
 2 ID: zypz457
 3 LANG: C++
 4 TASK: friday
 5  */
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 #include <cmath>
11 using namespace std;
12 int n;
13 int month[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
14 int cnt[7];
15 bool leap(int i) {
16   return ((i%4==0 && i%100!=0)||(i%400==0));
17 }
18 void solve() {
19   int n, i, j, sum = 0; 
20   memset(cnt, 0, sizeof(cnt));
21   scanf("%d", &n);
22   for (i = 1900; i < 1900+n; ++i) {
23     if (!leap(i)) {
24       month[2] = 28;
25     } else month[2] = 29;
26     for (j = 1; j <= 12; ++j) {
27       cnt[(13+sum)%7]++;
28       sum += month[j];
29     }
30   }
31   printf("%d ", cnt[6]);
32   for(i = 0; i < 5; ++i) printf("%d ", cnt[i]);
33   printf("%d\n", cnt[5]);
34 }
35 int main(void) {
36   freopen("friday.in", "r", stdin);
37   freopen("friday.out", "w", stdout);
38   solve();
39   return 0;
40 }

注意2月的时候判断，当初写的是month[2]--;这是不对的，因为每次都减1,当然不对了……囧