【CCF 201712-3】 Crontab

写在前面

这是一道恶心的大模拟，需要考虑到的细节非常多，博主在踩了很多坑之后终于得了100分，先放个截图：

遇到的一些坑

坑1：采用暴力法（超时，-25分）

坑2：英文字母不区分大小写（没考虑，-20分）

坑3：s可以取，t不可取（没考虑，-20分）

坑4：注意有些year-month-day是不存在的

坑5：时间相同时，按输入顺序排序输出

解本题的两种思路

①暴力模拟时间流动【逻辑较清晰，但超时】：每次累加一分钟，分别查询符合条件的cron

②枚举所有可能+排序【需要注意的点多一些】：对每条cron，用5层for循环（年、月、日、时、分）找到[s, t]区间内所有符合的日期，加入vecotr<Result>，最后按时间稳定排序即可

两种思路的C++代码（带详细注释）

暴力法（75分）

#include <iostream>
#include <cstring>
#include <sstream>
#include <iomanip>
using namespace std;

string month[13] = {"", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
string week[7] =   {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};

struct Cron
{
    string line, s[5], cmd;		//整行，<><><><><>，command
    bool a[5][60];				//标记是否可行
};

inline int to_int(const string& a)
{
    int res;
    stringstream ss;
    ss << a;
    ss >> res;
    return res;
}

inline string to_str(int a)
{
    string res;
    stringstream ss;
    ss << a;
    ss >> res;
    return res;
}

inline void deal_cron(Cron& t)
{
    //把英文转化为数字
    size_t p;
    for(int i = 1; i < 13; ++i)
    {
        p = t.line.find(month[i]);
        if(p != string::npos) t.line.replace(p, 3, to_str(i));
    }
    for(int i = 0; i < 7; ++i)
    {
        p = t.line.find(week[i]);
        if(p != string::npos) t.line.replace(p, 3, to_str(i));
    }

    //拆解line为5个子串
    stringstream ss;
    ss << t.line;
    for(int i = 0; i < 5; ++i)
        ss >> t.s[i];
    ss >> t.cmd;

    //分别处理五个子串
    string tmp;
    for(int i = 0; i < 5; ++i)
    {

        //把','转化为' '
        for(size_t j = 0; j < t.s[i].size(); ++j)
            if(t.s[i][j] == ',') t.s[i][j] = ' ';
        ss.clear();
        ss << t.s[i];

        //填充数组a
        while(ss >> tmp)
        {
            if(tmp == "*")
            {
                if(i == 0)
                {
                    for(int j = 0; j <= 59; ++j)
                        t.a[i][j] = 1;
                }
                else if(i == 1)
                {
                    for(int j = 0; j <= 23; ++j)
                        t.a[i][j] = 1;
                }
                else if(i == 2)
                {
                    for(int j = 1; j <= 31; ++j)
                        t.a[i][j] = 1;
                }
                else if(i == 3)
                {
                    for(int j = 1; j <= 12; ++j)
                        t.a[i][j] = 1;
                }
                else if(i == 4)
                {
                    for(int j = 0; j <= 6; ++j)
                        t.a[i][j] = 1;
                }
                break;
            }

            p = tmp.find("-");
            if(p != string::npos)
            {
                for(int j = to_int(tmp.substr(0, p)); j <= to_int(tmp.substr(p + 1)); ++j)
                    t.a[i][j] = 1;
            }
            else t.a[i][to_int(tmp)] = 1;
        }
    }
}

long long n, s, t;
long long year, mon, day, hour, minu, wee;		//当前的状态
long long year1, mon1, day1, hour1, minu1;		//终止状态

inline int year_day(int y)
{
    if((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) return 366;
    else return 365;
}

inline int month_day(int year, int month)
{
    if(month == 2)
        return year_day(year) - 337;
    if(month == 4 || month == 6 || month == 9 || month == 11)
        return 30;
    else return 31;
}

inline void deal_time()
{
	//计算起始日期和终止日期
    year = s / 100000000;
    mon = (s % 100000000) / 1000000;
    day = (s % 1000000) / 10000;
    hour = (s % 10000) / 100;
    minu = s % 100;
    year1 = t / 100000000;
    mon1 = (t % 100000000) / 1000000;
    day1 = (t % 1000000) / 10000;
    hour1 = (t % 10000) / 100;
    minu1 = t % 100;
	
	//计算起始星期 
    long long days = 0;
    for(int i = 1970; i < year; ++i)
        days += year_day(i);
    for(int i = 1; i < mon; ++i)
        days += month_day(year, i);
    days += day - 1;
    wee = (4 + days) % 7;
}

inline bool next()			//下一分钟 
{
    ++minu;
    if(minu == 60)
    {
        ++hour;
        minu = 0;
    }
    if(hour == 24)
    {
        ++day;
        wee = (wee + 1) % 7;
        hour = 0;
    }
    if(day == month_day(year, mon) + 1)
    {
        ++mon;
        day = 1;
    }
    if(mon == 13)
    {
        ++year;
        mon = 1;
    }
    if(minu != minu1 || hour != hour1 || mon != mon1 || day != day1 || year != year1) return 1;
    else return 0;
}

inline void print_time()		//打印时间 
{
    cout << year;
    cout << setfill('0') << setw(2) << mon;
    cout << setfill('0') << setw(2) << day;
    cout << setfill('0') << setw(2) << hour;
    cout << setfill('0') << setw(2) << minu;
}

inline bool isMatch(Cron& t)		//cron是否符合要求 
{
    if(t.a[0][minu] && t.a[1][hour] && t.a[2][day] && t.a[3][mon] && t.a[4][wee]) return 1;
    else return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s >> t;
    Cron cron[n];
    cin.get();
    for(int i = 0; i < n; ++i)
    {
        getline(cin, cron[i].line);
        memset(cron[i].a, 0, sizeof(cron[i].a));
        deal_cron(cron[i]);
    }

//	for(int i=0; i<5; ++i)
//	{
//		for(int j=0; j<60; ++j)
//			if(cron[0].a[i][j]) cout<<j<<' ';
//		cout<<endl;
//	}

    deal_time();
    do
    {
        for(int i = 0; i < n; ++i)
        {
            if(isMatch(cron[i]))
            {
                print_time();
                cout << ' ' << cron[i].cmd << '\n';
            }
        }
    }
    while(next());

    return 0;
}

枚举+排序（100分）

#include <bits/stdc++.h>
using namespace std;

string month[13] = {"", "JAN", "FEB", "MAR", "APR", "MAY", "JUN", "JUL", "AUG", "SEP", "OCT", "NOV", "DEC"};
string week[7] =   {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

struct Cron
{
    string line, s[5], cmd;		//整行，<><><><><>，command
    set<long long> a[5];		//标记可行的日期
} cron;

struct Result	//需要输出的内容 
{
    long long res;
    string cmd;
    Result(long long a, string& b): res(a), cmd(b) {}
};

inline int to_int(const string& a)	//评测系统不支持C++11，所以写了这个函数
{
    int res;
    stringstream ss;
    ss << a;
    ss >> res;
    return res;
}

inline string to_str(int a)		//评测系统不支持C++11，所以写了这个函数
{
    string res;
    stringstream ss;
    ss << a;
    ss >> res;
    return res;
}

void deal_cron(Cron& t)
{
    //拆解line为5个子串
    stringstream ss;
    ss << t.line;
    for(int i = 0; i < 5; ++i)
        ss >> t.s[i];
    ss >> t.cmd;

    //将英文全转化为大写
    transform(t.s[3].begin(), t.s[3].end(), t.s[3].begin(), ::toupper);
    transform(t.s[4].begin(), t.s[4].end(), t.s[4].begin(), ::toupper);

    //把英文转化为数字
    size_t p;
    for(int i = 1; i < 13; ++i)
    {
        p = t.s[3].find(month[i]);
        if(p != string::npos) t.s[3].replace(p, 3, to_str(i));
    }
    for(int i = 0; i < 7; ++i)
    {
        p = t.s[4].find(week[i]);
        if(p != string::npos) t.s[4].replace(p, 3, to_str(i));
    }

    //分别处理五个子串
    string tmp;
    for(int i = 0; i < 5; ++i)
    {

        //把','转化为' '
        for(size_t j = 0; j < t.s[i].size(); ++j)
            if(t.s[i][j] == ',') t.s[i][j] = ' ';
        ss.clear();
        ss << t.s[i];

        //填充集合a[i]
        while(ss >> tmp)
        {
            if(tmp == "*")		//如果是*，全部放入set
            {
                if(i == 0)
                {
                    for(int j = 0; j <= 59; ++j)
                        t.a[i].insert(j);
                }
                else if(i == 1)
                {
                    for(int j = 0; j <= 23; ++j)
                        t.a[i].insert(j);
                }
                else if(i == 2)
                {
                    for(int j = 1; j <= 31; ++j)
                        t.a[i].insert(j);
                }
                else if(i == 3)
                {
                    for(int j = 1; j <= 12; ++j)
                        t.a[i].insert(j);
                }
                else if(i == 4)
                {
                    for(int j = 0; j <= 6; ++j)
                        t.a[i].insert(j);
                }
                break;
            }

            p = tmp.find("-");
            if(p != string::npos)		//如果有'-'，就取2个数字的范围
            {
                for(int j = to_int(tmp.substr(0, p)); j <= to_int(tmp.substr(p + 1)); ++j)
                    t.a[i].insert(j);
            }
            else t.a[i].insert(to_int(tmp));	//没有'-'，就直接插入这个数字
        }
    }
}

long long n, s, t, res, year, year1, j;	//year：起始年份  year1：终止年份   j：当前年份

long long year_day(int y)
{
    if((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) return 366;
    else return 365;
}

long long month_day(int year, int month)
{
    if(month == 2)
        return year_day(year) - 337;
    if(month == 4 || month == 6 || month == 9 || month == 11)
        return 30;
    else return 31;
}

vector<Result> result;
set<long long>::iterator p0, p1, p2, p3, p4;

bool isLegal_week(long long year, long long mon, long long day)	//星期数是否合法
{
    long long days = 0, wee;
    for(int i = 1970; i < year; ++i)
        days += year_day(i);
    for(int i = 1; i < mon; ++i)
        days += month_day(year, i);
    days += day - 1;
    wee = (4 + days) % 7;

    if(cron.a[4].find(wee) == cron.a[4].end()) return 0;		//如果此星期数符合取值范围，返回1
    else return 1;
}

bool isLegal()	//是否合法
{
    if(res >= s && res < t && *p1 <= month_day(j, *p0) && isLegal_week(j, *p0, *p1))	//日期范围、天数是否符合月份、星期数是否相符
        return 1;
    return 0;
}

bool cmp(const Result& a, const Result& b)
{
    return a.res < b.res;
}

void print_result()
{
    for(vector<Result>::iterator p = result.begin(); p != result.end(); ++p)
        cout << p->res << " " << p->cmd << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s >> t;
    cin.get();

    year = s / 100000000;
    year1 = t / 100000000;
    for(int i = 0; i < n; ++i)
    {
        getline(cin, cron.line);
        for(j = 0; j < 5; ++j)
            cron.a[j].clear();
        deal_cron(cron);

        for(j = year; j <= year1; ++j)												//年
            for(p0 = cron.a[3].begin(); p0 != cron.a[3].end(); ++p0)				//月
                for(p1 = cron.a[2].begin(); p1 != cron.a[2].end(); ++p1)			//日
                    for(p2 = cron.a[1].begin(); p2 != cron.a[1].end(); ++p2)		//时
                        for(p3 = cron.a[0].begin(); p3 != cron.a[0].end(); ++p3)	//分
                        {
                            res = j * 100000000 + *p0 * 1000000 + *p1 * 10000 + *p2 * 100 + *p3;
                            if(isLegal()) result.push_back(Result(res, cron.cmd));
                        }
    }

    stable_sort(result.begin(), result.end(), cmp);
    print_result();
    return 0;
}

一些总结

1.看清楚题目的所有要求

2.大模拟题有时候也要考虑运行时间

3.遇到大量输入输出时，记得关同步三部曲，同时把endl换成'\n'

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

本题题面

详细题目请前往：http://www.cspro.org/lead/application/ccf/login.jsp