CSP 201712-3 Crontab 0→85→95→100
3 Crontab
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:00
map<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处理为v
void 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,"%02d",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,"%02d",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,"%02d",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,"%02d",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 && year%100!=0) || year%400==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,"%02d",month);
time+=str;
sprintf(str,"%02d",day);
time+=str;
//计算周次
week%=7;
sprintf(str,"%02d",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 201711222352
0 7 * * 1,3-5 get_up
30 23 * * Sat,Sun go_to_bed
15 12,18 * * * have_dinner
201711170700 get_up
201711171215 have_dinner
201711171815 have_dinner
201711181215 have_dinner
201711181815 have_dinner
201711182330 go_to_bed
201711191215 have_dinner
201711191815 have_dinner
201711192330 go_to_bed
201711200700 get_up
201711201215 have_dinner
201711201815 have_dinner
201711211215 have_dinner
201711211815 have_dinner
201711220700 get_up
201711221215 have_dinner
201711221815 have_dinner
*/