题目链接
一些话
流程
<!---->输出共一行,包含一个整数,表示在 date1
和 date2
之间,有多少个日期是回文的。
//求有多少个类问题,用枚举做
//此题的枚举情况,要判断回文串、在区间内和 日期合法
//要判断多个性质,可以直接枚举符合其中一种性质的情况
//回文串和区间内容易枚举,但区间内枚举的时间复杂度太高,要枚举8次方级别的数字,而回文串只要枚举一半,即4次方级别,所以此题选择枚举回文串然后做其它两个判断
套路
1.回文串枚举
//回文串的枚举可以只枚举一半,然后通过
<!--for(int i = 1000;i < 10000;i ++){--> <!-- int date = i,x=i;--> <!-- for(int j = 0;j < 4;j++) date = date * 10 + x % 10,x/=10;--> <!-- if(date >= date1 && date <= date2 && check(date)) ans++;--> <!--}-->
来让其恢复完整
2.//闰年的判断:(year % 4 == 0 && year % 100|| year % 400 == 0),被四百整除这条经常会漏
ac代码
[//]: # (打卡模板,上面预览按钮可以展示预览效果 ^^) ``` // 19:45~05 wa; //20:06~20:16 accepted; 和 date2 之间,有多少个日期是回文的。 //求有多少个类问题,用枚举做 //此题的枚举情况,要判断回文串、在区间内和 日期合法 //要判断多个性质,可以直接枚举符合其中一种性质的情况 //回文串和区间内容易枚举,但区间内枚举的时间复杂度太高,要枚举8次方级别的数字,而回文串只要枚举一半,即4次方级别,所以此题选择枚举回文串然后做其它两个判断 //回文串的枚举可以只枚举一半,然后通过 <!--for(int i = 1000;i < 10000;i ++){--> <!-- int date = i,x=i;--> <!-- for(int j = 0;j < 4;j++) date = date * 10 + x % 10,x/=10;--> <!-- if(date >= date1 && date <= date2 && check(date)) ans++;--> <!--}--> 来让其恢复完整 //闰年的判断:(year % 4 == 0 && year % 100|| year % 400 == 0),被四百整除这条经常会漏 // #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N = 1e5 + 10; int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; bool check(int date){ int year = date / 10000; int month = date % 10000 / 100; int day = date % 100; // cout << year << month << day << endl; if(month != 2 && day > months[month] || !day) return false; if(month > 12 || !month) return false; if(month == 2 && day > 28 + (year % 4 == 0 && year % 100|| year % 400 == 0)) return false; return true; } int main(){ int date1,date2; cin >> date1 >> date2; int ans = 0; for(int i = 1000;i < 10000;i ++){ int date = i,x=i; for(int j = 0;j < 4;j++) date = date * 10 + x % 10,x/=10; if(date >= date1 && date <= date2 && check(date)) ans++; } cout << ans << endl; return 0; } ```