uva 1032解题报告
2019/3/26 xzc 23:35
vjudge链接
题意：
给出n个(n<=100)日期的闭区间，组成一个集合A
又给出m个(m<=100)日期的闭区间，组成一个新的集合B
求集合B减去集合A的差集(A中的所有区间的日子的票价都已知),所求的区间相邻的要合并
样例：
Sample Input
1 1
19900101 19901231
19901201 20000131
0 3
19720101 19720131
19720201 19720228
19720301 19720301
1 1
20010101 20011231
20010515 20010901
0 0
Sample Output
Case 1:
1/1/1991 to 1/31/2000
Case 2:
1/1/1972 to 2/28/1972
3/1/1972
Case 3:
No additional quotes are required.
思路：
- 先把集合A，B区间排序，合并
- 求差集的时候取出A中每个区间，和B中的区间for一遍相比较，遇到和B中的某个区间有重叠的部分，就割掉这部分
- 具体见代码实现
- 数据范围100，O(n^2)完全可以，不然还可以加一个优化，循环B的时候不从第一个开始，可以lower_bound()
上代码(0ms)
- 我用了sscanf从字符串中读入日期
- 写了一个struct Date,重载了运算符
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 1e5+100;
bool isLeap(int year)
{
return ((year%4==0&&year%100)||(year%400==0));
}
int Days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
struct Date{
int year,month,day;
Date(){}
Date(int y,int m,int d):year(y),month(m),day(d){}
bool operator < (const Date& rhs)const{
if(year!=rhs.year) return year < rhs.year;
if(month!=rhs.month) return month < rhs.month;
return day < rhs.day;
}
bool operator == (const Date& rhs)const{
return year==rhs.year&&month==rhs.month&&day==rhs.day;
}
bool operator <= (const Date& rhs)const{
return *this<rhs||*this==rhs;
}
void Print()
{
printf("%d/%d/%d",month,day,year);
}
void getMessage(int &y,int &m,int &d)
{
y = year, m = month, d = day;
}
};
Date nextDay(Date today)
{
int year,month,day;
today.getMessage(year,month,day);
Days[2] = 28 + isLeap(year);
if(++day>Days[month]) day = 1,++month;
if(month>12) month = 1,++year;
return Date(year,month,day);
}
Date preDay(Date today)
{
int year,month,day;
today.getMessage(year,month,day);
Days[2] = 28 + isLeap(year);
if(day>1)
return Date(year,month,day-1);
if(month>1)
return Date(year,month-1,Days[month-1]);
return Date(year-1,12,31);
}
char str[10];
void getDate(int &y,int &m,int &d)
{
scanf("%s",str);
sscanf(str,"%4d%2d%2d",&y,&m,&d);
}
void makeEasy(vector<pair<Date,Date> > &x,vector<pair<Date,Date> > &y)
{ ///把区间集合x去重，合并以后，结果保存到y里面
if(!x.size()) return;
int len = x.size();
y.pb(x[0]);
int cnt = 0; //ans(y)区间最后一个元素的下标
for(int i=1;i<len;++i)
{
if(nextDay(y[cnt].second) < x[i].first) //第i个区间和前一个区间没有交集，直接push
{
y.pb(x[i]); ++cnt;
}
else
{
y[cnt].second = max(y[cnt].second,x[i].second) ;
}
}
}
void show(pair<Date,Date> &x)
{
printf(" ");
if(x.first==x.second) x.first.Print();
else x.first.Print(),printf(" to "),x.second.Print();
printf("\n");
}
void showSet(vector<pair<Date,Date> > &s)
{
for(auto& x:s)
show(x);
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int nx,nr,ca=0,y1,m1,d1,y2,m2,d2;
while(scanf("%d%d",&nx,&nr)!=EOF&&(nx||nr))
{
if(ca) printf("\n");
printf("Case %d:\n",++ca);
vector<pair<Date,Date> > dx,dr;
For(i,1,nx)
{
getDate(y1,m1,d1);
getDate(y2,m2,d2);
dx.pb( MP( Date(y1,m1,d1) , Date(y2,m2,d2) ) );
}
sort(dx.begin(),dx.end() );
For(i,1,nr)
{
getDate(y1,m1,d1);
getDate(y2,m2,d2);
dr.pb( MP( Date(y1,m1,d1) , Date(y2,m2,d2) ) );
}
sort(dr.begin(),dr.end() );
vector<pair<Date,Date> > ask,hasKnown;
makeEasy(dr,ask); //合并要查询区间
makeEasy(dx,hasKnown); //合并已知的区间
if(!hasKnown.size())
{
showSet(ask);
continue;
}
hasKnown.pb(MP(Date(10000,12,30),Date(10000,12,31)));
vector<pair<Date,Date> > ans;
for(const auto &x:ask) //查询的区间
{
Date left = x.first;
Date right = x.second;
for(const auto& y:hasKnown)
{
if(y.second < left) continue; //该原始区间在要查询区间的左边(相离)
if(right<y.first) //该原始区间在要查询区间的右边
{
ans.pb(MP(left,right));
break;
}
//两个区间有交集了
if(y.first<=left&&right<=y.second)
{
break; //全切掉了
}
if(left<y.first&&right<=y.second) //右边被割没了
{
ans.pb( MP ( left, preDay (y.first)));
break;
}
if(y.first<=left&&y.second<right) //左边被割没了
{
left = nextDay(y.second);continue;
}
//[left,right]两头都比y范围大
ans.pb(MP(left,preDay(y.first)));
left = nextDay(y.second);
}
}
if(!ans.size())
{
printf(" No additional quotes are required.\n");continue;
}
for(auto &x:ans)
show(x);
}
return 0;
}
附题面：
A research group is developing a computer program that will fetch historical stock market quotes from
a service that charges a fixed fee for each day’s quotes that it delivers. The group has examined the
collection of previously-requested quotes and discovered a lot of duplication, resulting in wasted money.
So the new program will maintain a list of all past quotes requested by members of the group. When
additional quotes are required, only quotes for those dates not previously obtained will be fetched from
the service, thus minimizing the cost.
You are to write a program that d etermines when new quotes are required. Input for the program
consists of the date ranges for which quotes have been requested in the past and the date ranges for
which quotes are required. The program will then determine the date ranges for which quotes must be
fetched from the service.
Input
There will be multiple input cases. The input for each case begins with two non-negative integers NX
and NR, (0 ≤ NX, NR ≤ 100). NX is the number of existing date ranges for quotes requested in
the past. NR is the number of date ranges in the incoming requests for quotes. Following these are
NX + NR pairs of dates. The first date in each pair will be less than or equal to the second date in
the pair. The first NX pairs specify the date ranges of quotes which have been requested and obtained
in the past, and the next NR pairs specify the date ranges for which quotes are required.
Two zeroes will follow the input data for the last case.
Each input date will be given in the form Y Y Y Y MMDD. Y Y Y Y is the year (1700 to 2100), MM
is the month (01 to 12), and DD is the day (in the allowed range for the given month and year). Recall
that months 04, 06, 09, and 11 have 30 days, months 01, 03, 05, 07, 08, 10, and 12 have 31 days, and
month 02 has 28 days except in leap years, when it has 29 days. A year is a leap year if it is evenly
divisible by 4 and is not a century year (a multiple of 100), or if it is divisible by 400.
Output
For each input case, display the case number (1, 2, . . . ) followed by a list of any date ranges for which
quotes must be fetched from the service, one date range per output line. Use the American date format
shown in the sample output below. Explicitly indicate (as shown) if no additional quotes must be
fetched. If two date ranges are contiguous or overlap, then merge them into a single date range. If a
date range consists of a single date, print it as a single date, not as a range consisting of two identical
dates. Display the date ranges in chronological order, starting with the earliest date range.
Sample Input
1 1
19900101 19901231
19901201 20000131
0 3
19720101 19720131
19720201 19720228
19720301 19720301
1 1
20010101 20011231
20010515 20010901
0 0
Sample Output
Case 1:
1/1/1991 to 1/31/2000
Case 2:
1/1/1972 to 2/28/1972
3/1/1972
Case 3:
No additional quotes are required.
大样例:
uva的debug网址：
https://www.udebug.com/UVa/1032
![关于多项式的一点研究及其在ACM竞赛中的应用 关于多项式的一点研究及其在ACM竞赛中的应用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)