试题 A: 日期统计

解题思路分析

本题要求从给定的长度为 100 的数组中，找出所有长度为 8 的子序列，这些子序列能组成一个合法的 2023 年日期（格式为 yyyymmdd），并统计不同日期的数量。

核心思路

1. 日期合法性判断：年份固定为 2023，因此子序列的前四位必须是 2、0、2、3。月份必须在 01 到 12 之间，天数必须符合对应月份的天数（注意闰年 2023 年不是闰年，2 月为 28 天）。
2. 子序列匹配：题目要求的是子序列，不是连续子串。这意味着我们可以从数组中按顺序挑选 8 个数字，只要它们的相对顺序与数组中的顺序一致即可。
3. 去重统计：相同的日期只统计一次，因此需要使用集合（Set）来存储找到的合法日期。
4. 暴力枚举优化：直接枚举所有长度为 8 的子序列（C(100,8) 数量巨大）不可行。由于年份固定为 2023，我们可以先定位数组中所有可能的 2、0、2、3 的位置，然后在这些位置之后寻找月份和天数。

算法步骤

1. 将给定的 100 个数字存入数组。
2. 找出所有数字 2 的位置（作为年份的第一位）。
3. 对于每个找到的 2，检查其后面是否有 0、2、3 依次出现（作为年份的后三位）。
4. 如果找到了完整的 2023，则继续在后面寻找两位月份（01-12）和两位天数（需根据月份判断是否合法）。
5. 将合法的日期（格式为 8 位数字字符串）加入集合。
6. 最后输出集合的大小。

参考代码实现（Python）

# 给定的数组 arr = [5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3] 月份天数表（2023年不是闰年） month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] def is_valid_date(month, day): """判断月份和天数是否合法""" if month < 1 or month > 12: return False if day < 1 or day > month_days[month - 1]: return False return True def find_dates(): """查找所有合法的2023年日期""" dates = set() n = len(arr) # 遍历所有可能的起始位置（年份的第一位'2'） for i in range(n - 7): # 至少需要8位，所以i最大为n-8 if arr[i] != 2: continue # 寻找年份 2023 year_positions = [i] target = [0, 2, 3] idx = i + 1 for num in target: found = False while idx &lt; n: if arr[idx] == num: year_positions.append(idx) idx += 1 found = True break idx += 1 if not found: break else: # 成功找到完整的2023年份，继续找月份和日期 # year_positions 现在包含4个位置：[i, pos0, pos2, pos3] # 从最后一个年份数字的位置之后开始找月份 start_search = year_positions[-1] + 1 # 月份是两位数字 for m1 in range(start_search, n - 2): # 至少还需要月份第二位和两位日期 for m2 in range(m1 + 1, n - 1): month = arr[m1] * 10 + arr[m2] if month &lt; 1 or month &gt; 12: continue # 找日期 for d1 in range(m2 + 1, n): for d2 in range(d1 + 1, n): day = arr[d1] * 10 + arr[d2] if is_valid_date(month, day): date_str = f"2023{month:02d}{day:02d}" dates.add(date_str) return dates if name == "main": valid_dates = find_dates() print(f"不同的2023年日期数量: {len(valid_dates)}") 如果需要查看具体日期，可以取消下面的注释 for date in sorted(valid_dates): print(date)

参考代码实现（C++）

#include <iostream> #include <vector> #include <set> #include <string> using namespace std; // 月份天数表（2023年不是闰年） const int month_days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool isValidDate(int month, int day) { if (month < 1 || month > 12) return false; if (day < 1 || day > month_days[month - 1]) return false; return true; } int main() { vector<int> arr = {5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3}; set&lt;string&gt; dates; int n = arr.size(); // 遍历所有可能的起始位置（年份的第一位'2'） for (int i = 0; i &lt;= n - 8; i++) { if (arr[i] != 2) continue; // 寻找年份 2023 vector&amp;lt;int&amp;gt; year_pos = {i}; vector&amp;lt;int&amp;gt; target = {0, 2, 3}; int idx = i + 1; bool year_found = true; for (int num : target) { bool found = false; while (idx &amp;lt; n) { if (arr[idx] == num) { year_pos.push_back(idx); idx++; found = true; break; } idx++; } if (!found) { year_found = false; break; } } if (!year_found) continue; // 成功找到完整的2023年份，继续找月份和日期 // year_pos 现在包含4个位置：[i, pos0, pos2, pos3] // 从最后一个年份数字的位置之后开始找月份 int start_search = year_pos.back() + 1; // 月份是两位数字 for (int m1 = start_search; m1 &amp;lt; n - 2; m1++) { for (int m2 = m1 + 1; m2 &amp;lt; n - 1; m2++) { int month = arr[m1] * 10 + arr[m2]; if (month &amp;lt; 1 || month &amp;gt; 12) continue; // 找日期 for (int d1 = m2 + 1; d1 &amp;amp;lt; n; d1++) { for (int d2 = d1 + 1; d2 &amp;amp;lt; n; d2++) { int day = arr[d1] * 10 + arr[d2]; if (isValidDate(month, day)) { char date_str[9]; sprintf(date_str, "2023%02d%02d", month, day); dates.insert(string(date_str)); } } } } } } cout &lt;&lt; "不同的2023年日期数量: " &lt;&lt; dates.size() &lt;&lt; endl; // 如果需要查看具体日期，可以取消下面的注释 // for (const string&amp; date : dates) { // cout &lt;&lt; date &lt;&lt; endl; // } return 0; }

注意事项

• 上述代码采用了暴力搜索的方法，但由于年份固定且数组长度只有 100，实际计算量在可接受范围内。
• 关键点在于理解"子序列"的含义：不需要连续，但必须保持原有顺序。
• 去重使用集合（Set）数据结构，自动过滤重复日期。
• 日期合法性检查包括月份范围（01-12）和对应月份的天数范围。

运行上述代码即可得到本题的答案。注意：由于是结果填空题，只需要提交最终的整数结果即可。