以下摘要由GPT-4o生成:
小明在处理历史文献中的日期时遇到格式不统一的问题，这些日期在1960年到2059年之间，并且省略了年份的前两位，导致每个日期可能对应多个实际日期。文章要求根据给定的日期格式”AA/BB/CC”输出所有可能的真实日期，并按照时间排序。此外，牛牛对回文日期感兴趣，希望在指定日期范围内计算出多少个日期的88位数字表示是回文的。同时，提到了如何找出某单位票据ID中出现的断号和重号，及如何统计满足条件的三元组数量，最后涉及连号区间的计算方法。这些问题涵盖了日期处理、数据结构与算法的多种应用。

日期问题

日期八位字符的处理与校验；

题目

小明正在整理一批历史文献。这些历史文献中出现了很多日期。

小明知道这些日期都在1960年1月1日至2059年12月31日。

令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。

更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入格式

一个日期，格式是”AA/BB/CC”。

即每个’/’隔开的部分由两个 0-9 之间的数字（不一定相同）组成。

输出格式

输出若干个不相同的日期，每个日期一行，格式是”yyyy-MM-dd”。

多个日期按从早到晚排列。

数据范围

0≤A,B,C≤90≤A,B,C≤9

输入样例：

1
02/03/04

输出样例：

1
2
3
2002-03-04
2004-02-03
2004-03-02
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
#include<cstdio>//格式化输入输出,sacnf,printf;
#include<cstring>
#include<algorithm>
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check_valid(int year, int month, int day){
    
    if(month == 0 || month > 12) return false;
    
    if(day == 0 ) return false;
    
    if(month != 2){
        
        if(day > days[month]) return false;
        
    }else{
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;//判断为闰年;
        if(day > 28 + leap) return false;
    }
    
    return true;
}

int main (){
    int a, b, c;
    scanf("%d/%d/%d", &a, &b, &c);
    
    
    
    for(int date = 19600101; date < 20591231; date++){
        int year = date / 10000, month = date % 10000 / 100, day = date % 100;
        
        if(check_valid(year, month, day)){
            if(year % 100 == a && month == b && day == c || //年/月/日
                month == a && day == b && year % 100 == c || //月/日/年
                day == a && month == b && year % 100 == c){    //日/月/年
                    printf("%d-%02d-%02d\n",year, month, day);
                } 
        }
    }
    return 0;
}

题目-回文日期

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 8 位数字表示一个日期，其中，前 4 位代表年份，接下来 2 位代表月份，最后 2 位代表日期。

显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的 8位数字是回文的。

现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。

一个 8 位数字是回文的，当且仅当对于所有的 ii(1≤i≤8) 从左向右数的第 i 个数字和第 9−i个数字（即从右向左数的第 i 个数字）是相同的。

例如：

  • 对于 2016年 11 月 19 日，用 88 位数字 20161119 表示，它不是回文的。
  • 对于 2010年 11 月 22 日，用 88 位数字 20100102 表示，它是回文的。
  • 对于 2010 年 10 月 22 日，用 88 位数字 20101002 表示，它不是回文的。

输入格式

输入包括两行，每行包括一个 8 位数字。

第一行表示牛牛指定的起始日期 date1，第二行表示牛牛指定的终止日期 date2。保证 date1 和 date2 都是真实存在的日期，且年份部分一定为 4 位数字，且首位数字不为 0。

保证 date1 一定不晚于 date2。

输出格式

输出共一行，包含一个整数，表示在 date1date1 和 date2date2 之间，有多少个日期是回文的。

输入样例：

1
2
20110101
20111231

输出样例：

1
1
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
#include<iostream>
#include<algorithm>
using namespace std;
//枚举year，先求对应位，再求出对应的回文数，如果满足日期条件，那么可以判断日期为回文数;
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check_valid(int date){
    int year = date / 10000;
    int month = date % 10000 / 100;//先得到四位，再求前两位;
    int day = date % 100; //得到后两位;
    if(month >= 13 || !month || !day) return false;
    if( month != 2 && day > months[month]) return false;
    
    if(month == 2 ){
        bool leap =( year % 4 == 0 && year % 100) || (year % 400 == 0);//是闰年;
        if( day > 28 + leap) return false;//是闰年就加leap，否则不加;
    }
    return true;
    
}


int main (){
    int date1, date2;
    cin >> date1 >> date2;
    int res = 0;
    for(int i = 0; i <= 10000; i++){
        int date = i,x = i;
        while(x){
            date = date * 10 + x %10;
            x /= 10;
        }
        if(check_valid(date) && date1 <= date && date <= date2) res ++;
    }
    cout << res ;
    return 0;
}

特别地:回文数求法与将数字转换为字符数组

1
2
3
4
5
int res;
while(num){
    res = res * 10 + num % 10;
    num /= 10;
}//将数字123转换为回文数321;
1
2
3
4
5
6
int a[100], i = 0;
int num = 123;
while(num){
	a[i] =  num % 10;
    num /= 10;
}

排序模拟

题目

sstream库处理数据读入问题

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的ID号。

全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。

因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。

你的任务是通过编程，找出断号的ID和重号的ID。

假设断号不可能发生在最大和最小号。

输入格式

第一行包含整数 N，表示后面共有 N 行数据。

接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。

输出格式

要求程序输出1行，含两个整数 m,n，用空格分隔。

其中，m表示断号ID，n表示重号ID。

数据范围

1≤N≤100

输入样例：

1
2
3
2
5 6 8 11 9
10 12 9

输出样例：

1
7 9
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
//sstream库处理string
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;


const int N = 10010;
int a[N];
int n;

int main (){
    
    int t;
    cin >> t;
    string line;
    getline(cin, line);//读取第一行换行符;
    
    while(t --){
        
        getline(cin, line);//读取一行，处理每一行;
        stringstream ssin(line);
        while(ssin >> a[n]) n++;
    }//读取数据;
    sort(a, a + n);//排序
    
    int res1, res2;
    for(int i = 1; i < n; i++){
        if(a[i] == a[i - 1]) res2 = a[i];//重复;
        else if(a[i] >= a[i - 1] + 2) res1 = a[i] - 1;//前一个数断号
    }
    cout << res1 << ' ' << res2;
    
    
    
    
    return 0;
}

二分 前缀和 双指针

题目

给定三个整数数组

A=[A1,A2,…AN]
B=[B1,B2,…BN]
C=[C1,C2,…CN]

请你统计有多少个三元组 (i,j,k)(i,j,k) 满足：

  1. 1≤i,j,k≤N
  2. Ai<Bj<Ck

输入格式

第一行包含一个整数 N。

第二行包含 N个整数 A1,A2,…A。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式

一个整数表示答案。

数据范围

1≤N≤105
0≤Ai,Bi,Ci≤10

输入样例：

1
2
3
4
3
1 1 1
2 2 2
3 3 3

输出样例：

1
27
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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N = 100010;
int a[N],b[N],c[N];
int sa[N], sc[N];
int s[N];
int cnt[N];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]), a[i]++;//加一防止越界
    for(int i = 0; i < n; i++) scanf("%d", &b[i]), b[i]++;
    for(int i = 0; i < n; i++) scanf("%d", &c[i]), c[i]++;
    
    for(int i = 0; i < n; i++) cnt[a[i]]++;
    for(int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];
    for(int i = 0; i < n; i++) sa[i] = s[b[i] - 1];//减一为之前多加的；
    
    memset(cnt, 0, sizeof cnt);//重置为0；
    memset(s, 0, sizeof s);
    
    for(int i = 0; i < n; i++) cnt[c[i]]++;
    for(int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];
    for(int i = 0; i < n; i++) sc[i] = s[N - 1] - s[b[i]];//减一为之前多加的；计算大于b[i]个数
    LL res = 0;
    for(int i = 0; i < n; i++) res += (LL)sa[i] * sc[i];
    cout << res ;
    
    return 0;
}

题目-问题转换

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L,R][L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1的“连续”数列，则称这个区间连号区间。

当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数 N，表示排列的规模。

第二行是 N个不同的数字 Pi，表示这 N 个数字的某一排列。

输出格式

输出一个整数，表示不同连号区间的数目。

数据范围

1≤N≤10000,
1≤Pi≤N,

输入样例1：

1
2
4
3 2 4 1

输出样例1：

1
7

样例解释

1
用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10000;
int a[N];
int INF = 100000000;

int main (){
    
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int res = 0;
    for(int i = 0; i < n; i++){
        int Max = -INF, Min = INF;
        for(int j = i; j < n; j++){
            Max = max(Max, a[j]);
            Min = min(Min, a[j]);
            if(Max - Min == j - i) res++; //把上升区间转换为最大值最小值的差，节省time复杂度
            //因为是0 - n的数，不重复；
        }
    }
    cout << res;
    
    
    return 0;
}