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

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594
            這套還行,稍有點小水

            1. 遞推數列
                典型的矩陣應用啊~POJ挺多道這種題的
                又NC地調試語句忘擦掉就交。。
            //2009年清華大學計算機研究生機試真題 遞推數列

            #include
            <stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #define N 10000

            typedef 
            int M[2][2];

            M c, mtx;

            void copy(M x, M y) {
                
            for(int i = 0; i < 2++i)
                    
            for(int j = 0; j < 2++j)
                        x[i][j] 
            = y[i][j];
            }


            void AC(M x, M y) {
                M z;
                
            int i, j, k, t;
                
            for(i = 0; i < 2++ i)
                    
            for(j = 0; j < 2++j) {
                        t 
            = 0;
                        
            for(k = 0; k < 2++k)
                            
            if(x[i][k] && y[k][j]) {
                                t 
            = (t + (x[i][k] % N) * (y[k][j] % N)) % N;
                            }

                        z[i][j] 
            = t;
                    }

                copy(x, z);
            }


            void Cal(int k) {
                
            if(k == 1{
                    copy(mtx, c);
                    
            return;
                }

                Cal(k 
            >> 1);
                AC(mtx, mtx);
                
            if(k & 1) AC(mtx, c);
            }


            int main() {
                
            int a0, a1, p, q, k, ans;
                
            while(~scanf("%d %d %d %d %d"&a0, &a1, &p, &q, &k)) {
                    
            if(!k) {
                        printf(
            "%d\n", a0 % N);
                    }

                    
            else if(k == 1{
                        printf(
            "%d\n", a1 % N);
                    }

                    
            else {
                        c[
            0][0= p; c[0][1= q;
                        c[
            1][0= 1; c[1][1= 0;
                        Cal(k 
            - 1);
                        a0 
            %= N; a1 %= N;
                        ans 
            = (mtx[0][0* a1 +  mtx[0][1* a0) % N;
                        printf(
            "%d\n", ans);
                    }

                }

                
            return 0;
            }


            2. 代理服務器
                一開始理解錯題意了,其實是很水很暴力的貪心,因為訪問順序是一定的,所以只要每次找出可以訪問的服務器最多的那個代理服務器就行
            //2009年清華大學計算機研究生機試題 代理服務器
            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>

            int n, m, cnt;
            char nIP[1010][16], mIP[5010][16];

            int main() {
                
            int i, j, np, mp, mx, time;
                
            while(~scanf("%d"&n)) {
                    
            for(i = 0; i < n; ++i) scanf("%s", nIP[i]);
                    scanf(
            "%d"&m);
                    
            for(i = 0; i < m; ++i) scanf("%s", mIP[i]);
                    np 
            = mp = time = 0;
                    
            while(mp < m) {
                        mx 
            = 0;
                        
            for(i = 0; i < n; ++i) {
                            cnt 
            = 0;
                            
            for(j = mp; j < m; ++j) 
                                
            if(strcmp(nIP[i], mIP[j])) cnt++;
                                
            else
                                    
            break;
                            }

                            
            if(cnt > mx) {
                                mx 
            = cnt;
                                np 
            = i;
                            }

                        }

                        
            if(!mx) break;
                        time
            ++;
                        mp 
            += mx;
                    }

                    
            if(!mx) {
                        puts(
            "-1");
                    }

                    
            else
                        printf(
            "%d\n", time - 1);
                }

                
            return 0;
            }

            Feedback

            # re: 清華大學計算機研究生機試題-2009年[未登錄]  回復  更多評論   

            2012-02-09 15:29 by lee
            LZ,很高興看到你的博客。對于第一題遞推數列,能夠解釋一下什么情況下是典型的矩陣應用呢?

            # re: 清華大學計算機研究生機試題-2009年  回復  更多評論   

            2012-02-09 17:56 by Uriel
            @lee
            矩陣是用來加速運算的,像這種遞推式,直接算的話復雜度O(n),用矩陣做的話就可以降到log級別。。
            主要是一些能構造出轉移矩陣,轉化為矩陣連乘的題,

            # re: 清華大學計算機研究生機試題-2009年  回復  更多評論   

            2012-03-27 16:15 by Bice
            @Uriel
            能勞煩解釋一下第一個程序嗎,太深奧了看不懂 啊

            # re: 清華大學計算機研究生機試題-2009年  回復  更多評論   

            2012-03-27 16:28 by Uriel
            @Bice
            這。。幾句話說不清楚。。
            大致過程就是找遞推式,構造轉移矩陣,然后求第N項就化為矩陣連乘問題
            ps:ACM常見題。。,網上有N多介紹

            # re: 清華大學計算機研究生機試題-2009年  回復  更多評論   

            2012-03-27 17:56 by Johnnyao
            請問,對于第一題的題意,難道是我理解錯了嗎,遞推式不是已經在題目中給出了嗎?能否講解一下題意
            http://ac.jobdu.com/problem.php?id=1081

            # re: 清華大學計算機研究生機試題-2009年  回復  更多評論   

            2012-03-27 18:08 by Uriel
            @Johnnyao
            是給了啊,所以這題只要構造轉移矩陣就行了,像這題的話轉移矩陣就是
            [p q]
            [1 0]
            計算過程就是
            [p q] ^ k - 1 [a1]
            [1 0] * [a0]
            久久精品人人做人人爽97| 99久久免费国产精精品| 色婷婷狠狠久久综合五月| 久久亚洲国产成人影院网站| 狠狠精品久久久无码中文字幕 | 久久精品国产亚洲综合色| 国产精品亚洲综合专区片高清久久久| 青青草原综合久久大伊人导航| 伊人久久大香线焦AV综合影院| 中文字幕一区二区三区久久网站| 亚洲一级Av无码毛片久久精品| 91久久精一区二区三区大全| 一本大道久久香蕉成人网| 91精品国产91久久久久福利| 久久久久久久久久久精品尤物| 亚洲伊人久久大香线蕉苏妲己| 国产A三级久久精品| 久久久久亚洲av毛片大| 国产精品久久自在自线观看| 久久午夜夜伦鲁鲁片免费无码影视| 亚洲国产精品久久久久网站 | 99久久免费国产特黄| 久久亚洲AV无码精品色午夜 | 精品久久久久久国产| 久久久久久精品免费看SSS| 久久国产热这里只有精品| 久久99国产精品久久| 国产99精品久久| 狠狠色噜噜狠狠狠狠狠色综合久久| 亚洲AV日韩AV天堂久久| 7777久久久国产精品消防器材| 欧美国产成人久久精品| 久久综合久久鬼色| 色99久久久久高潮综合影院| 青青久久精品国产免费看| 亚洲国产成人乱码精品女人久久久不卡| 国产ww久久久久久久久久| 国内精品久久久久久久涩爱 | 久久99国产精一区二区三区| 97久久超碰国产精品2021| 久久国产免费观看精品|