【NOIP2016】【Luogu2010】回文日期（枚举，可以计算出部分值）

problem

• 指定两个日期（8位数字描述）
• 问这之间有多少日期表示是回文串（包含这两个日期本身）

solution1

• 枚举所有日期
• 回文串判断

//O((t-s)*360)
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

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

bool check(string x){
    for(int i = 0; i < 4; i++)
        if(x[i] != x[7-i])return false;
    return true;
}
int getnum(string x, int l, int r){
    int ans = 0;
    for(int i = l; i <= r; i++)
        ans = ans*10+x[i]-'0';
    return ans;
}
string getstring(int i, int j, int k){
    string ans = "";
    ans += i/1000%10+'0';
    ans += i/100%10+'0';
    ans += i/10%10+'0';
    ans += i%10+'0';
    if(j < 10)ans +="0", ans += j+'0';
    else ans += j/10%10+'0', ans += j%10+'0';
    if(k < 10)ans +="0", ans += k+'0';
    else ans += k/10%10+'0', ans += k%10+'0';
    return ans;
}
bool is_run(int x){
    return (x%4==0&&x%100!=0)||(x%400==0);
}

int main(){
    string s, t;
    cin>>s>>t;
    int ans = 0;
    int s1 = getnum(s,0,3), t1 = getnum(t,0,3);
    int s2 = getnum(s,4,5), t2 = getnum(t,4,5);
    int s3 = getnum(s,6,7), t3 = getnum(t,6,7);
    if(s1 == t1){
        if(is_run(s1))days[2]++;
        if(s2 == t2){
            for(int k = s3; k <= t3; k++)
                if(check(getstring(s1,s2,k)))ans++;
        }else{
            for(int k = s3; k <= days[s2]; k++)
                if(check(getstring(s1,s2,k)))ans++;
            for(int j = s2+1; j < t2; j++)
                for(int k = 1; k <= days[j]; k++)
                    if(check(getstring(s1,j,k)))ans++;
            for(int k = 1; k <= t3; k++)
                if(check(getstring(s1,t2,k)))ans++;
        }
        if(is_run(s1))days[2]--;
    }else{
        if(is_run(s1))days[2]++;
        for(int k = s3; k <= days[s2]; k++)
            if(check(getstring(s1,s2,k)))ans++;
        for(int j = s2+1; j <= 12; j++)
            for(int k = 1; k <= days[j]; k++)
                if(check(getstring(s1,j,k)))ans++;
        if(is_run(s1))days[2]--;
        for(int i = s1+1; i < t1; i++){
            if(is_run(i))days[2]++;
            for(int j = 1; j <= 12; j++){
                for(int k = 1; k <= days[j]; k++){
                    if(check(getstring(i,j,k)))ans++;
                }
            }
            if(is_run(i))days[2]--;
        }
        if(is_run(t1))days[2]++;
        for(int j = 1; j < t2; j++)
            for(int k = 1; k <= days[j]; k++)
                if(check(getstring(t1,j,k)))ans++;
        for(int k = 1; k <= t3; k++)
            if(check(getstring(t1,t2,k)))ans++;
        if(is_run(t1))days[2]--;
    }
    cout<<ans<<'\n';
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
 

solution2

你真的想像上面一样写？？？
1、枚举所有回文串（即枚举月份和日期，可以反过来就算出年份【因为答案是回文串啊】），在范围内就累加答案。
2、二月不需要判断闰年：二月只能是闰年才会成立，不可能是平年。因为当二月是平年时，有28天，就是0228，整个日期是82200228，但是8220是闰年，，hh。

//O(360)
#include<iostream>
using namespace std;
int days[15] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
int main(){
    int s, t;
    cin>>s>>t;
    int ans = 0;
    for(int j = 1; j <= 12; j++){
        for(int k = 1; k <= days[j]; k++){
            int i = (k%10*1000)+(k/10*100)+(j%10*10)+(j/10);//算出回文情况下的前4位
            int data = i*10000+j*100+k;
            if(data<s || data > t)continue;
            ans++;
        }
    }
    cout<<ans<<'\n';
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

QwQ

吐槽：是一个枚举题。难点(代码复杂度)在于枚举所有的日期，因为要对是否为开始的月份日期，结束的月份日期进行分类讨论，代码就变长了，也更加容易出错（虽然我一遍就对了没调试，但是写了大约50mins，，如果哪里炸了就更惨，复杂度也不优。）。。。

角度？：
1、枚举题目给定的范围，判断是否为答案，累加ans。（模拟）
2、枚举答案的可能情况即所有可行解，判断是否在题目范围内，累加ans。
有什么区别么额，，qaq。
还是有一点的吧？雾。。。
这样吧。。 & #$%^&*(@!%^
3、关键可能是？通过枚举一部分数据来计算出另一部分数据，减少了枚举的量，优化了效率。
4、尝试从不同角度去思考不同的枚举方式，可能代码复杂度会有降低。
大致。

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/81163774