备战蓝桥杯（日益更新）（刷题）
文章目录
- 备战蓝桥杯（日益更新）（刷题）
- 前言：
- 一、二分：
- 1. acwing503 借教室：（二分 + 差分）
- 2. acwing1227 分巧克力：（二分 + 数学推导计算）
- 3. acwing5407 管道（二分、区间合并、差分）
- 二、前缀和：
- 1. acwing562 壁画（向上取整 + 前缀和）
- 2. acwing1230 K倍区间（前缀和 + “同余数相减是倍数？”）
- 三、差分：
- 1.acwing4262 空调（差分 + “一加一减求最大”）
- 2. acwing5396 棋盘（二维差分 + “%2 和 &1”）
- 四、双指针：
- 1. acwing3745 牛的学术圈1（h指数）（双指针）
- 2. acwing4405 统计子矩阵
- 五、归并排序：
- 六、多路归并：
- 七、贡献法：
- 1. acwing4261 孤独的照片
- 2.acwing2868 子串分值（贡献法 + 模拟 + 数学推导）
- 八、日期问题：
- 1. acwing3498 日期差值：
- 2. acwing2867 回文日期：
- 九、区间合并：
- 十、递归：
- 十一、DFS：
- 十二、回溯：
- 十三、BFS：
- 十四、Flood Fill：
- 十五、并查集：
- 十六、哈希：
- 十七、单调队列：
- 十八、树状数组：
- 十九、状态压缩dp：
- 二十、线性dp：
- 二十一、背包问题：
- 二十二、区间dp：
- 二十三、树状dp：
- 二十四、快速幂：
- 二十五、最大公约数：
- 二十六、分解质因数：
- 二十七、矩阵乘法：
- 二十八、组合计数：
- 二十九、数学期望：
- 三十、欧拉函数：
- 三十一、最短路：
- 三十二、贪心：
- 三十三、括号序列：
- 总结
前言：
刷题ing😊 刷题ing😊 刷题ing😊
提示：以下是本篇文章正文内容：
一、二分：
1. acwing503 借教室：（二分 + 差分）
/*
题目：我们须要处理n天的借教室的信息，其中第i天学校有ri个教室可以使用。
共有m份订单，每份订单用三个正整数描述，分别为dj，sj，tj，
表示某租借者要从sj天到tj天租借教室（包含sj、tj天）（就是包头包尾），每天租借dj个教室。
如果在分配过程中，遇到一份订单无法完成，则需要停止教室分配，通知当前申请人修改订单。
现在，我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单？
输入：
第一行包含2个正整数n，m，表示天数和订单数量。
第二行包含n个正整数，其中第i个数表示ri。
接下来由m行，每行包含3个正整数，表示dj，sj，tj。
每行相邻的两个数之间均使用一个空格隔开。
天数与订单均从1开始编号。
输出：
如果所有的订单满足，则输出只有1行，包含一个整数0.
否则，输出两行，第一行输出一个-1，第二行输出需要修改订单的申请人编号。
数据范围：
1 < n,m < 10^6
0 < ri, dj < 10^9
1 < sj, tj < n
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
int n, m;
int r[N], d[N], s[N], t[N];
LL b[N];
// 判断订单是否 不可以完成，如果不可以完成，返回true，可以完成，返回false。
bool check(int mid)
{
for(int i = 1; i <= n; i ++) b[i] = r[i] - r[i - 1];// 差分初始化
for(int i = 1; i <= mid; i ++)// 一个区间里面的数都 减去 一个d[i]
{
b[s[i]] -= d[i];
b[t[i] + 1] += d[i];
}
// 求前缀和
for(int i = 1; i <= n; i ++)
{
b[i] += b[i - 1];
if(b[i] < 0) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d", &r[i]);
for(int i = 1; i <= m; i ++) scanf("%d%d%d", &d[i], &s[i], &t[i]);
// 如果全部订单可以完成，直接打印0.
if(!check(m))
{
puts("0");
return 0;
}
// 否则，二分寻找那个 需要修改订单的申请人编号
int l = 1, r = m;
while(l < r)
{
int mid = (l + r) >> 1;
if(check(mid)) r = mid;// 1 ~ mid的范围有，向又收缩
else l = mid + 1;
}
printf("-1\n%d\n", r);// 找到打印
return 0;
}
2. acwing1227 分巧克力：（二分 + 数学推导计算）
/*
有K个人，有N块巧克力，其中第i块是Hi*Wi的方格组成的长方形
要从这N块巧克力切出K块巧克力分给他们。
切除的巧克力须要满足：1.是正方形 2.大小相同
例如：一块6*5的巧克力可以切出6块2*2的巧克力或者2块3*3的巧克力。
希望得到的巧克力尽可能的大，请计算出最大的边长是多少？
输入：（输入保证每位小朋友至少能获得一块1*1的巧克力）
第一行包含2个整数N和K
一下N行包含两个整数Hi 和 Wi
输出：
输出最大可能的边长
数据范围：
1 < N, K < 10^5
1 < Hi, Wi < 10^5
*/
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
int h[N], w[N];// 长， 宽
// 二分“二段性”的判断条件
bool check(int mid)
{
LL res = 0;
for(int i = 0; i < n; i ++)
{
// 加括号：先乘积 后下取整 ！= 先下去整 后乘积
// 例如：2 *（3/4） ！= 2 * 3 / 4
res += (LL)h[i] / mid * (w[i] / mid);
if(res >= m) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) scanf("%d%d", &h[i], &w[i]);
// 长度和宽度最大为 1e5
int l = 1, r = 1e5;
while(l < r)
{
int mid = l + r + 1 >> 1;// 向上取整
if(check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", r);
return 0;
}
3. acwing5407 管道（二分、区间合并、差分）
/*
有一根长度为 len 的横向的管道，该管道按照单位长度分为 len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器
一开始管道是空的，位于 Li 的阀门会在 Si 时刻打开，并不断让水流入管道。
对于位于 Li 的阀门，它流入的水在 Ti（Ti >= Si）时刻会使得从第 Li - （Ti - Si）段到 Li + (Ti - Si) 段的传感器检测到水流。
求管道中每一段中间的传感器都检测到有水流的 最早时间。
输入：
第一行：n， len分别表示会打开的阀门数和管道长度
接下来n行包含Li 和 Si，表示位于第Li段管道的阀门会在Si时刻打开
输出：
一个整数
数据范围：
对于30%的测试用例，n <= 200, 1 <= si, len <= 3000
70%, n <= 5000, si, len <= 5000
100%, n <= 10^5, si, len <= 10^9,
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;// 会打开n个阀门， 有m段管道
PII w[N], q[N];
// w: 位于 Li 的阀门会在 Si 时刻打开，并不断让水流入管道。（注意1）
// p: 二分后，每个区间对应的左右端点
// 判断mid时刻是否可以覆盖完所有的位置:
bool check(int mid)
{
int cnt = 0;// 区间数量
for(int i = 0; i < n; i ++)
{
int L = w[i].x, S = w[i].y;// 位置，打开时刻
if(S <= mid)// 时间
{
int t = mid - S;// 距离S经过多长时间
// 确定左右端点 (阀门扩散水)
// max,min：保证 左右端点 在范围内。
int l = max(1, L - t), r = min((LL)m, (LL)L + t);// L + t 爆int （注意2）
q[cnt ++] = {l, r};
}
}
// 按照区间的左端点 升序排序 （注意3）
sort(q, q + cnt);
int st = -1, ed = -1;
// 遍历所有区间：
for(int i = 0; i < cnt; i ++)
{
// 注意：ed + 1，就是不用重合，也要合并（注意4）
// 看end端点，如果end+1端点小于st的话，说明一个区间已经合并完毕。
// 否者就是判断区间是否要扩展，从两个end的中去最大值。
if(q[i].x <= ed + 1) ed = max(ed, q[i].y);
else st = q[i].x, ed = q[i].y;
}
// 判断合并区间的结果是否满足要求。
return st == 1 && ed == m;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) scanf("%d%d", &w[i].x, &w[i].y);
// 2e9：第一个点，在1e9时刻打开阀门，且管道长度为1e9，所以最慢在2e9时刻 都能检测到水
int l = 0, r = 2e9;
while(l < r)
{
int mid = (LL)l + r >> 1;// 2e9
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return 0;
}
二、前缀和：
1. acwing562 壁画（向上取整 + 前缀和）
/*
有N段壁画，每段壁画上面都有一个美观评分（如果它的上面有画的话）
不幸的是，由于洪水泛滥，墙体开始崩溃。
每天可以绘制一段墙体，在第一天，可以自由的选择一段墙面进行绘制。
在接下来的每一天，只能选择与绘制完成的墙面相邻的墙进行作画。
每天结束的时候，一段未被涂颜料的墙将被摧毁（防水颜料），“且毁掉的墙一定只能与一段还未被毁掉的墙面相邻”。
壁画的总体美观程度等于它作画的所有的墙面的美观评分的总和。
要保证，无论墙壁是如何被摧毁的，都可以达到至少B的美观总分。
请问，可以保证达到的美观总分B的最大值是多少？（这个题目叙述，我也是醉了）
输入：
第一行包含整数T，表示有T组测试数据
接下来由T组：
第一行输入一个整数N
第二行行包含一个长度为N的字符串，字符串有数字0 ~ 9构成，第i个字符表示第i段墙面被上色后能达到的美观评分。
输出：
每组数据输出一个结果，每个结果占一行。
结果表示：Case #x：y
其中x为组别编号，y为可以保证达到的美观评分的最大值。
数据范围：
1 <= T <= 100, 2 <= N <= 5*10^6
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5000010;
int n;
int s[N];// 前缀和数组
char str[N];// 字符串
int main()
{
int T;
scanf("%d", &T);
for(int cases = 1; cases <= T; cases ++)
{
scanf("%d", &n);
scanf("%s", str + 1);// 字符串从索引为1的位置开始录入。
for(int i = 1; i <= n; i ++)// 求前缀和
s[i] = s[i - 1] + str[i] - '0';// 注意1:字符边int数
int res = 0, m = (n + 1) / 2;// 注意2：向上取整
for(int i = m; i <= n; i ++)
res = max(res, s[i] - s[i - m]);// 遍历，找到长度为m的最大区间和
printf("Case #%d：%d\n", cases, res);
}
return 0;
}
2. acwing1230 K倍区间（前缀和 + “同余数相减是倍数？”）
/*
给定一个长度为N的数列，A1, A2, ... ,AN 如果其中一段连续的子序列 Ai, ... , Aj 的和是K的倍数，我们就称这个区间[i, j]是K倍区间。
求出数列中总共有多少个K倍区间？
输入：
第一行包含2个整数 N 和 K
以下N行每行都包含一个整数Ai
输出：
输出一个整数，表示K倍区间的数量
数据范围：
1 <= N, K <= 10^6
1 <= Ai <= 10^6
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, k;
LL s[N];
int cnt[N];
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++)
{
// 输入数据的时候 ，顺便求前缀和数组
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
LL res = 0;
cnt[0] ++;
for(int i = 1; i <= n; i ++)
{
res += cnt[s[i] % k];
cnt[s[i] % k] ++;
}
printf("%lld\n", res);// 打印的时候要注意是 long long
return 0;
}
三、差分：
1.acwing4262 空调（差分 + “一加一减求最大”）
/*
有N头奶牛对牛棚的室温十分挑剔，有的喜欢温度低一些，而有的喜欢高一些
奶牛编号从1到N，每个牛栏里有一头奶牛
第i头奶牛希望她的牛栏中的温度是pi，而现在她的牛栏中的温度是ti
为了确保每一头奶牛都感到舒适，安装了一个新的空调系统
该系统进行控制的方式非常有趣，它可以向系统发送命令，告诉它将一组连续的牛栏的温度都升高1个单位或降低。
一组连续的牛栏最短可以包含一个1个。
求出空调系统发送命令的最小数量。
输入：
第一行包含N
下一行包含N个非负整数 p1 ... pn
最后一行包含N个非负整数t1 ... tn
输出：
一个整数，须要使用的最小指令数
数据范围：
1 <= N <= 10^5
0 <= pi, ti <= 10^4
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N]; // A A-B A-B的差分
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
// 直接在原数组里面操作，求出 A-B
for(int i = 1; i <= n; i ++)
{
int b;
scanf("%d", &b);
a[i] -= b;
}
// 从后往前求出A-B的差分数组
for(int i = n; i; i --) a[i] -= a[i - 1];
int pos = 0, neg = 0;// 正数之和 负数之和
for(int i = 1; i <= n; i ++)
{
if(a[i] > 0) pos += a[i];
else neg -= a[i];// 直接求负数的绝对值
}
printf("%d\n", max(pos, neg));
return 0;
}
2. acwing5396 棋盘（二维差分 + “%2 和 &1”）
/*
小蓝拥有n*n大小的棋盘，一开始棋盘上全是白子。
小蓝进行了m次操作，每次操作会将棋盘上某个范围内所有的棋子的颜色取反
（也就是白子变黑子，黑子变白子）
请输出所有操作做完后，棋盘上每个棋子的颜色。
输入：
第一行包含2个整数n，m，表示棋盘大小，操作数
接下来m行，每行包含4个整数
x1,y1,x2,y2，表示将（x1, y1）和 (x2, y2) 范围内的棋子颜色取反。
输出：
输出n行，每行n个0或1表示该位置棋子的颜色。
白色0，黑色1.
数据范围：
30% 1 <= n, m <= 500
100% 1 <= n, m <= 2000 1<= x1, x2, y1, y2 <= n
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, m;
int b[N][N];
int main()
{
scanf("%d%d", &n, &m);
while(m --)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
// 差分：一个矩阵范围都 +/- 去一个数
b[x1][y1] ++;
b[x1][y2 + 1] --;
b[x2 + 1][y1] --;
b[x2 + 1][y2 + 1] ++;
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
b[i][j] += b[i - 1][j] +b[i][j - 1] - b[i - 1][j - 1];// 差分还原为前缀和
printf("%d", b[i][j] & 1);// 相当于b[i][j] % 2
}
puts("");// 换行
}
return 0;
}
四、双指针：
1. acwing3745 牛的学术圈1（h指数）（双指针）
/*
Bessie发表了N篇论文，并且她的第i篇论文得到了ci次其他论文的引用。
h指数等于使得研究员至少h篇引用次数不少于h的论文的最大整数。
例如，如果一名研究员有4篇论文，引用次数分别为（1, 100, 2, 3），则h指数为2，然而若引用次数为（1, 100, 3, 3）。
为了提升她的h指数，Bessie计划写一篇综述，并引用她曾经写过的论文。
由于页数限制，她最多可以引用L篇论文，并且“她只能引用每篇她的论文至多一次”
请帮助Bessie求出在写完这篇综述后，她可以达到的最大h指数。
注意：Bessie的导师可能会告知她纯粹为了提升h指数而写综述是违反学术道德的。
输入：
第一行包含N 和 L
第二行宝行c1 ，...， cn
输出：
可以达到的最大h指数
数据范围：
1 <= N <= 10^5
0 <= ci <= 10^5
0 <= L <= 10^5
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, L;
int q[N];
int main()
{
scanf("%d%d", &n, &L);
for(int i = 1; i <= n; i ++) scanf("%d", &q[i]);
sort(q + 1, q + n + 1, greater<int>());// 降序排序
int res = 0;
// 双指针i，j
// i - j表示的是h-1的个数
for(int i = 1, j = n; i <= n; i ++)
{
while(j && q[j] < i) j --;// q[j] >= i
if(q[i] >= i - 1 && i - j <= L)
res = i;
}
printf("%d\n", res);
return 0;
}
2. acwing4405 统计子矩阵
/*
给定一个N*M的矩阵A，请你统计有多少个子矩阵（最小1*1，最大N*M）满足子矩阵中所有数的和不超过给定的整数K。
输入：
第一行包含3个整数N, M 和 K
之后N行每行包含M个整数，代表矩阵A。
输出：
一个整数表示答案。
数据范围：
30% N, M <= 20
70% N, M <= 100
100% 1 <= N, M <= 500 0 <= Aij <= 1000
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 510;
int n, m, k;
int s[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j];// 动态求 列 的前缀和
}
LL res = 0;
for(int i = 1; i <= n; i ++)// 上边界
for(int j = i; j <= n; j ++)// 下边界
for(int l = 1, r = 1, sum = 0; r <= m; r ++)// 用双指针枚举左右边界
{
sum += s[j][r] - s[i - 1][r];// 加上第r列
while(sum > k)
{
sum -= s[j][l] - s[i - 1][l];// 删掉第l列
l ++;
}
res += r - l + 1;// 方案数
}
printf("%lld\n", res);
return 0;
}
五、归并排序：
六、多路归并：
七、贡献法：
1. acwing4261 孤独的照片
/*
john购买了N头新的奶牛，有G和H两种品种
奶牛排成一排，john想要为每个连续不少于3头奶牛的序列拍摄一张照片。
孤独的照片：其中只有一头牛的品种是 G 或 H。
他最后会把所有的“孤独的照片”给扔掉。
给定奶牛的排列方式，求出john会扔掉多少张“孤独的照片”。
如果两张照片以不同位置的奶牛开始 或 结束，则认为它们是不同的。
输入：
第一行包含N
第二行包含长度为N的字符串。(内容是G 或 H)
输出：
扔掉的数量
数据范围：
3 <= N <= 5*10^5
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 500010;
int n;
char str[N];
int l[N], r[N];// 每个字符的左/右边，连续出现与本身不同字符的个数。
int main()
{
scanf("%d", &n);
scanf("%s", str);
// 如果出现的字符是G，那么l[i]为h，而且将h重置，然后g++
for(int i = 0, h = 0, g = 0; i < n; i ++)
if(str[i] == 'G') l[i] = h, h = 0, g ++;
else l[i] = g, g = 0, h ++;
for(int i = n - 1, h = 0, g = 0; i >= 0; i --)
if(str[i] == 'G') r[i] = h, h = 0, g ++;
else r[i] = g, g = 0, h ++;
LL res = 0;
for(int i = 0; i < n; i ++)
// 注意：l[i] 或 r[i] 可能会是0.
res += (LL)l[i] * r[i] + max(l[i] - 1, 0) + max(r[i] - 1, 0);
printf("%lld", res);
return 0;
}
2.acwing2868 子串分值（贡献法 + 模拟 + 数学推导）
/*
对于一个字符串S，我们定义S的分值f（S）为S重恰好出现一次的字符个数。
例如：f("aba") = 1, f("abc") = 3, f("aaa") = 0
现在给定一个字符串，请计算出所有非空子串s[i, j]的f（s[i, j]）之和是多少？
输入：一个全部有小写字母组成的字符串
输出：一个整数
数据范围：
20% 1 <= n <= 10
40% 1 <= n <= 100
50% 1 <= n <= 1000
60% 1 <= n <= 10000
100% 1 <= n <= 100000
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
char str[N];
int l[N], r[N], p[26];// 当前字母左边第一次出现的位置，右边第一次出现的位置
// p：辅助计算 ：存储下标i代表字母 出现的位置
int main()
{
// 从1开始
scanf("%s", str + 1);
n = strlen(str + 1);
// 左边：p[i]全为0 (边界情况)
for(int i = 1; i <= n; i ++)
{
int t = str[i] - 'a';// 0 ~ 25
l[i] = p[t];
p[t] = i;
}
// 右边：p[i]全为 n + 1
for(int i = 0; i < 26; i ++) p[i] = n + 1;
for(int i = n; i; i --)
{
int t = str[i] - 'a';
r[i] = p[t];
p[t] = i;
}
LL res = 0;
for(int i = 1; i <= n; i ++)
res += (LL) (i - l[i]) * (r[i] - i);// 计算公式
printf("%lld", res);
return 0;
}
八、日期问题：
1. acwing3498 日期差值：
/*
有两个日期，求两个日期之间的天数，如果两个日期是连续的，
我们规定它们之间的天数为2天。（包头包尾）
输入：输入包含多组数据
每组数据占2行，分别表示2个日期，形式为YYYYMMDD
输出：
每组数据输出一行，即日期差值
数据范围：
年份范围[1, 9999]，保证输入的日期合法。测试的数据组数不超过100.
*/
#include <iostream>
#include <algorithm>
#include <cstring>
// #include <cmath>
using namespace std;
// 平年每月的天数
const int months[] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
// 判断是否是闰年，是闰年就要“返回+1”
int is_leap(int year)
{
// 不能被100整除，可以被4整除 或 可以被400整除
if(year % 100 && year % 4 == 0 || year % 400 == 0)
return 1;
return 0;
}
// 获取year年month月的天数
int get_month_days(int year, int month)
{
int res = months[month];
if(month == 2) res += is_leap(year);// 闰年2月天数+1
return res;
}
// 获取 从y年m月d日 总天数
int get_total_days(int y, int m, int d)
{
// 年
int res = 0;
for(int i = 1; i < y; i ++)
res += 365 + is_leap(i);
// 月
for(int i = 1; i < m; i ++)
res += get_month_days(y, i);
// 日
return res + d;
}
int main()
{
int y1, m1, d1, y2, m2, d2;
// scanf的返回值是成功读取的输入项的数量，
// 如果达到文件末尾或发生输入错误，它会返回EOF（通常是-1）。
// %04d表示读取一个整数，并且这个整数至少占用4位数字，如果不足4位则在前面补0。
// 这通常用于读取年份，如2023。
while(scanf("%04d%02d%02d", &y1, &m1, &d1) != -1)
{
scanf("%04d%02d%02d", &y2, &m2, &d2);
printf("%d\n", abs( get_total_days(y1, m1, d1) - get_total_days(y2, m2, d2) ) + 1);
}
return 0;
}
2. acwing2867 回文日期：
/*
日期按“yyyymmdd”的格式写成一个8位数是回文数，那么这个日期就是 普通回文日期。
还有 特殊的回文日期：ABABBABA类型的。
例子：20200202、20211202、21211212
给定一个8位数的日期，请你计算该日期之后的下一个回文日期和下一个ABABBABA类型的回文日期各是哪一天？（有可能相等）
注意：本题一定有解
输入：
一个8为整数N
输出：2行
第1行表示下一个回文日期
第2行表示下一个ABABBABA类型的回文日期
数据范围：
1000 01 01 < N < 8999 12 31 (保证N合法)
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int months[] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
int is_leap(int year)
{
if(year % 100 && year % 4 == 0 || year % 400 == 0)
return 1;
return 0;
}
// 获取y年m月有多少天
int get_days(int y, int m)
{
if(m == 2) return 28 + is_leap(y);
return months[m];
}
// 天数+1
// d+1，可能到下一月份，m+1可能到下一年
void next_day(int& y, int& m, int& d)
{
d ++;
if(d > get_days(y, m))
{
d = 1;
m ++;
if(m > 12)
{
m = 1;
y ++;
}
}
}
// 检查是否是回文串
bool check1(char s[])
{
for(int i = 0, j = 7; i < j; i ++, j --)
if(s[i] != s[j])
return false;
return true;
}
// 检查是否是ABABBABA类型的回文串
bool check2(char s[])
{
// 只用判断前4个就好
char a = s[0], b = s[1], c = s[2], d = s[3];
if(a == c && b == d && a != b)
return true;
return false;
}
int main()
{
int y, m, d;
scanf("%04d%02d%02d", &y, &m, &d);
char s[10] = {0};
bool found1 = false, found2 = false;// 标志
while(!found1 || !found2)
{
next_day(y, m, d);// 下一天
// 注意1：将三个整数y、m和d按照指定的格式"%04d%02d%02d"写入字符串s中。
sprintf(s, "%04d%02d%02d", y, m, d);
if(check1(s))
{
if(!found1)
{
puts(s);
found1 = true;
}
// 在是回文串的基础上，判断是否满足 第二个条件
if(!found2 && check2(s))
{
puts(s);
found2 = true;
}
}
}
return 0;
}
九、区间合并：
十、递归：
十一、DFS：
十二、回溯：
十三、BFS：
十四、Flood Fill：
十五、并查集：
十六、哈希：
十七、单调队列：
十八、树状数组：
十九、状态压缩dp：
二十、线性dp：
二十一、背包问题：
二十二、区间dp：
二十三、树状dp：
二十四、快速幂：
二十五、最大公约数：
二十六、分解质因数：
二十七、矩阵乘法：
二十八、组合计数：
二十九、数学期望：
三十、欧拉函数：
三十一、最短路：
三十二、贪心：
三十三、括号序列：
总结
提示：这里对文章进行总结：
💕💕💕
![[尚硅谷flink] 检查点笔记](https://img-blog.csdnimg.cn/img_convert/88b730e4882d6a9c23fe17eeaa312791.png)
