lightoj1234 分段打表

àì夳堔傛蜴生んèń 2022-08-10 09:47 164阅读 0赞

1234 - Harmonic Number

<table> 
 <tbody> 
  <tr> 
   <td title="special judge"><a href="http://lightoj.com/volume_submit.php?problem=1234" rel="nofollow"><img src="http://lightoj.com/images/submit3.png" alt=""> </a></td> 
   <td><a href="http://lightoj.com/volume_showproblem.php?problem=1234&amp;language=english&amp;type=pdf" rel="nofollow">PDF (English) </a></td> 
   <td><a href="http://lightoj.com/volume_problemstat.php?problem=1234" rel="nofollow">Statistics </a></td> 
   <td><a href="http://lightoj.com/forum_showproblem.php?problem=1234" rel="nofollow">Forum </a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td>Time Limit: <span style="color:#B45F04">3 second(s)</span></td> 
   <td>Memory Limit: <span style="color:#B45F04">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

In mathematics, the **nth** harmonic number isthe sum of the reciprocals of the first **n** natural numbers:

![a1.png][]

![a2.png][]

In this problem, you are given **n**, you have to find **Hn**.

# Input #

Input starts with an integer **T (≤ 10000)**,denoting the number of test cases.

Each case starts with a line containing an integer **n (1≤ n ≤ 108)**.

# Output #

For each case, print the case number and the **nth**harmonic number. Errors less than **10\-8** will be ignored.

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Sample Input</h1> </td> 
   <td> <h1>Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>12</p> <p>1</p> <p>2</p> <p>3</p> <p>4</p> <p>5</p> <p>6</p> <p>7</p> <p>8</p> <p>9</p> <p>90000000</p> <p>99999999</p> <p>100000000</p> </td> 
   <td> <p>Case 1: 1</p> <p>Case 2: 1.5</p> <p>Case 3: 1.8333333333</p> <p>Case 4: 2.0833333333</p> <p>Case 5: 2.2833333333</p> <p>Case 6: 2.450</p> <p>Case 7: 2.5928571429</p> <p>Case 8: 2.7178571429</p> <p>Case 9: 2.8289682540</p> <p>Case 10: 18.8925358988</p> <p>Case 11: 18.9978964039</p> <p>Case 12: 18.9978964139</p> </td> 
  </tr> 
 </tbody> 
</table>

题意：不说了。

分析：一亿的数据量，可以每50个或者100个记录下来。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=1e8;
    double a[N/50+50];
    void init()
    {
        double t=1.0;
        for(int i=2;i<=N;i++)
        {
            t += 1.0/i;
            if(i%50 == 0)
            {
                a[i/50]=t;
            }
        }
    }
    int main()
    {
        int T=in(),ii=1;
        init();
        while(T--)
        {
            int n=in();
            double ans = a[n/50];
            for(int i=n/50*50+1;i<=n;i++)
            {
                ans += 1.0/i;
            }
            printf("Case %d: %.10lf\n",ii++,ans);
        }
        return 0;
    }

[a1.png]: /images/20220731/e5fad4b5af164fa19f2b596ea1510deb.png
[a2.png]: /images/20220731/f6402283e274475885fcab942892bad8.png