首页 > 代码库 > ZOJ How Many Nines 模拟 | 打表
ZOJ How Many Nines 模拟 | 打表
If we represent a date in the format YYYY-MM-DD (for example, 2017-04-09), do you know how many 9s will appear in all the dates between Y1-M1-D1 and Y2-M2-D2 (both inclusive)?
Note that you should take leap years into consideration. A leap year is a year which can be divided by 400 or can be divided by 4 but can‘t be divided by 100.
Input
The first line of the input is an integer T (1 ≤ T ≤ 105), indicating the number of test cases. Then T test cases follow. For each test case:
The first and only line contains six integers Y1, M1, D1, Y2, M2, D2, their meanings are described above.
It‘s guaranteed that Y1-M1-D1 is not larger than Y2-M2-D2. Both Y1-M1-D1 and Y2-M2-D2 are between 2000-01-01 and 9999-12-31, and both dates are valid.
We kindly remind you that this problem contains large I/O file, so it‘s recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
Output
For each test case, you should output one line containing one integer, indicating the answer of this test case.
Sample Input
4 2017 04 09 2017 05 09 2100 02 01 2100 03 01 9996 02 01 9996 03 01 2000 01 01 9999 12 31
Sample Output
4 2 93 1763534
Hint
For the first test case, four 9s appear in all the dates between 2017-04-09 and 2017-05-09. They are: 2017-04-09 (one 9), 2017-04-19 (one 9), 2017-04-29 (one 9), and 2017-05-09 (one 9).
For the second test case, as year 2100 is not a leap year, only two 9s appear in all the dates between 2100-02-01 and 2100-03-01. They are: 2017-02-09 (one 9) and 2017-02-19 (one 9).
For the third test case, at least three 9s appear in each date between 9996-02-01 and 9996-03-01. Also, there are three additional nines, namely 9996-02-09 (one 9), 9996-02-19 (one 9) and 9996-02-29 (one 9). So the answer is 3 × 30 + 3 = 93.
这题其实用一个数组int sum[10000][12][31]表示前缀和，第i年，第j个月，第k天有多少个合法情况。
然后区间减法即可。
不过我做的时候没想到这样，直接用模拟，wa良久。
我是先把begin的年份一直暴力向后算，算到新一年的1月1号，然后end的也一直向前算，算到那一年的1月一号。
然后直接对年份前缀和即可。然后边界很难处理。烦。。
如果能提交要再写一次。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> bool isyear(int val) { if (val % 400 == 0) return true; if (val % 4 == 0 && val % 100 != 0) return true; return false; } int has[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; void add(int &year, int &month, int &day) { day++; int t = has[month]; if (month == 2 && isyear(year)) t++; if (day > t) { day = 1; month++; if (month > 12) { year++; month = 1; } } } void cut(int &year, int &month, int &day) { if (day != 1) day--; else { if (month == 1) { month = 12; year--; } else month--; day = has[month]; if (month == 2 && isyear(year)) day++; } } bool toless(int year1, int month1, int day1, int year2, int month2, int day2) { if (year1 < year2) return true; if (month1 < month2) return true; if (day1 < day2) return true; return false; } int cnt(int val) { int ans = 0; while (val / 10 > 0) { ans += val % 10 == 9; val /= 10; } ans += val == 9; return ans; } LL sum[9999 + 20]; void work() { int year1, month1, day1; int year2, month2, day2; scanf("%d%d%d%d%d%d", &year1, &month1, &day1, &year2, &month2, &day2); LL ans = 0; while (toless(year1, month1, day1, year2, month2, day2)) { if (month1 == 1 && day1 == 1) { break; } if (month1 == 9) ans++; if (day1 % 10 == 9) ans++; ans += cnt(year1); add(year1, month1, day1); } while (toless(year1, month1, day1, year2, month2, day2)) { bool flag = false; if (month2 == 1 && day2 == 1) { flag = true; } if (month2 == 9) ans++; if (day2 % 10 == 9) ans++; ans += cnt(year2); if (flag) break; cut(year2, month2, day2); } if (!(month1 == 1 && day1 == 1)) { //样例一的情况，移动去不了1月1号 if (month1 == 9) ans++; if (day1 % 10 == 9) ans++; ans += cnt(year1); printf("%lld\n", ans); return; } if (year1 == year2) { //1987 12 28 1988 1 1 ans += cnt(year1); } // cout << year1 << " " << month1 << " " << day1 << endl; // cout << year2 << " " << month2 << " " << day2 << endl; ans += sum[year2 - 1] - sum[year1 - 1]; printf("%lld\n", ans); } void init() { int year = 1; while (year <= 9999) { sum[year] += sum[year - 1]; sum[year] += cnt(year) * (365 + isyear(year)); sum[year] += 30; sum[year] += 3 * 11; sum[year] += 2 + isyear(year); year++; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif init(); int t; scanf("%d", &t); while (t--) work(); return 0; }
ZOJ How Many Nines 模拟 | 打表