上交OJ-1008. 二哥买期货
2018-05-16 本文已影响18人
code猪
- 二哥买期货
Description
二哥想知道在一段时期内，一共有多少个交易日。期货交易日的限定如下：
- 周六、周日不能交易
- 元旦期间（1月1日）不能交易
- 五一劳动节期间（5月1日至3日）不能交易
- 十一国庆节期间（10月1日至7日）不能交易
- 没有在上述要求中提到的日期均可交易
Input Format
第一行有一个整数n，表示一共有n组数据。
每组数据都有一行，是两个用空格分开的日期，分别为开始日期和结束日期。日期格式为YYYY-MM-DD（比如2010-11-11）；数据保证开始日期不晚于结束日期。
对于所有数据：n≤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
分析
这个题真是变态，没有看过Linux的时间相关源码根本就完成不了。
使用一般方法，一定会超时。
计算一个日期从1年1月1日的天数，快速方法：
if((m-=2)<=0) {
y--;
m+=12;
}
return y/4-y/100+y/400+367*m/12+d+y*365-719499
而计算一个日期星期几，快速方法：
int day[]={0,3,2,5,0,3,5,1,4,6,2,4};
y-=m<3;
int week=(y+y/4-y/100+y/400+day[m-1]+d)%7;
return week==0 ? 7 : week;
这个题的源码如下，其中注释的代码是我没有百度的代码，正确但超时！
#include <iostream>
using namespace std;
bool is_run(int y) //判断是否为润年
{
if(0==y%400)
return true;
else if((0!=y%100) && (0==y%4))
return true;
else
return false;
}
int days_from_1900_01_01(int y, int m, int d) //计算从固定日期起的天数
{
/*int i,j,k;
int sum=0;
for(i=1900;i<y;i++) {
if(is_run(i))
sum+=366;
else
sum+=365;
}
for(i=1;i<m;i++) {
switch(i) {
case 1: sum+=31; break;
case 2: is_run(y) ? sum+=29 : sum+=28; break;
case 3: sum+=31; break;
case 4: sum+=30; break;
case 5: sum+=31; break;
case 6: sum+=30; break;
case 7: sum+=31; break;
case 8: sum+=31; break;
case 9: sum+=30; break;
case 10: sum+=31; break;
case 11: sum+=30; break;
}
}
sum+=d;
return sum;*/
/*使用快速方法从1年1月1日计算*/
if((m-=2)<=0) {
y--;
m+=12;
}
return y/4-y/100+y/400+367*m/12+d+y*365-719499;
}
int day_week(int y, int m, int d) //计算星期几
{
// int week=days_from_1900_01_01(y,m,d)%7;
int day[]={0,3,2,5,0,3,5,1,4,6,2,4};
y-=m<3;
int week=(y+y/4-y/100+y/400+day[m-1]+d)%7;
return week==0 ? 7 : week;
}
bool is_weekend(int y, int m, int d) //判断是否为周末
{
int week=days_from_1900_01_01(y,m,d)%7;
if(week==0 || week==6)
return true;
else
return false;
}
int num_weekend(int y, int m, int d) //计算从固定日期起周末的数目
{
int num_all=days_from_1900_01_01(y,m,d);
int num=(num_all/7)*2;
if((num_all%7)==6)
return num+1;
else
return num;
}
int cmp_data(int y1, int m1, int d1, int y2, int m2, int d2) //日期比较
{
if(y1<y2)
return -1;
else if(y1>y2)
return 1;
if(m1<m2)
return -1;
else if(m1>m2)
return 1;
if(d1<d2)
return -1;
else if(d1>d2)
return 1;
else
return 0;
}
int count_deal_from_1900_01_01(int y, int m, int d) //计算从固定日期起可交易的天数
{
int sum=days_from_1900_01_01(y,m,d)-num_weekend(y,m,d);
int i,j,k;
for(i=1900; i<=y; i++) {
if(!is_weekend(i,1,1))
sum-=1;
for(j=1;j<=3;j++) {
if(cmp_data(y,m,d,i,5,j)>=0 && !is_weekend(i,5,j))
sum-=1;
}
for(j=1;j<=7;j++) {
if(cmp_data(y,m,d,i,10,j)>=0 && !is_weekend(i,10,j))
sum-=1;
}
}
return sum;
}
int is_deal_day(int y, int m, int d) //判断固定日期是否为交易日
{
if(is_weekend(y,m,d))
return 0;
if(cmp_data(y,m,d,y,1,1)==0)
return 0;
for(int i=1;i<=3;i++) {
if(cmp_data(y,m,d,y,5,i)==0)
return 0;
}
for(int i;i<=7;i++) {
if(cmp_data(y,m,d,y,10,i)==0)
return 0;
}
return 1;
}
int main()
{
int n;
int result[365];
int y1,m1,d1;
int y2,m2,d2;
int i,j,k;
cin>>n;
for(i=0;i<n;i++) {
char tmp[11] ;
cin>>tmp;
y1=(tmp[0]-'0')*1000+(tmp[1]-'0')*100+(tmp[2]-'0')*10+(tmp[3]-'0');
m1=(tmp[5]-'0')*10+(tmp[6]-'0');
d1=(tmp[8]-'0')*10+(tmp[9]-'0');
cin>>tmp;
y2=(tmp[0]-'0')*1000+(tmp[1]-'0')*100+(tmp[2]-'0')*10+(tmp[3]-'0');
m2=(tmp[5]-'0')*10+(tmp[6]-'0');
d2=(tmp[8]-'0')*10+(tmp[9]-'0');
result[i]=count_deal_from_1900_01_01(y2,m2,d2)-count_deal_from_1900_01_01(y1,m1,d1)+is_deal_day(y1,m1,d1);
}
for(i=0;i<n;i++)
cout<<result[i]<<endl;
return 0;
}
