1631 小鲨鱼在51nod小学
1 秒131,072 KB20 分3 级题鲨鱼巨巨2.0(以下简称小鲨鱼)以优异的成绩考入了51nod小学。并依靠算法方面的特长,在班里担任了许多职务。
每一个职务都有一个起始时间A和结束时间B,意为小鲨鱼在[A, B]时间内,担任了某职务(inclusively)。
现在给定小鲨鱼的职务履历表,你可以高效的给出小鲨鱼在某天担任了哪些职务吗?
p.s. 由于小鲨鱼担任的职务太多,所有任期小于一个自然月的职务都忽略不计。(如1月1日~2月1日为一个自然月,即月份加1)
p.p.s. 输入数据保证小鲨鱼同时不担任超过200种职务。(牛!)
p.p.p.s 输入的日期均为合法日期,范围在2000年01月01日~2999年12月31日。
p.p.p.p.s巨大的输入输出,推荐使用scanf/printf,编译器推荐使用Virtual C++
收起
输入
第一行为一个整数n,代表小鲨鱼担任过N种职务。(1 <= n <= 10^5)接下来的n行,每一行为七个整数,y0, m0, d0, y1, m1, d1, x。意为在<y0, m0, d0>到<y1, m1, d1>时间内,小鲨鱼担任了职务x。(1 <= x <= 10^9)给定的时间皆合法,且起始日期小于或等于截止日期。职务x是唯一的。接下来是一个整数q,代表q次查询。(1 <= q <= 10^4)接下来的q行,每一行为三个整数<y, m, d>,代表查询的日期。时间皆合法。
输出
每一次查询输出一行结果。首先输出一个整数n,代表此时小鲨鱼担任的职务数。(n可以为0)接下来是n个整数,代表小鲨鱼担任的职务。职务列表保持升序。
输入样例
42000 01 01 2000 01 01 1112000 01 02 2001 02 02 2222000 01 28 2000 02 29 3332000 01 29 2000 02 28 44442000 01 012000 01 022000 01 282000 02 29
输出样例
01 222
#include <vector>#include <cstdio>#include <set>#include <iostream>#include <algorithm>using namespace std;struct date{int vis,number,f1,f2;}a[100001];bool cmp(date x,date y){if(y.f1==x.f1)return x.f2<y.f2;return x.f1<y.f1;}int main() { int n;cin>>n;for(int i=0;i<n;i++){int y0,m0,d0,y1,m1,d1;scanf("%d%d%d%d%d%d%d",&y0,&m0,&d0,&y1,&m1,&d1,&a[i].number);a[i].f1=y0*10000+m0*100+d0;a[i].f2=y1*10000+m1*100+d1;if(y0==y1){if(m0==m1) a[i].vis=0;else if((m1-m0)==1){if(d0<=d1) a[i].vis=1;else a[i].vis=0;}else a[i].vis=1;}else if((y1-y0)==1){if(m0==12&&m1==1){if(d0<=d1) a[i].vis=1;else a[i].vis=0;}else a[i].vis=1;}else a[i].vis=1;}sort(a,a+n,cmp);int Q;cin>>Q;while(Q--){int y,m,d,t;set<int> s;scanf("%d%d%d",&y,&m,&d);t=y*10000+m*100+d;for(int i=0;i<n;i++){if(t>=a[i].f1&&t<=a[i].f2&&a[i].vis) s.insert(a[i].number);}cout<<s.size();if(s.size()!=0){set<int>::iterator it;for(it=s.begin();it!=s.end();it++)printf(" %d",*it);}cout<<endl;}return 0;}
2 222 3332 222 333
解题思路
辣鸡水题,不想说了,没做的趁早遛了吧,毫无意义这个题。
AC代码
如果觉得《51Nod1631 小鲨鱼在51nod小学》对你有帮助,请点赞、收藏,并留下你的观点哦!