USACO Friday the Thirteenth ——水题

May 21, 2013
USACO

题目链接：http://cerberus.delos.com:790/usacoprob2?a=EYxUgMg3whp&S=friday 题目大意：　　意思比较简单。求1900年到1900+N年的每个月的13号落在了星期几。输出13号落在一个星期的每一天的次数。题目思路：　　方法一：　　有个蔡勒公式：　　　　这个公式可以根据某天的日期，算出这一天是星期几，套用一下就行了。公式中的符號含義如下： ——选自维基百科


/*
ID: zypz457
LANG: C++
TASK: friday
 */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
int n;
int cnt[7];
int cal(int y, int m, int d) {
  int month = m, c;
  if (month == 1) {
    month = 13; y--;
  } else if (month == 2) {
    month = 14; y--;
  } else {month = m;}
  m = month;
  c = y/100; y = y%100;
  int ans = (y + y/4 + floor(c/4) -2*c + floor(26*(m+1)/10) + d - 1);
  ans = (ans%7 + 7) % 7;
  return ans;
}
void solve() {
  scanf("%d", &n);
  memset(cnt, 0, sizeof(cnt));
  int y, j, i, month, ans;
  for (i = 0; i < n; ++i) {
    y = i + 1900;
    for (j = 1; j <= 12; ++j) {
      ans = cal(y, j, 13);
      cnt[ans]++;
    }
  }
  printf("%d ", cnt[6]);
  for (i = 0; i < 5; ++i) printf("%d ", cnt[i]);
  printf("%d\n", cnt[5]);
}
int main(void) {
  freopen("friday.in", "r", stdin);
  freopen("friday.out", "w", stdout);
  solve();
  return 0;
}

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


/*
ID: zypz457
LANG: C++
TASK: friday
 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
int n;
int month[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
int cnt[7];
bool leap(int i) {
  return ((i%4==0 && i%100!=0)||(i%400==0));
}
void solve() {
  int n, i, j, sum = 0; 
  memset(cnt, 0, sizeof(cnt));
  scanf("%d", &n);
  for (i = 1900; i < 1900+n; ++i) {
    if (!leap(i)) {
      month[2] = 28;
    } else month[2] = 29;
    for (j = 1; j <= 12; ++j) {
      cnt[(13+sum)%7]++;
      sum += month[j];
    }
  }
  printf("%d ", cnt[6]);
  for(i = 0; i < 5; ++i) printf("%d ", cnt[i]);
  printf("%d\n", cnt[5]);
}
int main(void) {
  freopen("friday.in", "r", stdin);
  freopen("friday.out", "w", stdout);
  solve();
  return 0;
}

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

Read more