• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2011年5月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

            題目地址:

                 http://acm.hdu.edu.cn/showproblem.php?pid=2227 

            題目描述:

            Find the nondecreasing subsequences

            Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 211    Accepted Submission(s): 80


            Problem Description
            How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, ...., sn} ? For example, we assume that S = {1, 2, 3}, and you can find seven nondecreasing subsequences, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
             

            Input
            The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, ...., sn}, 1 <= n <= 100000, 0 <= si <= 2^31.
             

            Output
            For each test case, output one line containing the number of nondecreasing subsequences you can find from the sequence S, the answer should % 1000000007.
             

            Sample Input
            3 1 2 3
             

            Sample Output
            7
             

             題目分析: 

                     整整一天的時間, 終于是把這個題A了  ,HDU 第一,  紀念下.....................

            1HUT-MiYu375MS1824K2358BG++

            2010-08-27 09:44:32 

             但也沒有什么值得高興的,  題目的思路是 小A 的,  0rz.......................  現在還是沒有理解樹狀數組是怎么解這一題的,  它的思路是怎樣的,

            一點也沒明白,   剛開始做的時候, 還以為 輸入數據已經是按非遞減排序了, 所以直接用 公式 2^n - 1, WA ...

            .....  問過小A 才發現, 輸入數據是 隨機的.  這時就要像找上升子串一樣, 找到它 所有的上升子串.  這里用到了 樹狀數組, 繼續理解-ing......

             

            先發代碼 :

             

            /*
            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
                      http://www.cnblog.com/MiYu
            Author By : MiYu
            Test      : 1
            Program   : 2227 
            */

            #include <iostream>
            #include <algorithm>
            using namespace std;
            #define lowbit(x) (x&(-x))
            int num[100005];
            int numcopy[100005];
            int hash[100005];
            int com[100005];
            int nCount = 1;
            void add ( int x,int k )
            {
                 while ( x <= nCount )
                 {
                       com[x] += k;
                       if ( com[x] >= 1000000007 ) com[x] %= 1000000007;
                       x += lowbit(x); 
                 } 
            }
            int sum ( int x )
            {
                int s = 0;
                while ( x > 0 )
                {
                       s += com[x];
                       if ( s >= 1000000007 ) s %= 1000000007;
                       x -= lowbit(x);
                } 
                return s %= 1000000007;
            }
            int cmp (const void *a, const void *b)
            {
                return *((int*)a) - *((int*)b); 
            }
            int sfind ( int x )
            {
                int *p = (int *)bsearch ( &x,hash+1,nCount+1,sizeof ( int ),cmp ); 
                return p - hash;
            }
            int find(int num){
                int top=1,bottom=nCount,mid=(top+bottom)/2,ans=mid;
                while(num!=hash[ans]){
                    if(hash[mid]<=num){
                        top=(ans=mid)+1;
                    }else{
                        bottom=mid-1;
                    }
                    mid=(top+bottom)/2;
                }
                return ans;
            }

            inline bool scan_d(int &num)  //整數輸入
            {
                    char in;bool IsN=false;
                    in=getchar();
                    if(in==EOF) return false;
                    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
                    if(in=='-'){ IsN=true;num=0;}
                    else num=in-'0';
                    while(in=getchar(),in>='0'&&in<='9'){
                            num*=10,num+=in-'0';
                    }
                    if(IsN) num=-num;
                    return true;
            }
            int main ()
            {
                int N;
                while ( scan_d ( N ) )
                {
                       for ( int i = 0; i != N; ++ i )
                           scan_d ( num[i] ),numcopy[i] = num[i];
                       sort ( num, num + N );
                       memset ( com,0,sizeof (com) );
                       nCount = 1;
                       hash[1] = num[0];
                       for ( int i = 1; i < N; ++ i )
                       {
                             if ( num[i] != num[i-1] )
                                  hash[++nCount] = num[i]; 
                       } 
                       for ( int i = 0; i < N; ++ i )
                       {
                            int pos = find ( numcopy[i] ); 
                            int res = sum ( pos ) + 1;
                            add ( pos,res );
                       }
                       cout << sum ( nCount ) << endl;
                }
                return 0;
            }

             

             

            一本久久综合亚洲鲁鲁五月天| 狠狠色婷婷久久综合频道日韩| 97久久国产综合精品女不卡 | 久久国产成人午夜aⅴ影院| 亚洲一区中文字幕久久| 亚洲国产日韩欧美综合久久| 国产69精品久久久久久人妻精品| 久久国产精品无码一区二区三区| 亚洲国产成人久久笫一页| 亚洲AV成人无码久久精品老人| 久久久久国产一级毛片高清板| 久久综合给久久狠狠97色| 久久无码AV一区二区三区| 久久久久亚洲av成人网人人软件 | 人人狠狠综合久久亚洲88| 久久久亚洲AV波多野结衣| 色综合久久中文综合网| 亚洲国产另类久久久精品小说| 久久免费视频6| 久久综合一区二区无码| 精品久久久久久无码专区| 一本色道久久99一综合| 成人亚洲欧美久久久久| 久久国产成人精品国产成人亚洲| 久久久无码精品亚洲日韩蜜臀浪潮 | 久久精品国产精品青草 | 久久福利资源国产精品999| 精品熟女少妇aⅴ免费久久| 成人久久精品一区二区三区| 久久婷婷国产麻豆91天堂| 久久婷婷五月综合国产尤物app| 精品久久久一二三区| 久久久久亚洲精品日久生情 | 精品久久久久久国产牛牛app| 久久久久久亚洲精品成人| 日日噜噜夜夜狠狠久久丁香五月| 2021国产精品午夜久久| 亚洲精品tv久久久久久久久| 无码AV波多野结衣久久| 精品永久久福利一区二区| 国内精品伊人久久久久|