e525 - 106 彰雲嘉區複賽 - Q5 回文日期問題
題目描述
題目要求給定一個西元年份，找出該年份內所有可能形成回文日期的日期，並輸出回文日期的數量以及所有回文日期（包含重複的日期）。日期表示方式允許前導零，例如 20170102 和 2017102 都是有效的日期表示。
解題思路
程式碼透過迴圈遍歷所有可能的月份和日期，並將其與給定的年份組合形成一個日期字串。然後，程式碼檢查該字串是否為回文。如果字串是回文，則將其添加到一個儲存回文日期的陣列中。最後，程式碼對陣列進行排序，並輸出回文日期的數量和所有回文日期。程式碼還考慮了閏年的情況，以確保日期是有效的。
複雜度分析
- 時間複雜度: O(12 * 31 * 4) = O(1488)。因為月份迴圈最多執行 12 次，日期迴圈最多執行 31 次，並且在每次迴圈中執行常數時間的操作。
- 空間複雜度: O(101)。因為
ans陣列最多可以儲存 101 個回文日期。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int t,m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31},it,ss;
string s,ans[101];
bool judge(string s){
for(int i=0,sl=s.length();i<sl;++i){
if(s[i]!=s[sl-i-1])return 0;
}
return 1;
}
bool cmp(string x,string y){
int xx=0,yy=0;
for(int i=0;i<x.length();++i){
xx*=10;
xx+=x[i]-'0';
}
for(int j=0;j<y.length();++j){
yy*=10;
yy+=y[j]-'0';
}
if(xx>yy)return 0;
return 1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> s;
ss=0;
for(int i=0;i<4;++i){
ss*=10;
ss+=s[i];
}
it=0;
if((ss%4==0&&ss%100)||ss%400==0)m[2]=29;
else m[2]=28;
for(int i=1;i<=12;++i){
for(int j=1;j<=m[i];++j){
string tmp=s;
if(i<10&&j<10){
string tmp2=tmp;
tmp2+=(i%10+'0');
tmp2+=(j%10+'0');
if(judge(tmp2)){
//cout << i << " " << j << "\n";
ans[it]=tmp2;
++it;
}
}
if(i<10){
string tmp2=tmp;
tmp2+=(i%10+'0');
tmp2+=(j/10+'0');
tmp2+=(j%10+'0');
if(judge(tmp2)){
//cout << i << " " << j << "\n";
ans[it]=tmp2;
++it;
}
}
if(j<10){
string tmp2=tmp;
tmp2+=(i/10+'0');
tmp2+=(i%10+'0');
tmp2+=(j%10+'0');
if(judge(tmp2)){
//cout << i << " " << j << "\n";
ans[it]=tmp2;
++it;
}
}
tmp+=(i/10+'0');
tmp+=(i%10+'0');
tmp+=(j/10+'0');
tmp+=(j%10+'0');
if(judge(tmp)){
//cout << i << " " << j << "\n";
ans[it]=tmp;
++it;
}
}
}
sort(ans,ans+it,cmp);
cout << it << " ";
for(int i=0;i<it;++i){
cout << ans[i] << " ";
}
cout << "\n";
}
}