程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> hdu 5439 Aggregated Counting(長春網絡賽——找規律+二分)

hdu 5439 Aggregated Counting(長春網絡賽——找規律+二分)

編輯:關於C

Aggregated Counting

Time Limit: 1500/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 665Accepted Submission(s): 302

Problem Description   Aggregated Counting Meetup (ACM) is a regular event hosted by Intercontinental Crazily Passionate Counters (ICPC). The ICPC people recently proposed an interesting sequence at ACM2016 and encountered a problem needed to be solved.

The sequence is generated by the following scheme.
1. First, write down 1, 2 on a paper.
2. The 2nd number is 2, write down 2 2’s (including the one originally on the paper). The paper thus has 1, 2, 2 written on it.
3. The 3rd number is 2, write down 2 3’s. 1, 2, 2, 3, 3 is now shown on the paper.
4. The 4th number is 3, write down 3 4’s. 1, 2, 2, 3, 3, 4, 4, 4 is now shown on the paper.
5. The procedure continues indefinitely as you can imagine. 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, . . . .

The ICPC is widely renowned for its counting ability. At ACM2016, they came up with all sorts of intriguing problems in regard to this sequence, and here is one: Given a positive numbern\, First of all, find out the position of the last n\ that appeared in the sequence. For instance, the position of the last 3 is 5, the position of the last 4 is 8. After obtaining the position, do the same again: Find out the position of the last (position number). For instance, the position of the last 3 is 5, and the position of the last 5 is 11. ICPC would like you to help them tackle such problems efficiently.

   
Input   The first line contains a positive integer T,T≤2000\, indicating the number of queries to follow. Each of the following T\ lines contain a positive number n(n≤10\9\)\ representing a query.    
Output   Output the last position of the last position of each queryn\. In case the answer is greater than 1000000006\, please modulo the answer with 1000000007\.    
Sample Input  

3 3 10 100000
 
 

Sample Output  

11 217 507231491
 
 

Source   2015 ACM/ICPC Asia Regional Changchun Online    
Recommend   hujie|We have carefully selected several similar problems for you:56645663566256615660     題目大意::按下列規則生成一組序列,令f(n)為n這個數在序列中出現的最後一個位置,求f(f(n))的值。

解題思路:

令原序列為a,根據定義和序列的生成規則可以推出:

  • f(n)等於a的前n項和
  • f(n)是n這個數在a中出現的最後一個位置

    f(f(n))的含義為:a的前m項和,m為n在a中最後出現的位置。所以f(f(n))的計算式可以寫成:

    f(f(n))=1 + (2+3)*2 + (4+5)*3 + (6+7+8)*4 + ... + (...+n)*t

    大概就是上述的內容,我這裡采用了幾個數組來存取上述的過程,把公式整理出來。

    詳見代碼。

     

    #include 
    #include 
    #include 
    #include 
    
    using namespace std;
    
    #define N 450010
    const int Mod=(1e9+7);
    
    long long a[N];//表示第i個的結尾數字
    int b[N];//表示i出現了幾次
    long long s[N];//表示前i個和
    
    int main()
    {
        a[1]=1;
        a[2]=3;
        a[3]=5;
        b[1]=1;
        b[2]=2;
        b[3]=2;
        s[1]=1;
        s[2]=11;
        s[3]=38;
    
        int k=4,pre=4,kk=3;//k用來循環,pre表示的當前這一列數的下標,kk表示下標對應的數字是多少
        while (a[k-1]<=1e9)
        {
            for (k=pre;ka[mid-1])
                {
                    break;
                }
                else
                {
                    if (n>a[mid])
                    {
                        l=mid+1;
                    }
                    else
                        r=mid;
                }
            }
            printf ("%lld\n",(s[mid-1]+mid*((a[mid-1]+1+n)*(n-a[mid-1])/2))%Mod);
        }
        return 0;
    }
    
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved