Informatics Olympiad all in one 1974: [16noip popularization group] palindrome date | Luogu p2010 [noip2016 popularization group] palindrome date

【 Topic link 】

ybt 1974：【16NOIP Popularization group 】 Palindrome date
Luogu P2010 [NOIP2016 Popularization group ] Palindrome date

【 Topic test site 】

1. simulation

【 Their thinking 】

solution 1： enumeration Date structure

Set the structure representing the date , Attributes include year, month, day , There are methods ： Enter the next day , And judge whether the current date is palindrome .
The input date is a string , The constructor will precede the string 4 Characters become numeric , Is year . The middle two characters become months , The last two characters become days . Year, month and day are integer variables , You can use substr() Function substring , as well as stoi() Function to convert a string to an integer .
Set the function that changes the current date to the next day next(), Let Rijia first 1, If the day exceeds the number of days in this month , Then month plus 1, Daily change into 1. If the month exceeds 12, Then add the year 1, The month becomes 1. If the month changes , Update the number of days in this month md.
Judge whether the current date is palindrome , You can split the number of year, month and day , Each bit is saved in a length of 8 In the integer array of . Traversing half of an array (<n/2), Judge whether the corresponding positions before and after this array are the same . If the same , Then this date is palindrome .
Main function , Give Way d Is the start date , Each cycle determines whether the current date is palindrome , If yes, count , Then let the date become the next day . If the current date is the end date , So get out of the loop .
Last output count .
The complexity is the difference between two date values , In extreme cases , from 0 year 1 month 1 The day is coming 9999 year 12 month 12 Japan , There's a total appointment $366\ast 10000=3\ast 10^6$ God , It is acceptable .

solution 2： Deep search Construct palindrome string

Save numbers with an integer array , Search deeply and construct all possible palindrome numbers . After constructing palindrome numbers , Judge whether the date is legal , And whether the date is between the start and end dates .
In the worst case , Just search 4 Digit number , Each number has 10 Kind of , The maximum number of searches is $10^4$ Time , Better than the solution 1.

【 Solution code 】

solution 1： enumeration Date structure

#include<bits/stdc++.h>
using namespace std;
struct Date// Date structure 
{
    
    int y, m, d, md;//y: year , m: month , d: Japan , md: Days of current month 
    Date(string s)// Initialize date with string 
    {
    
        y = stoi(s.substr(0, 4));
        m = stoi(s.substr(4, 2));
        d = stoi(s.substr(6));
        md = getMonthDay();
    }
    bool isLeap()// Determine if the year is a leap year 
    {
    
        return y % 400 == 0 || y % 100 != 0 && y % 4 == 0;
    }
    int getMonthDay()// Get the number of days in the current month  
    {
    
        if(m == 2)
            return isLeap() ? 29 : 28;
        else if(m == 4 || m == 6 || m == 9 || m == 11)
            return 30;
        else
            return 31;
    }
    void next()// The date changes to the next day  
    {
    
        d++;
        if(d > md)// If the day exceeds the total number of days in the month 
        {
    
            d = 1;// Set day as 1
            m++;// Month plus 1
            if(m > 12)// If the month exceeds 12
            {
    
                y++;
                m = 1;
            }
            md = getMonthDay();
        }
    }
    bool isHuiwen()//s: Convert the current date to a string 
    {
    
        int a[10] = {
    y/1000, y/100%10, y/10%10, y%10, m/10, m%10, d/10, d%10};
        for(int i = 0; i < 4; ++i)
            if(a[i] != a[7-i])
                return false;
        return true;
    }
    bool isSame(Date b)
    {
    
        return y == b.y && m == b.m && d == b.d;
    }
};
int main()
{
    
    string s1, s2;
    int ct = 0;//ct: Count 
    cin >> s1 >> s2;//s1: Start date string  s2: End date string  
    Date d(s1), d2(s2);
    while(true)
    {
    
        if(d.isHuiwen())
            ct++;
        if(d.isSame(d2))
            break;
        d.next();
    }
    cout << ct << endl;
    return 0;
}

solution 2： Deep search Construct palindrome string

#include<bits/stdc++.h>
using namespace std;
#define N 8
int d[N], d1[N], d2[N], ct;
bool isLater(int a[], int b[])// date b Is it related to the date a identical , Or on the date b After the time  
{
    
    int y_a = a[0]*1000+a[1]*100+a[2]*10+a[3], m_a = a[4]*10+a[5], d_a = a[6]*10+a[7]; 
    int y_b = b[0]*1000+b[1]*100+b[2]*10+b[3], m_b = b[4]*10+b[5], d_b = b[6]*10+b[7];
    if(y_b < y_a)
        return false;
    else if(y_b > y_a)
        return true;
    else
    {
    
        if(m_b < m_a)
            return false;
        else if(m_b > m_a)
            return true;
        else
            return d_b >= d_a;
    }
}
bool isValidDate(int a[])// date a Is it legal  
{
    
    int md[13] = {
    0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int year = a[0]*1000+a[1]*100+a[2]*10+a[3], month = a[4]*10+a[5], day = a[6]*10+a[7]; 
    if(month > 12 || month < 1)
        return false;
    if(year % 400 == 0 || year % 100 != 0 && year % 4 == 0)// According to whether it is a leap year 2 Month days  
        md[2] = 29;
    else
        md[2] = 28;
    if(day > md[month] || day < 1)// If the day exceeds the number of days in the month , It is illegal.  
        return false;
    return true;
} 
void dfs(int k)// take d[k] And d[7-k] assignment  
{
    
    if(k == 2)
    {
    //d[0],d[1] And d[6],d[7] All assignments are completed , have a look d[6]d[7] Is it a legal date  
        int day = d[6]*10+d[7];
        if(day > 31 || day < 1)// The maximum date is 31 
            return;
    }
    if(k == 4)// If the assignment of all positions is completed  
    {
       
        if(isValidDate(d) && isLater(d1, d) && isLater(d, d2))//d It's a legal date , And in d1~d2 Between  
            ct++;// Count 
        return; 
    }
    for(int i = 0; i <= 9; ++i)
    {
    
        d[k] = d[7-k] = i;// The corresponding positions before and after are i 
        dfs(k+1);// Look at the next pair of positions  
    }
}
void toNum(int a[], string s)
{
    
    for(int i = 0; i < s.length(); ++i)
        a[i] = s[i] - '0';
}
int main()
{
    
    string s1, s2;
    cin >> s1 >> s2;//s1: Start date string  s2: End date string  
    toNum(d1, s1);
    toNum(d2, s2);
    dfs(0); 
    cout << ct << endl;
    return 0;
}