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

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            HDU 1711 HDOJ 1711 Number Sequence ACM 1711 IN HDU

            Posted on 2010-10-05 14:17 MiYu 閱讀(778) 評論(0)  編輯 收藏 引用 所屬分類: ACM ( 串 )
            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

             

             

            題目地址 :

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

            題目描述:

            代碼
            Number Sequence

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


            Problem Description
            Given two sequences of numbers : a[
            1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 100001 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1= b[2], ...... , a[K + M - 1= b[M]. If there are more than one K exist, output the smallest one.
             

            Input
            The first line of input 
            is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 100001 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-10000001000000].
             

            Output
            For each test 
            case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
             

            Sample Input
            2
            13 5
            1 2 1 2 3 1 2 3 1 3 2 1 2
            1 2 3 1 3
            13 5
            1 2 1 2 3 1 2 3 1 3 2 1 2
            1 2 3 2 1
             

            Sample Output
            6
            -1
             

             

             代碼

            題目分析 :
               很久以前做的一個題目,  純粹的套模板了..... 到現在還是沒明白 KMP 到底怎么回事, 也可能是我沒花時間去仔細的看的原因.

            今天上郵箱發現一個星期前一位網友問我的1711代碼速度為什么那么快, 著到代碼一看, 原來是個 簡單的KMP 裸題, 直接模板就行了,

            速度的話這里有個小技巧, 知道的人就不要笑話我了.  

            其實關鍵就是 對輸入數據的 加速
            !!!!
            一般對數據的輸入都是 
            %d 或 %%lf 對吧?  其實計算機讀取的數據是字符形的, 它也需要調用其他的函數將這個串轉換成
            數字,  所以你只要 用字符串讀入 數據,  然后自己寫個函數 把 這個字符串轉換成 數字久行了.

            其實呢, 很多題目都可以只要來加速的, 除非它的數據量不大.


            下面是我的代碼 : 


            #include 
            <iostream>
            using namespace std;
            const int MAXN=1000000;
            const int MAXM=10000;

            int nn[MAXN+1],mm[MAXM+1];
            int Fail[MAXM+1];

            void GetFail(int num[],int m){
                    Fail[
            0]=-1;
                    
            for(int i=1,j=-1;i<m;i++){
                            
            while(j>=0&&num[j+1]!=num[i]){
                                    j
            =Fail[j];
                            }
                            
            if(num[j+1]==num[i])j ++;
                            Fail[i]
            =j;
                    }
            }
            int KMP(int numA[],int numB[],int n,int m){
                    GetFail ( numB,m );    
                    
            for (int i=0,j=0;i<n;i++){
                            
            while(j&&numB[j]!=numA[i]){
                                    j
            =Fail[j-1]+1;
                            }
                            
            if(numB[j]==numA[i]) j++;
                            
            if(j == m) return i-m+2;
                    }
                    
            return -1;
            }
            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,M,T;
                
            while ( scan_d(T) )
                {
                       
            while ( T -- )
                       {
                              scan_d(N),scan_d(M);
                              
            for ( int i = 0; i != N; ++ i )
                                  scan_d ( nn[i] );
                              
            for ( int j = 0; j != M; ++ j )
                                  scan_d ( mm[j] );    
                              printf ( 
            "%d\n",KMP ( nn,mm,N,M ) );  
                       }
                }
                
            return 0;
            }
            天天综合久久一二三区| 久久久久久精品免费看SSS| 99久久99久久精品免费看蜜桃| 久久亚洲AV成人无码| 亚洲国产精品无码久久一区二区| 久久永久免费人妻精品下载| 久久亚洲国产欧洲精品一| 亚洲国产成人久久综合野外| 亚洲精品乱码久久久久久中文字幕 | 亚洲国产精品成人久久蜜臀 | 2021精品国产综合久久| 久久综合给合综合久久| 久久只有这精品99| 国内精品伊人久久久久AV影院| 久久精品九九亚洲精品天堂 | 国产精品女同久久久久电影院| 99久久精品免费看国产| 久久亚洲AV成人出白浆无码国产 | 亚洲av日韩精品久久久久久a| 久久久久免费精品国产| 午夜人妻久久久久久久久| 久久久久国产精品麻豆AR影院| 久久男人Av资源网站无码软件| 亚洲国产一成久久精品国产成人综合 | 三级片免费观看久久| av无码久久久久不卡免费网站| 色老头网站久久网| 欧美久久一区二区三区| 久久99精品久久久久久野外 | 久久99精品久久久久久齐齐| 精品久久久久久亚洲| 精品久久久噜噜噜久久久 | 91精品国产高清91久久久久久| 狠狠色狠狠色综合久久| 麻豆精品久久久久久久99蜜桃 | 久久亚洲AV成人无码软件| 精品久久人人爽天天玩人人妻| 青青青青久久精品国产h| 精品少妇人妻av无码久久| 久久香综合精品久久伊人| 欧美喷潮久久久XXXXx|