首页 > 代码库 > zoj 3950 how many nines
zoj 3950 how many nines
https://vjudge.net/problem/ZOJ-3950
题意:
给出两个日期,计算从第一个日期开始到第二个日期,每一天的日期中的9加起来一共有多少个。
思路:
看题解补的题。首先看这题的数据量,样例就有10的5次方个,而且那只能考虑O(1)的算法喽,那么就对日期进行一个大的预处理。把从2000,1,1到10000,1,1的显示的9全部算出来,然后查询的时候直接相减,每次查询只有O(1)的复杂度。具体还是看代码啦。
代码:
1 #include <stdio.h> 2 #include <string.h> 3 4 int sum[10005][15][35],pre[10005][15][35]; 5 int mon[15] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; 6 7 8 int leap(int x) 9 { 10 if (x % 400 == 0) return 1; 11 if (x % 100 == 0) return 0; 12 if (x % 4 == 0) return 1; 13 14 return 0; 15 } 16 17 int check(int y,int m,int d) 18 { 19 int num = 0; 20 21 while (y) 22 { 23 y % 10 == 9 ? ++num : num += 0; 24 y /= 10; 25 } 26 27 while (m) 28 { 29 m % 10 == 9 ? ++num : num += 0; 30 m /= 10; 31 } 32 33 while (d) 34 { 35 d % 10 == 9 ? ++num : num += 0; 36 d /= 10; 37 } 38 39 return num; 40 } 41 42 void init(int y1,int m1,int d1,int y2,int m2,int d2) 43 { 44 int tmp = 0; 45 46 47 while (y1 != y2 || m1 != m2 || d1 != d2) 48 { 49 mon[2] = leap(y1) + 28; 50 51 pre[y1][m1][d1] = tmp;//tmp是到前一个日期显示的9的数量。 52 53 tmp += check(y1,m1,d1); 54 55 sum[y1][m1][d1] = tmp;//现在的日期显示的9的数量 56 57 if (++d1 > mon[m1]) 58 { 59 d1 = 1; 60 61 if (++m1 > 12) 62 { 63 m1 = 1; 64 mon[2] = 28 + leap(++y1); 65 } 66 } 67 } 68 } 69 70 int main() 71 { 72 int t; 73 74 scanf("%d",&t); 75 76 init(2000,1,1,10000,1,1); 77 78 while (t--) 79 { 80 int y1,m1,d1,y2,m2,d2; 81 82 scanf("%d%d%d%d%d%d",&y1,&m1,&d1,&y2,&m2,&d2); 83 84 printf("%d\n",sum[y2][m2][d2] - pre[y1][m1][d1]);//结束日期减去开始日期之前的那天,因为开始日期也要算的。 85 } 86 87 return 0; 88 }
zoj 3950 how many nines
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。