1008. 二哥买期货

http://acm.sjtu.edu.cn/OnlineJudge/problem/1008

对起始年份和结束年份，可以对每一天单独判断；

对中间的每个整年，周末总的天数分为两部分：

1. 每个整年恰有完整的52个周，所以至少有 2*52 天是周末；

2. 闰年时，366%7 = 2，需要判断12-31和12-30是否为周末即可，平年需要判断12-31是否为周末；

对中间的每个整年，都有11天假日，注意周末与假日重合的情况。

这道题麻烦之处在于星期的计算和周末与假日重合时的处理。

星期的计算公式：

1 int getweek(int y, int m, int d)
2 {
3     if (m==1 || m==2) m += 12, y -= 1;
4     return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1) % 7;
5 }

单独对每个假日进行判断，就避免了周末与假日重合时重复计算：

int holidays[11][2] = {{1,1}, {5,1}, {5,2}, {5,3}, {10,1}, {10,2}, {10,3}, {10,4}, {10,5}, {10,6}, {10,7}};

for (int j = 0; j < 11; ++j) {
    if (isWeekend(curYear, holidays[j][0], holidays[j][1]))
        ++ans;
}

(枚举的做法会超时，不过需要对拍时很有用。)

  1 # include <stdio.h>
  2 
  3 int holidays[11][2] = {{1,1}, {5,1}, {5,2}, {5,3}, {10,1}, {10,2}, {10,3}, {10,4}, {10,5}, {10,6}, {10,7}};
  4 
  5 int getweek(int y, int m, int d)
  6 {
  7     if (m==1 || m==2) m += 12, y -= 1;
  8     return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1) % 7;
  9 }
 10 bool isWeekend(int y, int m, int d)
 11 {
 12     int w = getweek(y, m, d);
 13     return (w==0 || w==6);
 14 }
 15 
 16 const int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
 17 bool isLeapYear(int year) { return year%400==0 || (year%4==0 && year%100!=0); }
 18 
 19 void getdate(int &y, int &m, int &d)
 20 {
 21     char s[20];
 22     scanf("%s", s);
 23     y = (s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+(s[3]-'0');
 24     m = (s[5]-'0')*10+(s[6]-'0');
 25     d = (s[8]-'0')*10+(s[9]-'0');
 26 }
 27 
 28 bool isHoliday(int m, int d)
 29 {
 30     for (int i = 0; i < 11; ++i) {
 31         if (holidays[i][0] == m && holidays[i][1] == d) return true;
 32     }
 33     return false;
 34 }
 35 
 36 bool isEndOfMonth(int y, int m, int d)
 37 {
 38     if (m != 2 && d == days[m]) return true;
 39     else if (m==2) {
 40         if (isLeapYear(y)) return d == 29;
 41         else return d == 28;
 42     }
 43     return false;
 44 }
 45 
 46 int cal(int year, int m, int d, int mm, int dd)
 47 {
 48     int cnt = 0;
 49     for (int i = m, j = d; i < mm || (i==mm && j<=dd); ) {
 50         if (!isWeekend(year, i, j) && !isHoliday(i, j)) {
 51             ++cnt;
 52         }
 53         if (isEndOfMonth(year, i, j)) {
 54             ++i, j = 1;
 55         } else {
 56             ++j;
 57         }
 58     }
 59     return cnt;
 60 }
 61 
 62 void solve(void)
 63 {
 64     int n;
 65     int y1, m1, d1;
 66     int y2, m2, d2;
 67     scanf("%d", &n);
 68     while (n--) {
 69         getdate(y1, m1, d1);
 70         getdate(y2, m2, d2);
 71 
 72         int ans = 0;
 73 
 74         if (y1 == y2) {
 75             ans = cal(y1, m1, d1, m2, d2);
 76         } else {
 77             ans = cal(y1, m1, d1, 12, 31) + cal(y2, 1, 1, m2, d2);
 78             for (int i = y1+1; i < y2; ++i) {
 79                 if (isLeapYear(i)) {
 80                     ans += 366-52*2;
 81                     if (isWeekend(i, 12, 30)) --ans;
 82                     if (isWeekend(i, 12, 31)) --ans;
 83                 } else {
 84                     ans += 365-52*2;
 85                     if (isWeekend(i, 12, 31)) --ans;
 86                 }
 87                 ans -= 11;
 88                 for (int j = 0; j < 11; ++j) {
 89                     if (isWeekend(i, holidays[j][0], holidays[j][1]))
 90                         ++ans;
 91                 }
 92             }
 93         }
 94 
 95         printf("%d
", ans);
 96     }
 97 }
 98 
 99 int main()
100 {
101     solve();
102 
103     return 0;
104 }

View Code