11008: 【原1008】二哥买期货
题目
题目描述
author: xjia 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1008
Description
二哥想知道在一段时期内，一共有多少个交易日。期货交易日的限定如下：
- 周六、周日不能交易
- 元旦期间（1月1日）不能交易
- 五一劳动节期间（5月1日至3日）不能交易
- 十一国庆节期间（10月1日至7日）不能交易
- 没有在上述要求中提到的日期均可交易
Input Format
第一行有一个整数n，表示一共有n组数据。
每组数据都有一行，是两个用空格分开的日期，分别为开始日期和结束日期。日期格式为YYYY-MM-DD（比如2010-11-11）；数据保证开始日期不晚于结束日期。
对于所有数据：\( n \leq 365 \)
对于30%的数据：日期范围从2010-11-23至2012-12-21
对于70%的数据：日期范围从1900-01-01至9999-12-31
Output Format
输出共n行，每行一个整数，对应于一组数据。
每组数据需要输出在指定日期区间内，共有多少个交易日；区间的开始和结束日期也算在内（如果是交易日的话）。
Sample Input
4
2010-11-18 2010-11-20
2010-01-01 2010-01-01
2010-05-01 2010-05-03
2010-10-01 2010-10-07
Sample Output
2
0
0
0
FineArtz's solution
/* 二哥买期货 */
#include <iostream>
#include <string>
using namespace std;
bool LeapYear[10000] = {0}, CanTrade[10000][13][32] = {0};
const short Day[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
short Week[10000][13][32] = {0}, CanTradeDays[10000] = {0};
struct Date{
//constructor
Date(const string&);
Date(int, int, int);
Date& operator ++();
friend inline bool operator ==(const Date&, const Date&);
friend inline bool operator !=(const Date&, const Date&);
int yy, mm, dd;
};
Date::Date(const string& s){
yy = mm = dd = 0;
for (int i = 0; i != 4; ++i)
yy = yy * 10 + s[i] - '0';
mm = (s[5] - '0') * 10 + s[6] - '0';
dd = (s[8] - '0') * 10 + s[9] - '0';
}
Date::Date(int y, int m, int d) : yy(y), mm(m), dd(d){}
Date& Date::operator ++(){
++dd;
if (mm != 2){
if (dd > Day[mm]){
dd = 1;
++mm;
if (mm > 12){
mm = 1;
++yy;
}
}
}
else{
if (dd > (LeapYear[yy] ? 29 : 28)){
dd = 1;
mm = 3;
}
}
return *this;
}
inline bool operator ==(const Date& lhs, const Date& rhs){
return (lhs.yy == rhs.yy && lhs.mm == rhs.mm && lhs.dd == rhs.dd);
}
inline bool operator !=(const Date& lhs, const Date& rhs){
return !(lhs == rhs);
}
inline int succ(int x) { return ((x + 1) % 7 == 0) ? 7 : ((x + 1) % 7); }
void PreTreatment(){
for (int i = 1900; i <= 9999; ++i)
LeapYear[i] = (i % 400 == 0 || (i % 4 == 0 && i % 100 != 0));
Week[1900][1][1] = 1;
for (int yy = 1900; yy <= 9999; ++yy){
int day = 0, lday = 0, year = yy;
for (int mm = 1; mm <= 12; ++mm)
{
if (mm != 2) day = Day[mm];
else day = (LeapYear[year] ? 29 : 28);
if (mm > 1) Week[yy][mm][1] = succ(Week[yy][mm - 1][lday]);
else if (yy != 1900) Week[yy][mm][1] = succ(Week[yy - 1][12][31]);
for (int dd = 2; dd <= day; ++dd)
Week[yy][mm][dd] = succ(Week[yy][mm][dd - 1]);
lday = day;
day = 0;
}
}
for (int yy = 1900; yy <= 9999; ++yy)
for (int mm = 1; mm <= 12; ++mm){
int day;
if (mm != 2) day = Day[mm];
else day = (LeapYear[yy] ? 29 : 28);
for (int dd = 1; dd <= day; ++dd){
CanTrade[yy][mm][dd] = !((Week[yy][mm][dd] == 6) || (Week[yy][mm][dd] == 7)
|| (mm == 1 && dd == 1) || (mm == 5 && dd <= 3) || (mm == 10 && dd <= 7));
if (CanTrade[yy][mm][dd]) ++CanTradeDays[yy];
}
}
}
int gap(const Date& d1, const Date& d2){
int ret = 0;
if (d1.yy + 1 >= d2.yy){
for (Date d(d1.yy, d1.mm, d1.dd); d != d2; ++d)
if (CanTrade[d.yy][d.mm][d.dd]) ++ret;
return (CanTrade[d2.yy][d2.mm][d2.dd] ? ++ret : ret);
}
for (Date d(d1.yy, d1.mm, d1.dd); d != Date(d1.yy + 1, 1, 1); ++d)
if (CanTrade[d.yy][d.mm][d.dd]) ++ret;
for (Date d(d2.yy, 1, 1); d != d2; ++d)
if (CanTrade[d.yy][d.mm][d.dd]) ++ret;
if (CanTrade[d2.yy][d2.mm][d2.dd]) ++ret;
for (int yy = d1.yy + 1; yy != d2.yy; ++yy)
ret += CanTradeDays[yy];
return ret;
}
int main(){
PreTreatment();
int n;
cin >> n;
for (int data = 0; data != n; ++data){
string s1, s2;
cin >> s1 >> s2;
Date date1(s1), date2(s2);
cout << gap(date1, date2) << endl;
}
return 0;
}
ligongzzz's solution
#include <iostream>
#include <stdio.h>
using namespace std;
int dayOfMonth[][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} };
struct Date
{
int y, m, d;
int leap()
{
return (y % 4 == 0 && y % 100 != 0 || y % 400 == 0 ? 1 : 0);
}
int week()
{
int Y = y, M = m;
if (m == 1 || m == 2)
{
Y--;
M += 12;
}
int W = (d + M * 2 + 3 * (M + 1) / 5 + Y + Y / 4 - Y / 100 + Y / 400) % 7;
return W + 1;
}
Date() {}
Date(int yy, int mm, int dd) { y = yy; m = mm; d = dd; }
Date getNext()
{
Date t(y, m, d);
if (d < dayOfMonth[leap()][m])
t.d += 1;
else if (m < 12)
{
t.m += 1;
t.d = 1;
}
else
{
t.y += 1;
t.m = 1;
t.d = 1;
}
return t;
}
bool dealDay()
{
if (week() == 6 || week() == 7)
return false;
if (m == 1 && d == 1 || m == 5 && d >= 1 && d <= 3 || m == 10 && d >= 1 && d <= 7)
return false;
return true;
}
bool isWeekend()
{
return week() == 6 || week() == 7;
}
};
bool equals(Date d1, Date d2)
{
return d1.y == d2.y && d1.m == d2.m && d1.d == d2.d;
}
int ansOfYear(int year)
{
bool isleap = (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
int res = (isleap ? 366 : 365), t1, t2, t3 = 0, i;
t1 = 104;
if (isleap)
{
if (Date(year, 12, 30).isWeekend())
t1 += 1;
if (Date(year, 12, 31).isWeekend())
t1 += 1;
}
else
{
if (Date(year, 12, 31).isWeekend())
t1 += 1;
}
t2 = 11;
if (Date(year, 1, 1).isWeekend())
t3 += 1;
for (i = 1; i < 4; i++)
if (Date(year, 5, i).isWeekend())
t3 += 1;
for (i = 1; i < 8; i++)
if (Date(year, 10, i).isWeekend())
t3 += 1;
res = res - t1 - t2 + t3;
return res;
}
int main()
{
int n, res = 0, i;
Date d1, d2, t;
scanf("%d", &n);
while (n--)
{
res = 0;
scanf("%d-%d-%d %d-%d-%d", &d1.y, &d1.m, &d1.d, &d2.y, &d2.m, &d2.d);
if (d2.y - d1.y <= 1)
{
for (t = d1; !equals(t, d2.getNext()); t = t.getNext())
if (t.dealDay())
res += 1;
}
else
{
for (t = d1; !equals(t, Date(d1.y + 1, 1, 1)); t = t.getNext())
if (t.dealDay())
res += 1;
for (t = Date(d2.y, 1, 1); !equals(t, d2.getNext()); t = t.getNext())
if (t.dealDay())
res += 1;
for (i = d1.y + 1; i < d2.y; i++)
res += ansOfYear(i);
}
printf("%d\n", res);
}
return 0;
}
yyong119's solution
#include <iostream>
using namespace std;
int monthDays[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
struct date {
int year;
int month;
int day;
int dayForWeek;
};
int getWeek(const date &d) {
int m = d.month, y = d.year;
if(d.month <= 2) {
m += 12;
--y;
}
int dayForWeek = (d.day + 2 + 2 * m + 3 * (m + 1) / 5 - 1 + y + y / 4 - y / 100 + y / 400) % 7;
return dayForWeek;
}
int countDays(const date& d1, const date& d2) {
bool isLeap(int);
int count = 0, month, year;
if(d1.year == d2.year)
if(d1.month == d2.month)
return (d2.day - d1.day + 1);
else {
count = monthDays[d1.month] - d1.day + 1 + d2.day;
for (month = d1.month + 1; month < d2.month; ++month) count += monthDays[month];
if (2 >= d1.month && 2 < d2.month && isLeap(d1.year)) ++count;
return count;
}
else {
date d3 = {d1.year, 12, 31}, d4 = {d2.year, 1, 1};
count = countDays(d1, d3) + countDays(d4, d2);
for(year = d1.year + 1; year < d2.year; ++year) {
count += 365;
if(isLeap(year)) ++count;
}
return count;
}
}
bool isLeap(int year) {
return ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0);
}
bool betwDays(date &d1,date &d2,date &d3) {
if (d1.year < d3.year && d3.year < d2.year) return true;
else if(d3.year < d1.year || d3.year > d2.year) return false;
else if(d3.year == d1.year)
if(d1.year == d2.year) {
if(d1.month < d3.month && d3.month < d2.month) return true;
else if(d3.month < d1.month || d3.month > d2.month) return false;
else if(d3.month == d1.month)
if(d1.month == d2.month)
if(d1.day <= d3.day && d3.day <= d2.day)return true;
else return false;
else
if(d3.day >= d1.day) return true;
else return false;
else
if(d3.day <= d2.day)return true;
else return false;
}
else {
date d4 = {d1.year, 12, 31};
return (betwDays(d1, d4, d3));
}
else {
date d4 = {d2.year, 1, 1};
return (betwDays(d4, d2, d3));
}
}
void dayUp(date &d) {
bool isLeap(int);
++d.day;
if(d.day > monthDays[d.month] + (d.month == 2 && isLeap(d.year))) {
d.day=1;
++d.month;
if(d.month > 12) {
d.month = 1;
++d.year;
}
}
++d.dayForWeek;
if(d.dayForWeek > 6) d.dayForWeek = 0;
}
int main() {
date d1, d2, dtemp;
char eat;
int n, *p, i, j, daysNum, holidays, year;
cin >> n;
p = new int[n];
for(i = 0; i < n; ++i) {
cin >> d1.year >> eat >> d1.month >> eat >> d1.day;
cin >> d2.year >> eat >> d2.month >> eat >> d2.day;
d1.dayForWeek = getWeek(d1);
d2.dayForWeek = getWeek(d2);
daysNum = countDays(d1, d2);
holidays = daysNum / 7 * 2;
for(dtemp = d1, j = 0; j < daysNum % 7; ++j) {
if(dtemp.dayForWeek == 0 || dtemp.dayForWeek == 6) ++holidays;
dayUp(dtemp);
}
for(year = d1.year; year <= d2.year; ++year) {
dtemp.year = year;
dtemp.month = dtemp.day = 1;
dtemp.dayForWeek = getWeek(dtemp);
if(year != d1.year && year != d2.year || betwDays(d1, d2, dtemp))
holidays += (dtemp.dayForWeek != 0 && dtemp.dayForWeek != 6);
dtemp.month = 5;
dtemp.day = 1;
dtemp.dayForWeek = getWeek(dtemp);
for(j = 0; j < 3; ++j) {
if(year != d1.year && year != d2.year || betwDays(d1, d2, dtemp))
holidays += (dtemp.dayForWeek != 0 && dtemp.dayForWeek != 6);
dayUp(dtemp);
}
dtemp.month = 10;
dtemp.day = 1;
dtemp.dayForWeek = getWeek(dtemp);
for(j = 0; j < 7; ++j) {
if(year != d1.year && year != d2.year || betwDays(d1, d2, dtemp))
holidays += (dtemp.dayForWeek != 0 && dtemp.dayForWeek != 6);
dayUp(dtemp);
}
}
p[i] = daysNum - holidays;
}
for(i = 0; i < n; ++i) cout << p[i] << endl;
delete [] p;
return 0;
}