CSP 201712-3 Crontab(0→85→95→100)
tag:复杂模拟 字符串 日期
题面链接
http://118.190.20.162/view.page?gpid=T66.
题意
题目为任务的调度问题，个人感觉跟平常使用的日历中的日程计划比较类似。题目会给出多个任务以及该任务的执行时间，时间有可能是重复性的，我们需要做的就是按照时间先后输出执行的所有任务。
思路
采取构造的方式：对于给定任务，构造所有会执行的时间，用数据结构map（时间：任务列表）进行存储，由于map本身是有序的，所以处理完所有任务后，遍历map输出即可。
问题转化为如何构造给定任务的所有执行时间，可以先求出分钟、小时、日、月、星期的可行时间，然后进行组合，组合出yyyymmddHHMM格式的日期，其中星期由于没有显式位于日期中，因此采取对组合后的日期进行星期验证的方式保证星期的可行性。另外对于“*”即任意的情况，采取将取值范围内所有值均加入的方式进行处理，但因为构造日期可能不位于给定起始日期s,终止日期t之间、不同月份天数不同的问题可能出现非法日期（比如：0231，2月31日）等原因，所以对于构造的日期需要进一步进行检验保证其正确性。
需要注意的几个细节如下：
1.csp 编译器比较古老，不支持一些函数如stoi、tostring的使用；（0分：编译错误）
2.月份、星期的英文缩写不区分大小写；（85分）
3.可能存在区间重合问题，比如：3，1-5 如不特殊考虑，则3就构造多次，导致出错。（95分）
源码
#include <bits/stdc .h>#define endl '\n'using namespace std;typedef long long ll;map<string,vector<string> >mp;//时间：指令map<string,vector<string> >::iterator iter;//迭代器map<string,string> mpchar_num;//英文：数字。比如，Jan:01，Sun:00map<string,string> mp_week;//时间：周typedef struct {int year,month,day,hour,minutes;}node;node start,endt;string g_s,g_t,sminute,shour,sday,smonth,sweek,instructment;//ccf编译器不支持 my_stoi，my_to_string:进行转化int my_stoi(string s){return atoi(s.c_str());}string my_to_string(int i){char str[10]; itoa(i,str,10); return str;}//将字符串s处理为vvoid funs_v(string s,vector<string> &v,int j_start,int j_end){v.clear(); string s1="",s2=""; char str[5]; //遍历s for(int i=0;i<s.size();i ){//任意符 if(s[i]=='*'){for(int j=j_start;j<=j_end;j ){sprintf(str,"d",j); if(find(v.begin(),v.end(),str)==v.end()) v.push_back(str); } break; } //,号 if(s[i]==','){int j=my_stoi(s1);sprintf(str,"d",j); if(find(v.begin(),v.end(),str)==v.end()) v.push_back(str); s1="";continue; } //-号 if(s[i]=='-'){//s1-s2 for(i ;i<s.size();i ){if(s[i]==',')break; s2 =s[i]; } int sj=my_stoi(s2); for(int j=my_stoi(s1);j<=sj;j ){sprintf(str,"d",j); if(find(v.begin(),v.end(),str)==v.end()) v.push_back(str); } //s1,s2清零 s1="";s2="";continue; } //else:数字 s1 =s[i]; } if(s1!="") {int j=my_stoi(s1); sprintf(str,"d",j); if(find(v.begin(),v.end(),str)==v.end()) v.push_back(str); }}//将月份和周中的英文缩写处理为数字string funchar_num(string s){string ans="",s1=""; for(int i=0;i<s.size();i ){//小写字母 if(s[i]>='a' && s[i]<='z'){s1 =s[i];continue; } //大写字母转为小写 if(s[i]>='A' && s[i]<='Z'){s1 =(s[i]-'A' 'a');continue; } if(s1!=""){ans =mpchar_num[s1];s1="";} ans =s[i]; } if(s1!=""){ans =mpchar_num[s1];s1="";} return ans;}//获取某年某月的天数int month_day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};int get_day(int year,int month){//cout<<year<<" "<<month<<endl; if(month!=2) return month_day[month]; //若是闰年 if((year%4==0 && year0!=0) || year@0==0) return month_day[month] 1; return month_day[month];}//检查日期是否满足要求bool check(string s){//不在起止时间内 if(s<g_s || s>=g_t) return false; //在起止时间内，判断日期合法性（月份，日） //201711170032 //获取年、月、日 int c_year=0,c_month=0,c_day=0; c_year=my_stoi(s.substr(0,4)); c_month=my_stoi(s.substr(4,2)); c_day=my_stoi(s.substr(6,2)); if(c_day<=get_day(c_year,c_month)) return true; return false;}//添加指令void solve(){vector<string> vminute,vhour,vday,vmonth,vweek; //处理分钟 funs_v(sminute,vminute,0,59); //处理小时 funs_v(shour,vhour,0,23); //处理日 funs_v(sday,vday,1,31); //处理月 smonth=funchar_num(smonth); funs_v(smonth,vmonth,1,12); //处理周 sweek=funchar_num(sweek); funs_v(sweek,vweek,0,6); //cout<<sweek<<endl; //从年到月、日、时、分构造完整时间 for(int year=start.year;year<=endt.year;year ){for(int month=0;month<vmonth.size();month ){for(int day=0;day<vday.size();day ){for(int hour=0;hour<vhour.size();hour ){for(int minute=0;minute<vminute.size();minute ){string time=""; time =my_to_string(year);time =vmonth[month];time =vday[day];time =vhour[hour];time =vminute[minute]; //判断time是否符合要求 && 是否满足该周几 //cout<<time.substr(0,8)<<" "<<mp_week[time.substr(0,8)]<<endl; if(find(vweek.begin(), vweek.end(), mp_week[time.substr(0,8)]) != vweek.end() ){if(check(time)){mp[time].push_back(instructment); //cout<<instructment<<endl; } } } } } } }}//mpchar_num,mp_week的初始化void initial(){//初始化mpchar_num string s_month[]={"jan", "feb","mar","apr","may","jun","jul","aug","sep","oct","nov","dec"}; string s_week[]={"sun", "mon","tue","wed","thu","fri","sat"}; for(int i=0;i<12;i ) mpchar_num[s_month[i]]=my_to_string(i 1); for(int i=0;i<7;i ) mpchar_num[s_week[i]]=my_to_string(i); //初始化mp_week int week=4;//1970年1月1日：周四 string time=""; char str[5]; for(int year=1970;year<=2100;year ){for(int month=1;month<=12;month ){int all_day=get_day(year,month); for(int day=1;day<=all_day;day ){//构造time time=my_to_string(year); sprintf(str,"d",month); time =str; sprintf(str,"d",day); time =str; //计算周次 week%=7; sprintf(str,"d",week); mp_week[time]=str; week ; //cout<<time<<" "<<str<<endl; } } }}int main() {int n; initial(); cin>>n>>g_s>>g_t; //字符串转数字 start.year=my_stoi(g_s.substr(0,4));start.month=my_stoi(g_s.substr(4,2)); start.day=my_stoi(g_s.substr(6,2));start.hour=my_stoi(g_s.substr(8,2)); start.minutes=my_stoi(g_s.substr(10,2)); endt.year=my_stoi(g_t.substr(0,4));endt.month=my_stoi(g_t.substr(4,2)); endt.day=my_stoi(g_t.substr(6,2));endt.hour=my_stoi(g_t.substr(8,2)); endt.minutes=my_stoi(g_t.substr(10,2)); while(n--){cin>>sminute>>shour>>sday>>smonth>>sweek>>instructment; solve(); } //遍历map,输出结果 for(iter=mp.begin();iter!=mp.end();iter ){for(int i=0;i<iter->second.size();i ){cout<<iter->first<<" "<<iter->second[i]<<'\n'; } } return 0;}/*3 201711170032 2017112223520 7 * * 1,3-5 get_up30 23 * * Sat,Sun go_to_bed15 12,18 * * * have_dinner201711170700 get_up201711171215 have_dinner201711171815 have_dinner201711181215 have_dinner201711181815 have_dinner201711182330 go_to_bed201711191215 have_dinner201711191815 have_dinner201711192330 go_to_bed201711200700 get_up201711201215 have_dinner201711201815 have_dinner201711211215 have_dinner201711211815 have_dinner201711220700 get_up201711221215 have_dinner201711221815 have_dinner */
赞 (0)