题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3950
题意 给出两个日期 求 这个日期 经过 到 另外一个日期 这中间经过的日期 （包括两个端点） 中 有多少个9
思路
刚开始 想模拟 然后 测试数据 达到 1e5 然后 T掉了 可能是 模拟写的 不够优吧
后来 想到用 前缀和
但是 一个 日子 99991231 如果 开 一维数组 保存的话 会MLE
然后 想到用 三维数组
就可以了
AC代码
#include <string> #include <iostream> #include <cstdio> #include <cstring> #include <ctype.h> #include <cmath> #include <climits> #include <cstdlib> #include <algorithm> #include <deque> #include <queue> #include <vector> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define pb push_back #define CLR(a) memset(a, 0, sizeof(a)) using namespace std; typedef long long ll; typedef unsigned long long ull; const int INf = 0x3f3f3f3f; const int maxn = 1e4 + 5; const int year = 0; int leap[maxn]; int coun[maxn]; ll ans[maxn][15][35]; bool isleap(int x) { if ((x % 4 == 0 && x % 100 != 0) || x % 400 == 0) return true; return false; } int tran(int x) { int ans = 0; while (x) { if (x % 10 == 9) ans++; x /= 10; } return ans; } void init() { int tot[2][13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, }; CLR(leap); CLR(ans); for (int i = 2000; i <= 9999; i++) { if (isleap(i)) leap[i] = 1; coun[i] = tran(i); } ll vis = 0; for (int i = 2000, j = 1, k = 1; ; ) { ans[i][j][k] = vis + coun[i] + tran(j) + tran(k); vis = ans[i][j][k]; k++; if (tot[leap[i]][j] == k - 1) { j++; k = 1; } if (j == 13) { i++; j = 1; } if (i == 10000) break; } } int main() { init(); int t; scanf("%d", &t); while (t--) { int a, b, c, d, e, f; scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f); ll answ = ans[d][e][f] - ans[a][b][c]; answ += tran(a) + tran(b) + tran(c); printf("%lld\n", answ); } }转载于:https://www.cnblogs.com/Dup4/p/9433163.html
