每日一题之日期统计

问题描述

小蓝现在有一个长度为 100100 的数组，数组中的每个元素的值都在 00 到 99 的范围之内。数组中的元素从左至右如下所示：

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

现在他想要从这个数组中寻找一些满足以下条件的子序列：

1. 子序列的长度为 8；
2. 这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。

请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023年的日期。对于相同的日期你只需要统计一次即可。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;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,6,1,4,0,1,0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3};// 预处理：记录每个数字出现的位置vector<vector<int>> digit_positions(10);for (int i = 0; i < arr.size(); i++) {digit_positions[arr[i]].push_back(i);}set<string> valid_dates; // 用于去重存储有效日期// 查找所有可能的2023年日期for (int m1 : {0, 1}) { // 月份第一位只能是0或1for (int m2 = 0; m2 <= 9; m2++) { // 月份第二位int month = m1 * 10 + m2;if (month < 1 || month > 12) continue; // 跳过无效月份// 确定每个月的最大天数int max_day;if (month == 2) {max_day = 28; // 2023年不是闰年} else if (month == 4 || month == 6 || month == 9 || month == 11) {max_day = 30;} else {max_day = 31;}for (int d1 = 0; d1 <= 3; d1++) { // 日期第一位只能是0-3for (int d2 = 0; d2 <= 9; d2++) { // 日期第二位int day = d1 * 10 + d2;if (day < 1 || day > max_day) continue; // 跳过无效日期// 检查数字序列2-0-2-3-m1-m2-d1-d2是否存在于数组中vector<int> pattern = {2, 0, 2, 3, m1, m2, d1, d2};int prev_pos = -1;bool valid = true;for (int digit : pattern) {auto it = upper_bound(digit_positions[digit].begin(), digit_positions[digit].end(), prev_pos);if (it == digit_positions[digit].end()) {valid = false;break;}prev_pos = *it;}if (valid) {// 格式化为yyyymmddchar date_str[9];sprintf(date_str, "2023%02d%02d", month, day);valid_dates.insert(date_str);}}}}}cout << valid_dates.size() << endl;return 0;
}

还有种简单的思路（一位大佬写的）

#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[])
{
/*    int num[110]{};for (int i = 0; i < 100; ++i){scanf("%d", &num[i]);}int days[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };int ans = 0;for (int i = 1; i <= 12; ++i){for (int j = 1; j <= days[i]; ++j){char str[10] = { 2,0,2,3 };if (i < 10){str[4] = 0;str[5] = i;}else{str[4] = i / 10;str[5] = i % 10;}if (j < 10){str[6] = 0;str[7] = j;}else{str[6] = j / 10;str[7] = j % 10;}int k = 0;for (int v = 0; v < 100; ++v){if (num[v] == str[k]){k++;}}if (k >= 8){ans++;}}}printf("%d", ans);*/  printf("235");return 0;
}