hihocoder1148 February 29（区间闰年计数）-白红宇

hihocoder1148 February 29（区间闰年计数）

阅读量：5251 次

发布时间：2019-06-14

本文共 1672 字，大约阅读时间需要 5 分钟。

hihocoder1148

因为题目没有给范围，我本来是这么写的。

1 for(int i = 0; i <= 10000; i++){2     if(i%4==0&&i%100!=0||i%400==0){3             cnt++;4     }5     memo[i] = cnt;6 }

然后RE了，事实证明长度还是很大的。

本题的关键在于利用计算闰年的方法巧妙地实现类似以上的计数。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #include
                 14 #define lson l, m, rt<<115 #define rson m+1, r, rt<<1|116 #define IO ios::sync_with_stdio(false);cin.tie(0);17 #define INF 0x3f3f3f3f18 #define MAXN 10001019 const int MOD=1e9+7;20 typedef long long ll;21 using namespace std;22 int n, d1, d2, yy1, y2;23 char s1[110], s2[110];24 map
                  
                    mp;25 int main()26 {27 cin >> n;28 int kase=0, cnt=0;29 mp["January"]=1;mp["February"]=2;mp["March"]=3;30 mp["April"]=4;mp["May"]=5;mp["June"]=6;31 mp["July"]=7;mp["August"]=8;mp["September"]=9;32 mp["October"]=10;mp["November"]=11;mp["December"]=12;33 for(int i = 0; i < n; i++){34 cnt=0;35 scanf("%s %d, %d", s1, &d1, &yy1);36 scanf("%s %d, %d", s2, &d2, &y2);37 if(yy1 != y2){38 //容斥的感觉39 int k1 = yy1/4-yy1/100+yy1/400;40 int k2 = (y2-1)/4-(y2-1)/100+(y2-1)/400;41 cnt=k2-k1; 42 43 if(yy1%4==0&&yy1%100!=0||yy1%400==0){44 if(mp[s1] <= 2){45 cnt++;46 }47 }48 if(y2%4==0&&y2%100!=0||y2%400==0){49 if(mp[s2] > 2||mp[s2]==2&&d2==29){50 cnt++;51 }52 } 53 } 54 else{55 if(yy1%4==0&&yy1%100!=0||yy1%400==0){56 if((mp[s1] <= 2)&&(mp[s2]>2||mp[s2]==2&&d2==29))57 cnt++;58 }59 }60 cout << "Case #" << ++kase << ": ";61 cout << cnt << endl;62 }63 return 0;64 }