• <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
            <2010年8月>
            25262728293031
            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;
            }

             

             

            久久这里只有精品久久| 亚洲综合久久久| 亚洲嫩草影院久久精品| 国内精品久久久久久久coent| 99久久国产亚洲高清观看2024| 久久久久无码国产精品不卡| 中文字幕人妻色偷偷久久| 久久福利青草精品资源站| 性高湖久久久久久久久AAAAA| 久久AV无码精品人妻糸列| 精品无码人妻久久久久久| 77777亚洲午夜久久多人| 日本免费一区二区久久人人澡| 波多野结衣久久| 久久99精品国产一区二区三区| 麻豆精品久久久久久久99蜜桃| 久久―日本道色综合久久| 久久亚洲中文字幕精品一区| 品成人欧美大片久久国产欧美...| 久久99热这里只有精品国产| 久久国产精品免费一区| 四虎国产精品免费久久久| 国内精品久久久久伊人av| 久久国产劲爆AV内射—百度| 国产—久久香蕉国产线看观看| 久久国产高潮流白浆免费观看| 久久久久久精品免费看SSS | 成人综合伊人五月婷久久| 久久影院久久香蕉国产线看观看| 成人免费网站久久久| 久久婷婷国产综合精品| 久久精品视频一| 久久精品aⅴ无码中文字字幕不卡| 久久久久国色AV免费看图片| 94久久国产乱子伦精品免费| 国产成人精品久久二区二区| 99久久99久久精品国产片果冻 | 国产精品无码久久综合| 色偷偷偷久久伊人大杳蕉| 色妞色综合久久夜夜| 国产69精品久久久久APP下载 |