题目描述Microzot\texttt{Microzot}Microzot公司推出了名为Doors MKB\texttt{Doors MKB}Doors MKB的革命性操作系统同时引入了一套全新的日历系统。新历法将一年分为两个时期Gill\texttt{Gill}Gill和Bates\texttt{Bates}Bates每个时期包含五个月份Sun\texttt{Sun}Sun、Water\texttt{Water}Water、Forest\texttt{Forest}Forest、Mountains\texttt{Mountains}Mountains、Money\texttt{Money}Money每月有363636天由666周First\texttt{First}First至Sixth\texttt{Sixth}Sixth组成每周666天。此外每年末尾还有555天平年或666天闰年的“庆典日”Feast\texttt{Feast}Feast111至Feast\texttt{Feast}Feast5/65/65/6不属于任何时期、月份或星期。新历的第一天对应公历199819981998年666月252525日即Doors MKB\texttt{Doors MKB}Doors MKB发布日。闰年规则与格里高利历相同。199819981998年666月252525日之前的日期在新历中需附加bd意为“before Doors\texttt{before Doors}before Doors”后缀。本题要求编写一个转换器将输入的日期可能是旧历或新历进行转换。若输入为旧历格式YYYY-MM-DD则输出对应的新历日期若输入为新历格式如Gill-Sun-First-1-1则输出Enter date in old format。输入以单独一行END结束。输入格式多行输入每行一个日期字符串。日期可能是旧历格式YYYY-MM-DD年范围为160016001600到500050005000或新历格式由Gill、Bates、Feast等关键词组成。输入以行END结束。输出格式对于每个旧历日期输出对应的新历日期字符串格式为Period-Month-Week-Day-Year或若为Feast\texttt{Feast}Feast日Feast N-Year若日期在199819981998年666月252525日之前则在年份后附加bd。对于每个新历日期输出一行Enter date in old format样例输入1998-06-25 Feast 2-12 1998-06-24 3476-06-21 2000-06-29 END输出Gill-Sun-First-1-1 Enter date in old format Feast 5-1bd Feast 3-1478 Gill-Sun-First-6-3题目分析本题的核心是日历系统之间的转换。两种日历都基于格里高利历的闰年规则但新历将一年重新划分为固定长度的周期180180180天 180180180天 5/65/65/6天且以199819981998年666月252525日为纪元起点。转换的关键步骤将旧历日期转换为从公元111年111月111日起的绝对天数可用格里高利历的累积天数公式。计算该日期与199819981998年666月252525日之间的天数差。根据差值在新历中定位先确定年份每365365365或366366366天递增一年再确定该年中的第几天从111开始计数然后根据第几天落入哪个区间确定时期、月份、周和日或判断是否为Feast\texttt{Feast}Feast日。若原日期早于199819981998年666月252525日则在新历日期后附加bd。新历日期识别若输入字符串包含Bates、Gill或Feast则认为属于新历格式直接输出提示信息。解题思路绝对天数计算toDays采用格里高利历的累积天数公式将年份分解为400400400年周期、100100100年周期、444年周期和余下平年加上月、日偏移。该函数返回从公元111年111月111日到给定日期的总天数包含起始日期。新历日期生成toDate输入两个绝对天数基准点dayOfStart199819981998年666月252525日和待转换日期dayOfCurrent。计算差值dayDiff abs(dayOfCurrent - dayOfStart)。若dayOfCurrent dayOfStart则从基准年开始向后推算年份和年内偏移否则向前推算且最终输出需加bd后缀。确定年份后计算该日期在当年是第几天从111开始。根据年内第几天判断若359 359359即第360360360天及以后则为Feast\texttt{Feast}Feast日输出Feast N其中NNN为天数减去359359359平年Feast\texttt{Feast}Feast555天闰年Feast\texttt{Feast}Feast666天。否则前180180180天属于Gill\texttt{Gill}Gill时期后180180180天属于Bates\texttt{Bates}Bates时期。每个时期内按363636天为一个月份666天为一周分别计算出月份名、周名和日数。输入处理逐行读取若行内容为END则终止。若行中包含Bates、Gill或Feast则视为新历格式输出提示。否则按旧历格式解析年、月、日调用toDays和toDate输出。复杂度分析toDays函数执行常数次算术运算时间复杂度O(1)O(1)O(1)。toDate函数通过循环逐年减去天数最多循环年份差值约500050005000年但实际每次查询最多约500050005000次迭代可接受。可优化为周期跳跃但本题数据量小无需优化。整体时间复杂度O(Y)O(Y)O(Y)其中YYY为日期所在年份与基准年份的差常数级。空间复杂度O(1)O(1)O(1)。代码实现// Microzoft Calendar// UVa ID: 631// Verdict: Accepted// Submission Date: 2017-06-03// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintdaysOfYear365;constintdaysOf4YearsdaysOfYear*41;constintdaysOf100YearsdaysOf4Years*25-1;constintdaysOf400YearsdaysOf4Years*100-3;constintdaysBeforeMonth[2][13]{{0,31,59,90,120,151,181,212,243,273,304,334,365},{0,31,60,91,121,152,182,213,244,274,305,335,366}};boolisLeapYear(intyyyy){return((yyyy%40yyyy%100!0)||yyyy%4000);}// 以公元元年1月1日为基准日期将公元元年以后的日期转换为天数。inttoDays(intyyyy,intmm,intdd){intdays0,yearyyyy-1;days(year/400)*daysOf400Years,year%400;days(year/100)*daysOf100Years,year%100;days(year/4)*daysOf4Years,year%4;daysyear*daysOfYear;daysdaysBeforeMonth[isLeapYear(yyyy)][mm-1]dd;returndays;};// 将天数转换为日期。voidtoDate(intdayOfStart,intdayOfCurrent){intyyyy1,dayDiffabs(dayOfCurrent-dayOfStart);if(dayOfCurrentdayOfStart)dayDiff1;while(true){intdayOfYearisLeapYear(yyyy)?366:365;if(dayDiffdayOfYear){yyyy1;dayDiff-dayOfYear;}elsebreak;}if(dayOfCurrentdayOfStart)dayDiff-1;else{intdayOfYearisLeapYear(yyyy)?366:365;dayDiffdayOfYear-dayDiff;}intdayToYearStartdayDiff;string monthNames[]{Sun,Water,Forest,Mountains,Money};string weekNames[]{First,Second,Third,Fourth,Fifth,Sixth};if(dayToYearStart359)coutFeast (dayToYearStart-359);else{if(dayToYearStart180)coutBates;elsecoutGill;dayToYearStart%180;cout-monthNames[dayToYearStart/36];dayToYearStart%36;cout-weekNames[dayToYearStart/6];dayToYearStart%6;cout-(dayToYearStart1);}cout-yyyy;if(dayOfCurrentdayOfStart)coutbd;cout\n;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string date;intdayOfStarttoDays(1998,6,25);while(getline(cin,date),date!END){if(date.find(Bates)!date.npos||date.find(Gill)!date.npos||date.find(Feast)!date.npos){coutEnter date in old format\n;continue;}intyearstoi(date.substr(0,4));intmonthstoi(date.substr(5,2));intdaystoi(date.substr(8,2));intdayOfCurrenttoDays(year,month,day);toDate(dayOfStart,dayOfCurrent);}return0;}总结本题通过将日期转换为绝对天数消除了闰年和月份差异带来的复杂性从而在统一的数值空间内进行日历转换。核心技巧是使用格里高利历的累积天数公式快速计算绝对天数。利用基准点199819981998年666月252525日计算相对偏移再按新历的固定周期时期、月份、周解析。注意处理早于基准点的日期附加bd后缀。输入检测通过关键词识别新历格式避免误转换。该解法清晰且通用适用于任何两种日历系统之间的转换只需定义好基准点和周期划分即可。