1464 字
7 分钟
AD 2020
题目描述
统计 起始日期（Y1M1D1）到结束日期（Y2M2D2）之间（包含首尾） 的「减灾日」总数，需考虑闰年对日期有效性的影响。
关键定义
减灾日判定规则
- 日期格式统一为 YYYYMMDD（8 位数字字符串，例如 2111 年 2 月 2 日表示为 21110202）
- 若该 8 位字符串中包含子串 “202”，则该日期为减灾日
闰年判定规则
- 符合以下任一条件即为闰年：
- 能被 400 整除
- 能被 4 整除但不能被 100 整除
bool Year(int x) { if ((x % 4 == 0 && x % 100 != 0) || x % 400 == 0) return true; return false;}- 闰年 2 月有 29 天，平年 2 月有 28 天
- 用于判断日期合法性、计算天数
- 题目已保证输入日期有效，无需额外验证输入，但计算过程中需考虑
输入输出要求
输入
- 第一行是正整数 T（1 ≤ T ≤ 10⁵），表示测试用例数量
- 每组用例一行，包含 6 个整数：Y1 M1 D1 Y2 M2 D2
- Y1 M1 D1：起始年 / 月 / 日
- Y2 M2 D2：结束年 / 月 / 日
- 数据约束：
- 起始日期 ≤ 结束日期
- 日期范围在 20000101 ~ 99991231 之间
- 所有日期均为有效日期
- 注意：输入输出数据量较大，需使用快速 IO 方法（如 C++ 的 scanf/printf）
输出
- 每组用例输出一行一个整数，即该日期区间内的减灾日总数
关键补充（从样例提炼）
若某一年的年份（YYYY）本身包含 “202”（如 2202 年，YYYY=2202），则该年的所有日期都是减灾日，无需逐个判断日期的月和日。
示例说明
输入示例
32111 02 01 2111 02 032202 01 01 2202 12 312000 01 01 9999 12 31输出示例
136544294解题思路
- 关键观察：
- 观察到数据范围在 20000101 ~ 99991231 之间，若是每个组数据都爆力查找，一定会超时，需要考虑更高效的算法，利用前缀和优化查询效率，答案就是 结束日期 - 开始日期 （若开始日期也是则 + 1）。
- 算法设计：
- 将数组 f 定义为 f[i][j][k] 表示从 20000101 到 i 年 j 月 k 日 之间的减灾日数量。
- 直接暴力检查 “ijk” 是否为灾难日，并用 val 来线性存储，若是，则 val = val + 1， 且f[i][j][k] = val(避免了通过状态转移的方式解决问题,更加简便)
- 整体时间复杂度为O(T)
- 本题收获/踩坑点：
- 在年月日转换为字符串时，忘记了前导零
- 自己写的toString函数时，忘记了处理前导零的情况(对前导零的处理并不擅长)
//这是我目前想到的处理前导零的方法// x 表示处理的值 mod 表示最高位的基数(比如 4444 最高位基数为 1000)string to_string(int x,int mod){ string s = ""; while(mod >= 1){ //表示当前剩余位数 s = s + char((x - x % mod) / mod + '0'); // 最高位 = x - 除了最高位以外的数字 x %= mod; //去除最高位 mod /= 10; //位数 - 1 } return x;}- 我在处理闰年的数据非常冗余，判断当前是否是闰年并且是2月份，可以直接在年份中修改2月的天数为29天（若不是闰年则为28天）
//直接在年份中修改2月的天数为29天（若不是闰年则为28天） if( y % 400 == 0 || (y % 100 != 0 && y % 4 == 0) ) months[2] = 29; else months[2] = 28;代码
#include<bits/stdc++.h>
using namespace std;//#define int long long#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#define x first#define y second#define endl "\n"typedef signed long long LL;typedef pair<int, int> PII;
const int N = 1e5 + 10;
int a[10000][15][33];int m[13] = { 0, 31, 28, 31, 30 ,31, 30, 31, 31, 30, 31, 30 ,31 };
bool Year(int x) { if ((x % 4 == 0 && x % 100 != 0) || x % 400 == 0) { return true; } return false;}
//分别表示 当前值 和 预期位数(4位是 1000， 3位 100 以此类推)string to_string(int x,int mod) { string s = ""; while (mod >= 1) { s = s + char((x - x % mod) / mod + 48); x = x % mod; mod = mod / 10; } return s;}
int check(string s) { for (int i = 0; i <= 5; i++) { if (s[i] == '2' && s[i + 1] == '0' && s[i + 2] == '2') { return 1; } } return 0;}
//推荐写法// void init( )// {// int total = 0;// for( int y = 2000; y <= 9999; ++ y )// {// if( y % 400 == 0 || (y % 100 != 0 && y % 4 == 0) ) months[2] = 29;// else months[2] = 28;// for( int m = 1; m <= 12; ++ m )// {// for( int d = 1; d <= months[m]; ++ d )// {// if( check( y, m, d ) ) total ++;// sum[y][m][d] = total;// }// }// }// }
//不推荐写法：第一次写void init() { for (int i = 2000; i <= 9999; i++) { //从 2000 年到 9999年 a[i][0][0] = a[i - 1][12][31]; // i 年 0 月 0 日从 i - 1 年 12 月 31 日转换来 for (int j = 1; j <= 12; j++) { int flag = int(Year(i) && j == 2); //如果当前为 闰年 且 2月份 a[i][j][0] = a[i][j - 1][m[j - 1] + int(Year(i) && (j - 1) == 2)]; for (int k = 1; k <= m[j] + flag; k++) { string s = to_string(i, 1000) + to_string(j,10) + to_string(k,10); a[i][j][k] = a[i][j][k - 1] + check(s); //若是减灾日则 + 1否则迭代 } } }}
void solve() { string s; int y1, y2, m1, m2, d1, d2; cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2; //s = to_string(y1, 1000) + to_string(m1, 10) + to_string(d1 + 1, 10);// cout << s << endl;// cout << check(s) << endl; cout << a[y2][m2][d2] - a[y1][m1][d1 - 1] << endl;}
signed main() { IOS; init(); int _; cin >> _; while (_--) { solve(); }}部分信息可能已经过时