题目描述
no
样例
blablabla
这道题我提交了两遍,洛谷又提交了两遍,第一遍超时两个点,80分,第二遍过
两遍思路不同
算法1
(字符串模拟、暴力枚举) $O((b-a)*8)$
第一遍:
从年份a至b全部列出来,把年月日拨出来增加,然后在合起来判断是否回文
时间复杂度分析:blablabla
80分代码:
C++ 代码
//源代码
//
//语言: G++ 用户名: Hicode002 题号: 465
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include <algorithm>
#include<sstream>
#include<fstream>
#include<climits>
#include<cmath>
#include<cfloat>
//#include<windows.h>
using namespace std;
bool hws(string a){
int lena=a.size();
int s=lena-1;
for(int i=0;i<=lena/2;i++){
if(a[i]!=a[s])return 0;
s--;
}
return 1;
}//check
bool pr(long long a){
if(a%400==0||(a%4==0&&a%100!=0)){
return 1;//r
}
return 0;//p
}
bool dxy(long long a){
switch(a){
case 1:case 5:case 3: case 7:case 8:case 10: case 12:return 1;//31t
default:return 0;
}
}
//20111231 31:%100 2011:/10000 12:/100 %100
/*1 3 5 7 8 10 12:31
4 6 9 7 :30
2 :p:28 */int main()
{
long long a,b;
cin>>a>>b;
long long aday,amonth,ayear,bday,bmonth=0,byear=0;
string as="",asmonth,asyear,asday;
aday=a%100;
amonth=(a/100)%100;
ayear=a/10000;
// cout<<"year "<<ayear<<"month "<<amonth<<"day "<<aday<<endl;
// Sleep(1000);
stringstream ss;
while(1){
if(amonth==2&&pr(ayear)&&aday>29){
aday=1;
amonth++;
}else if(amonth==2&&pr(ayear)==0&&aday>28){
aday=1;
amonth++;
}else if(dxy(amonth)&&aday>31){
aday=1;
amonth++;
}else if(dxy(amonth)==0&&aday>30){
aday=1;
amonth++;
}
if(amonth>12){
amonth=1;
ayear++;
}
// cout<<"年:"<<ayear<<"月:"<<amonth<<"日:"<<aday<<endl;
// Sleep(100);
ss<<ayear;
ss>>asyear;
as+=asyear;
ss.clear() ;
ss<<amonth;
ss>>asmonth;
if(amonth>=1&&amonth<=9){
as+='0';
as+=asmonth;
}else{
as+=asmonth;
}
ss.clear();
ss<<aday;
ss>>asday;
if(aday>=1&&aday<=9){
as+='0';
as+=asday;
}else{
as+=asday;
}
ss.clear();
asday="",asyear="",asmonth="";
ss<<as;
ss>>byear;
// cout<<as<<endl;
if(hws(as)){
bmonth++;
}
if(byear==b){
ss.clear();
asday="",asyear="",asmonth="" ,byear=0;
break;
}
aday++;
ss.clear();
byear=0;
as="";
}
cout <<bmonth<<endl;
return 0;
}
算法2
(暴力枚举、模拟) $O()$
由于超时,我只能另选方法,我把年份取出递增到b
时间复杂度分析:blablabla
100分代码:
C++ 代码
//源代码
//
//语言: G++ 用户名: Hicode002 题号: 465
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include <algorithm>
#include<sstream>
#include<fstream>
#include<climits>
#include<cmath>
#include<cfloat>
//#include<windows.h>
using namespace std;
bool hws(string a){
int lena=a.size();
int s=lena-1;
for(int i=0;i<=lena/2;i++){
if(a[i]!=a[s])return 0;
s--;
}
return 1;
}//check
bool pr(long long a){
if(a%400==0||(a%4==0&&a%100!=0)){
return 1;//r
}
return 0;//p
}
bool dxy(long long a){
switch(a){
case 1:case 5:case 3: case 7:case 8:case 10: case 12:return 1;//31t
default:return 0;
}
}
long long dr(long long a){
long long num=0,yu=0;
while(a>0){
yu=a%10;
num=num*10+yu;
a/=10;
}
// cout<<"num::"<<num<<endl;
return num;
}
//20111231 31:%100 2011:/10000 12:/100 %100
/*1 3 5 7 8 10 12:31
4 6 9 7 :30
2 :p:28 */int main()
{
long long a,b;
cin>>a>>b;
long long aday,amonth,ayear,bday,bmonth=0,byear=0,t=0;
string as="",asmonth,asyear,asday;
ayear=a/10000;
// cout<<"year "<<ayear<<"month "<<amonth<<"day "<<aday<<endl;
// Sleep(1000);
while(1){
// cout<<ayear<<endl;
bday=dr(ayear);
// cout<<bday<<endl;
bmonth=ayear*10000+bday;
// cout<<bmonth<<endl;
if(bmonth>b){
cout<<t<<endl;
return 0;
}
aday=bmonth%100;//12344321 156651
amonth=(bmonth/100)%100;
if(amonth>=1&&amonth<=12&&aday>=1&&aday<=31&&bmonth>=a){
if(pr(ayear)&&amonth==2&&aday<=29){
t++;
}else if(pr(ayear)==0&&amonth==2&&aday<=28){
t++;
}else if(dxy(amonth)&&aday<=31){
t++;
}else if(dxy(amonth)==0&&aday<=30){
t++;
}
}
ayear++;
}
return 0;
}