分类讨论

$O(1)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

struct Date{
    int y, m, d;
    bool operator< (const Date &t)const
    {
        if(y != t.y) return y < t.y;
        if(m != t.m) return m < t.m;
        return d < t.d;
    }
    bool operator== (const Date &t)const
    {
        return y == t.y && m == t.m && d == t.d;
    }
};

vector<Date> date;
int a[3];

const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int y, int m, int d){
    if(y < 1960 || y >= 2060 || m < 1 || m > 12) return false;
    int maxd = days[m];
    if(m == 2 && (y % 400 == 0 || (y % 4 == 0 && y % 100))) maxd++;
    if(d < 1 || d > maxd) return false;
    return true;
}


int main(){
    string s;
    cin >> s;
    a[0] = (s[0] - '0') * 10 + s[1] - '0';
    a[1] = (s[3] - '0') * 10 + s[4] - '0';
    a[2] = (s[6] - '0') * 10 + s[7] - '0';
    if(check(1900 + a[0], a[1], a[2])) date.push_back({1900 + a[0], a[1], a[2]});
    if(check(2000 + a[0], a[1], a[2])) date.push_back({2000 + a[0], a[1], a[2]});
    if(check(1900 + a[2], a[0], a[1])) date.push_back({1900 + a[2], a[0], a[1]});
    if(check(2000 + a[2], a[0], a[1])) date.push_back({2000 + a[2], a[0], a[1]});
    if(check(1900 + a[2], a[1], a[0])) date.push_back({1900 + a[2], a[1], a[0]});
    if(check(2000 + a[2], a[1], a[0])) date.push_back({2000 + a[2], a[1], a[0]});
    sort(date.begin(), date.end());
    date.erase(unique(date.begin(), date.end()), date.end());
    for(int i = 0; i < date.size(); i++) printf("%d-%02d-%02d\n", date[i].y, date[i].m, date[i].d);
    return 0;
}