• <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;
            }

             

             

            久久久这里有精品中文字幕| 久久久久久精品免费看SSS| 少妇熟女久久综合网色欲| 免费精品99久久国产综合精品| 久久精品99久久香蕉国产色戒 | 国内精品欧美久久精品| 狠狠色噜噜狠狠狠狠狠色综合久久| 久久香蕉国产线看观看精品yw| 久久久久久曰本AV免费免费| 久久精品青青草原伊人| 亚洲AV无码久久精品色欲| 丰满少妇高潮惨叫久久久| 日韩欧美亚洲综合久久影院d3| 精品久久香蕉国产线看观看亚洲| 香港aa三级久久三级| 99久久精品免费看国产免费| 精品国产91久久久久久久a| 亚洲人成无码网站久久99热国产| 亚洲国产精品一区二区三区久久| 99蜜桃臀久久久欧美精品网站| 久久久久久人妻无码| 久久综合欧美成人| 亚洲&#228;v永久无码精品天堂久久| 久久久久久久久久免免费精品| 久久精品国产欧美日韩99热| 色偷偷91久久综合噜噜噜噜| 久久精品中文字幕无码绿巨人| 国产精品久久久久影院色| 久久午夜无码鲁丝片午夜精品| 亚洲精品tv久久久久久久久| 久久精品视频网| 2021国产精品久久精品| 午夜不卡久久精品无码免费| 久久99中文字幕久久| 久久91精品久久91综合| 国产日韩欧美久久| 影音先锋女人AV鲁色资源网久久| 91精品国产91久久| 国产99久久久国产精品小说| 久久综合噜噜激激的五月天| 精品综合久久久久久88小说 |