問題描述

首先我們要了解什么是子序列，就是一個序列之中可以忽略元素但是不能改變順序之后獲得的序列就叫做子序列。
如"123"就是"11234"的子序列而不是"11324"的子序列

解法一遞歸

#include <iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<string>
bool vis[202400000];
int pp[100] = {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
};
using namespace std;
int ans = 0;
bool checkd(int date) {if (vis[date])return false;vis[date] = 1;int date1 = date / 100%100;int date2 = date % 100;if (date1 > 12 || date1 < 1)return false;if (date1 == 1 || date1 == 3 || date1 == 5 || date1 == 7 || date1 == 8 || date1 == 10 || date1 == 12) {if (date2 <= 31 && date2 >= 1)return true;}else if (date1 == 2) {if (date2 <= 28&& date2 >= 1)return true;}else {if (date2 <= 30 && date2 >= 1)return true;}return false;
}
void dfs(int pos, int k, int date) {if (k == 8) {if (checkd(date)) {ans++;};return;}if (pos > 99) {return;}if (pp[pos] == 2 && k == 0 || pp[pos] == 0 && k == 1 || pp[pos] == 2 && k == 2 || pp[pos] == 3 && k == 3 ||pp[pos] <= 1 && k == 4 || pp[pos] <= 9 && k == 5 || pp[pos] <= 3 && k == 6 || pp[pos] <= 9 && k == 7){dfs(pos + 1, k + 1, date * 10 + pp[pos]);}dfs(pos + 1, k, date);
}
int main()
{dfs(0, 0, 0);cout << ans;return 0;
}

首先我們創建函數dfs()，pos代表數組位置，k代表位數，date表示當前的日期，其中date * 10 + pp[pos]是保存當前日期，我們迭代到位數k==8 return但是要檢查date是否合法

因為date有可能出現13，14之類的寫一個checkd函數如果查到合法ans++，bool vis是檢查日期是否重復的函數。 完成這一位搜索之后dfs(pos + 1, k, date);，直到pos>99 return

解法二：暴力破解

解法二直接窮舉2023所有的日期，看序列中有沒有，這樣就不要判斷重復，也不用判斷是否合法，直接從第一個位置到最后一個位置，輸出ans就可以，代碼也會少很多

#include <bits/stdc++.h>
#include<string>
#include<vector> 
using namespace std;int main()
{int day[] = { 1,31,28,31,30,31,30,31,31,30,31,30,31 };int ans = 0;int arr[100] = {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};for (int i = 1; i <= 12; i++) {for (int j = 1; j <= day[i]; j++) {int date[] = { 1,2,0,2,3,i / 10,i % 10,j / 10,j % 10 };int	id = 1;for (int c = 0; c < 100; c++){if (arr[c] == date[id]) {id++;}if (id > 8) {ans++;break;}}}}cout << ans;return 0;
}