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

            A Za, A Za, Fighting...

            堅信:勤能補拙

            問題:
            http://poj.org/problem?id=1147

            思路:
            這題太精妙了...
            恐怕是到目前為止,最為精妙的了...
            翻了很多網(wǎng)上資料,才想明白,艾,推理能力太差...

            關(guān)鍵點:
            1. 對于排序后的矩陣,每一行都可以通過第一行旋轉(zhuǎn)得到
            2. 假設(shè)矩陣中兩行都以0開始,則它們左旋后,前后次序不變,所以在矩陣中以0開始的第1行,它的左旋后的序列在最后一列的第一個0的行。對1       開始的行有同樣的性質(zhì)
            3. 通過1、2兩點即可確定next數(shù)組,即第一列與最后一列的對應(yīng)關(guān)系
            4. 觀察題目給出的Figure 1,可以看出第一列與最后一列之間的巧妙關(guān)系: b2可以通過找到第一列b1所對應(yīng)的最后一列的所在行而得到

            代碼:
             1 #include<stdio.h>
             2 #include<stdlib.h>
             3 #include<string.h>
             4 #define MAX_LEN 3001
             5 int first_col[MAX_LEN], last_col[MAX_LEN];
             6 int N, zeros, ones, next[MAX_LEN];
             7 
             8 int
             9 main(int argc, char **argv)
            10 {
            11     int i, count;
            12     while(scanf("%d"&N) != EOF) {
            13         zeros = ones = 0;
            14         for(i=1; i<=N; i++) {
            15             scanf("%d", last_col+i);
            16             if(last_col[i] == 0)
            17                 first_col[++zeros] = 0;
            18             else
            19                 ++ones;
            20         }
            21         for(i=1; i<=ones; i++)
            22             first_col[zeros+i] = 1;
            23         ones = zeros+1;
            24         zeros = 1;
            25         for(i=1; i<=N; i++) {
            26             if(last_col[i] == 0)
            27                 next[zeros++= i;
            28             else
            29                 next[ones++= i;
            30         }
            31 
            32         for(count=1, i=1; count<=N; i=next[i], ++count)
            33             printf("%d ", first_col[i]);
            34         printf("\n");
            35     }
            36 }
            posted @ 2010-10-18 18:25 simplyzhao 閱讀(242) | 評論 (0)編輯 收藏
            問題:
            http://poj.org/problem?id=3508

            思路:
            挺簡單的算數(shù)題(注意進(jìn)位),簡化為:
                  abc
                +  abc
                ---------
                     353
            第一次提交居然TLE,汗...
            然后把memset(result, 0, sizeof(result))的代碼刪掉,再適當(dāng)減少些運算,就AC了,860MS

            代碼:
             1 /* 860MS */
             2 #include<stdio.h>
             3 #include<stdlib.h>
             4 #include<string.h>
             5 #define MAX_LEN 1000003
             6 char num[MAX_LEN], result[MAX_LEN];
             7 int len;
             8 
             9 void
            10 solve()
            11 {
            12     int i, mark, minus, tmp;
            13     minus = mark = 0;
            14     for(i=len-1; i>=0; i--) {
            15         minus += mark;
            16         if(minus <= (num[i]-'0')) {
            17             result[i] = num[i] - minus;
            18             mark = 0;
            19         } else {
            20             result[i] = num[i] + 10 - minus;
            21             mark = 1;
            22         }
            23         minus = result[i]-'0';
            24     }
            25     result[len] = '\0';
            26     if(result[0== '0')
            27         printf("IMPOSSIBLE\n");
            28     else
            29         printf("%s\n", result);
            30 }
            31 
            32 int
            33 main(int argc, char **argv)
            34 {
            35     int tests = 0;
            36     while(scanf("%s", num)!=EOF && num[0]!='0') {
            37         len = strlen(num);
            38         printf("%d. "++tests);
            39         solve();
            40     }
            41 }
            posted @ 2010-10-17 20:45 simplyzhao 閱讀(239) | 評論 (0)編輯 收藏
            問題:
            http://poj.org/problem?id=1089

            思路:
            根據(jù)interval的begin升序排列,然后對于interval A, B只存在三種情況:
            A包含B、A與B相交、A與B分離

            代碼:
             1 #include<stdio.h>
             2 #include<stdlib.h>
             3 #include<string.h>
             4 #define MAX_LEN 50001
             5 struct Interval {
             6     int begin, end;
             7 }itvs[MAX_LEN], target[MAX_LEN];
             8 int N, total;
             9 
            10 int
            11 compare(const void *arg1, const void *arg2)
            12 {
            13     struct Interval *= (struct Interval *)arg1;
            14     struct Interval *= (struct Interval *)arg2;
            15     if(a->begin == b->begin)
            16         return a->end - b->end;
            17     return a->begin - b->begin;
            18 }
            19 
            20 void
            21 init()
            22 {
            23     int i;
            24     for(i=0; i<N; i++)
            25         scanf("%d %d"&itvs[i].begin, &itvs[i].end);
            26     qsort(itvs, N, sizeof(struct Interval), compare);
            27     total = 0;
            28 }
            29 
            30 void
            31 solve()
            32 {
            33     int i;
            34     struct Interval cur = itvs[0];
            35     for(i=1; i<N; i++) {
            36         if(itvs[i].begin > cur.end) {
            37             target[total++= cur;
            38             cur = itvs[i];
            39         } else {
            40             if(itvs[i].end > cur.end)
            41                 cur.end = itvs[i].end;
            42         }
            43     }
            44     target[total++= cur;
            45 }
            46 
            47 void
            48 output()
            49 {
            50     int i;
            51     for(i=0; i<total; i++)
            52         printf("%d %d\n", target[i].begin, target[i].end);
            53 }
            54 
            55 int
            56 main(int argc, char **argv)
            57 {
            58     while(scanf("%d"&N) != EOF) {
            59         init();
            60         solve();
            61         output();
            62     }
            63 }
            posted @ 2010-10-17 19:35 simplyzhao 閱讀(207) | 評論 (0)編輯 收藏
            參考:
            http://www.cnblogs.com/coeus/articles/1541722.html

            原理:
            1. 任何一個合數(shù)都可以表示成一個質(zhì)數(shù)和一個數(shù)的乘積
            2. 假設(shè)A是一個合數(shù),且A = x * y,這里x也是一個合數(shù),那么有:
                   A = x * y; (假設(shè)y質(zhì)數(shù),x合數(shù))
                   x = a * b; (假設(shè)a是質(zhì)數(shù),且a < x)
             ->  A = a * b * y = a * Z (Z = b * y)
            即一個合數(shù)(x)與一個質(zhì)數(shù)(y)的乘積可以表示成一個更大的合數(shù)(Z)與一個更小的質(zhì)數(shù)(a)的乘積
            這也是理解代碼中 if(i%primes[j] == 0)break;的關(guān)鍵
            例如: 如果i = 8; 那么由于i%2 == 0; 因此對于i=8就只需要檢查primes[1]即可,因為對于大于primes[1]的質(zhì)數(shù),像3,有:
                    8*3 = 2*4*3 = 12*2
            也就是說24(8*3=24)并不需要在8時檢查,在12時才檢查 

            代碼:
             1 /*
             2  * Problem:
             3  * given an upper bound like U(integer), print all the primes between 0-U
             4  *
             5  * Points:
             6  * this's a O(n) algorithm, amazing
             7  */
             8 #include<stdio.h>
             9 #include<stdlib.h>
            10 #include<string.h>
            11 #define MAX_N 250000
            12 int N, hash[MAX_N];
            13 int pcount, primes[MAX_N];
            14 
            15 void
            16 linear_selection()
            17 {
            18     int i, j;
            19     primes[pcount++= 1;
            20     for(i=2; i<=N; i++) {
            21         if(!hash[i])
            22             primes[pcount++= i;
            23         for(j=1; j<pcount && i*primes[j]<=N; j++) {
            24             hash[i*primes[j]] = 1;
            25             if(i%primes[j] == 0)
            26                 break;
            27         }
            28     }
            29 }
            30 
            31 int
            32 main(int argc, char **argv)
            33 {
            34     int i;
            35     while(1) {
            36         printf("Enter the upper boundary: ");
            37         scanf("%d"&N);
            38         if(!N)
            39             break;
            40         memset(hash, 0sizeof(hash));
            41         pcount = 0;
            42         linear_selection();
            43         for(i=0; i<pcount; i++)
            44             printf("%d\n", primes[i]);
            45     }
            46 }
            posted @ 2010-10-17 18:19 simplyzhao 閱讀(355) | 評論 (0)編輯 收藏
            問題:
            http://poj.org/problem?id=3051

            思路:
            還是教科書式的DFS典型應(yīng)用,簡單題

            代碼:
             1 #include<stdio.h>
             2 #include<stdlib.h>
             3 #include<string.h>
             4 #define MAX_W 83
             5 #define MAX_H 1001
             6 #define is_valid(x,y) (x>=0 && x<H && y>=0 && y<W)
             7 const int dx[] = {-1100};
             8 const int dy[] = {00-11};
             9 char photo[MAX_H][MAX_W];
            10 int hash[MAX_H][MAX_W];
            11 int W, H;
            12 
            13 int
            14 dfs(int x, int y)
            15 {
            16     int i, nx, ny, rt = 1;
            17     hash[x][y] = 1;
            18     for(i=0; i<4; i++) {
            19         nx = x+dx[i];
            20         ny = y+dy[i];
            21         if(is_valid(nx, ny) && photo[nx][ny]=='*' && !hash[nx][ny]) 
            22             rt += dfs(nx, ny);
            23     }
            24     return rt;
            25 }
            26 
            27 int
            28 solve()
            29 {
            30     int i, j, tmp, value = -1;
            31     for(i=0; i<H; i++)
            32         for(j=0; j<W; j++) {
            33             if(photo[i][j]=='*' && !hash[i][j]) {
            34                 tmp = dfs(i, j);
            35                 value = tmp > value ? tmp : value;
            36             }
            37         }
            38     return value;
            39 }
            40 
            41 int
            42 main(int argc, char **argv)
            43 {
            44     int i;
            45     while(scanf("%d %d"&W, &H) != EOF) {
            46         for(i=0; i<H; i++)
            47             scanf("%s", photo[i]);
            48         memset(hash, 0sizeof(hash));
            49         printf("%d\n", solve());
            50     }
            51 }
            posted @ 2010-10-17 13:13 simplyzhao 閱讀(191) | 評論 (0)編輯 收藏
            問題:
            http://poj.org/problem?id=1573

            思路:
            簡單題,純模擬...

            代碼:
             1 #include<stdio.h>
             2 #include<stdlib.h>
             3 #include<string.h>
             4 #define MAX_LEN 12
             5 #define is_valid(x, y) (x>=0 && x<R && y>=0 && y<C)
             6 char map[MAX_LEN][MAX_LEN];
             7 int steps[MAX_LEN][MAX_LEN];
             8 int R, C, entry;
             9 
            10 void
            11 solve()
            12 {
            13     char ch;
            14     int cx, cy, px, py;
            15     cx = px = 0;
            16     cy = py = entry-1;
            17     while(is_valid(cx, cy) && !steps[cx][cy]) {
            18         steps[cx][cy] = steps[px][py] + 1;
            19         ch = map[cx][cy];
            20         px = cx;
            21         py = cy;
            22         switch(ch) {
            23             case 'N':
            24                 cx = px-1;
            25                 cy = py;
            26                 break;
            27             case 'S':
            28                 cx = px+1;
            29                 cy = py;
            30                 break;
            31             case 'W':
            32                 cx = px;
            33                 cy = py-1;
            34                 break;
            35             case 'E':
            36                 cx = px;
            37                 cy = py+1;
            38                 break;
            39         }
            40     }
            41     if(!is_valid(cx, cy))
            42         printf("%d step(s) to exit\n", steps[px][py]);
            43     else if(steps[cx][cy])
            44         printf("%d step(s) before a loop of %d step(s)\n", steps[cx][cy]-1, steps[px][py]-steps[cx][cy]+1);
            45 }
            46 
            47 int
            48 main(int argc, char **argv)
            49 {
            50     int i;
            51     while(scanf("%d %d %d"&R, &C, &entry)!=EOF && R) {
            52         for(i=0; i<R; i++)
            53             scanf("%s", map[i]);
            54         memset(steps, 0sizeof(steps));
            55         solve();
            56     }
            57 }
            posted @ 2010-10-17 11:12 simplyzhao 閱讀(140) | 評論 (0)編輯 收藏
            問題:
            http://poj.org/problem?id=1154

            思路:
            教科書式的DFS,一次AC

            代碼:
             1 #include<stdio.h>
             2 #include<stdlib.h>
             3 #include<string.h>
             4 #define MAX_LEN 21
             5 #define is_valid(x, y) (x>=0&&x<R&&y>=0&&y<C)
             6 const int dx[] = {-1100};
             7 const int dy[] = {00-11};
             8 int R, C;
             9 int rt, hash[26]; /* A-Z */
            10 char map[MAX_LEN][MAX_LEN];
            11 
            12 void
            13 dfs(int x, int y, int cur)
            14 {
            15     int i, mark, next_x, next_y;
            16     mark = 0;
            17     hash[map[x][y]] = 1;
            18     for(i=0; i<4; i++) {
            19         next_x = x + dx[i];
            20         next_y = y + dy[i];
            21         if(is_valid(next_x, next_y) && !hash[map[next_x][next_y]]) {
            22             mark = 1;
            23             hash[map[next_x][next_y]] = 1;
            24             dfs(next_x, next_y, cur+1);
            25             hash[map[next_x][next_y]] = 0;
            26         }
            27     }
            28     if(!mark)
            29         rt = cur>rt ? cur : rt;
            30 }
            31 
            32 int
            33 main(int argc, char **argv)
            34 {
            35     int i;
            36     while(scanf("%d %d"&R, &C) != EOF) {
            37         for(i=0; i<R; i++)
            38             scanf("%s", map[i]);
            39         rt = -1;
            40         memset(hash, 0sizeof(hash));
            41         dfs(001);
            42         printf("%d\n", rt);
            43     }
            44 }
            posted @ 2010-10-17 01:19 simplyzhao 閱讀(209) | 評論 (0)編輯 收藏
            問題:
            http://ace.delos.com/usacoprob2?a=CTINrbaHwEW&S=packrec

            思路:
            這題不會,考慮的時候以為任意兩個矩陣至少存在相同的邊才可以合并...結(jié)果完全錯誤

            參考:
            http://starforever.blog.hexun.com/2097115_d.html
            http://greenmoon55.com/usaco-packing-rectangles/

            另外,這題學(xué)會了在C里面使用bool類型,原來不知道呢(*^__^*) 嘻嘻……
            stdbool.h頭文件

            代碼:
              1 /*
              2 ID: simplyz2
              3 LANG: C
              4 TASK: packrec
              5 */
              6 #include<stdio.h>
              7 #include<stdbool.h>
              8 #include<stdlib.h>
              9 #include<string.h>
             10 #define MAX_NUM 5
             11 #define INF 0x7FFFFFFF
             12 #define Max(a, b) ((a)>(b) ? (a) : (b))
             13 struct Rec {
             14     int h, w;
             15 } rectangle[MAX_NUM], rect[MAX_NUM], ans[MAX_NUM];
             16 bool used[MAX_NUM];
             17 int w, h, total, area;
             18 
             19 void
             20 exchange(struct Rec *r)
             21 {
             22     int temp = r->h;
             23     r->= r->w;
             24     r->= temp;
             25 }
             26 
             27 void
             28 judge()
             29 {
             30     int i, j, temp;
             31     if(w > h) {
             32         temp = w;
             33         w = h;
             34         h = temp;
             35     }
             36     if(w*<= area) {
             37         if(w*== area) {
             38             for(i=1; i<total; i++)
             39                 if(ans[i].w == w)
             40                     return;
             41             for(i=1; i<total; i++)
             42                 if(ans[i].w > w) {
             43                     for(j=total; j>i; j--)
             44                         ans[j] = ans[j-1];
             45                     ans[i].w = w;
             46                     ans[i].h = h;
             47                     ++total;
             48                     return;
             49                 }
             50             ans[total].w = w;
             51             ans[total++].h = h;
             52         } else {
             53             area = w*h;
             54             total = 1;
             55             ans[total].w = w;
             56             ans[total].h = h;
             57         }
             58     }
             59 }
             60 
             61 void
             62 work()
             63 {   
             64     //Case 1
             65     w=rect[1].w+rect[2].w+rect[3].w+rect[4].w;
             66     h=Max(rect[1].h,rect[2].h);
             67     h=Max(h,rect[3].h);
             68     h=Max(h,rect[4].h);
             69     judge();
             70  
             71     //Case 2
             72     w=Max(rect[1].w+rect[2].w+rect[3].w,rect[4].w);
             73     h=Max(rect[1].h,rect[2].h);
             74     h=Max(h,rect[3].h);
             75     h+=rect[4].h;
             76     judge();
             77  
             78     //Case 3
             79     w=Max(rect[1].w+rect[2].w,rect[3].w)+rect[4].w;
             80     h=Max(Max(rect[1].h,rect[2].h)+rect[3].h,rect[4].h);
             81     judge();
             82  
             83     //Case 4
             84     w=rect[1].w+Max(rect[2].w,rect[3].w)+rect[4].w;
             85     h=Max(rect[1].h,rect[4].h);
             86     h=Max(h,rect[2].h+rect[3].h);
             87     judge();
             88  
             89     //Case 6
             90     if (rect[3].h>=rect[2].h+rect[4].h)
             91     {
             92         w=Max(rect[3].w+rect[2].w,rect[3].w+rect[4].w);
             93         w=Max(w,rect[1].w);
             94         h=rect[1].h+rect[3].h;
             95         judge();
             96         return;
             97     }
             98     if (rect[3].h>rect[4].h)
             99     {
            100         w=Max(rect[1].w+rect[2].w,rect[2].w+rect[3].w);
            101         w=Max(w,rect[4].w+rect[3].w); 
            102         h=Max(rect[1].h+rect[3].h,rect[2].h+rect[4].h);
            103         judge();
            104         return;
            105     }
            106     if (rect[3].h==rect[4].h)
            107     {
            108         w=Max(rect[1].w+rect[2].w,rect[3].w+rect[4].w);
            109         h=Max(rect[1].h,rect[2].h)+rect[3].h;
            110         judge();
            111         return;
            112     }
            113     if (rect[3].h<rect[4].h && rect[4].h<rect[3].h+rect[1].h)
            114     {
            115         w=Max(rect[1].w+rect[2].w,rect[1].w+rect[4].w);
            116         w=Max(w,rect[3].w+rect[4].w);
            117         h=Max(rect[1].h+rect[3].h,rect[2].h+rect[4].h);
            118         judge();
            119         return;
            120     }
            121     w=Max(rect[2].w,rect[1].w+rect[4].w);
            122     w=Max(w,rect[3].w+rect[4].w);
            123     h=rect[4].h+rect[2].h;
            124     judge(); 
            125 }
            126 
            127 void
            128 rotate(int depth)
            129 {
            130     if(depth == MAX_NUM) {
            131         work();
            132         return;
            133     }
            134     rotate(depth+1);
            135     exchange(rect+depth);
            136     rotate(depth+1);
            137 }
            138 
            139 void
            140 dfs(int depth)
            141 {
            142     int i;
            143     if(depth == MAX_NUM) {
            144         rotate(1);
            145         return;
            146     }
            147     for(i=1; i<MAX_NUM; i++) {
            148         if(!used[i]) {
            149             used[i] = true;
            150             rect[depth] = rectangle[i];
            151             dfs(depth+1);
            152             used[i] = false;
            153         }
            154     }
            155 }
            156 
            157 int
            158 main(int argc, char **argv)
            159 {
            160     int i;
            161     freopen("packrec.in""r", stdin);
            162     freopen("packrec.out""w", stdout);
            163     for(i=1; i<MAX_NUM; i++)
            164         scanf("%d %d"&rectangle[i].w, &rectangle[i].h);
            165     total = 1;
            166     area = INF;
            167     memset(used, 0sizeof(used));
            168     dfs(1);
            169     printf("%d\n", area);
            170     for(i=1; i<total; i++)
            171         printf("%d %d\n", ans[i].w, ans[i].h);
            172     return 0;
            173 }
            posted @ 2010-10-13 19:45 simplyzhao 閱讀(392) | 評論 (0)編輯 收藏
            出處:
            http://ace.delos.com/usacotext2?a=4odBE1tA7sS&S=rec

            Sample Problem: n Queens [Traditional]

            Place n queens on an n x n chess board so that no queen is attacked by another queen.

            Depth First Search (DFS)

            The most obvious solution to code is to add queens recursively to the board one by one, trying all possible queen placements. It is easy to exploit the fact that there must be exactly one queen in each column: at each step in the recursion, just choose where in the current column to put the queen. 

             1 search(col)
             2     if filled all columns
             3         print solution and exit 

             4   for each row
             5       if board(row, col) is not attacked
             6            place queen at (row, col)
             7            search(col+1)
             8            remove queen at (row, col)

            Calling search(0) begins the search. This runs quickly, since there are relatively few choices at each step: once a few queens are on the board, the number of non-attacked squares goes down dramatically.

            This is an example of depth first search, because the algorithm iterates down to the bottom of the search tree as quickly as possible: once k queens are placed on the board, boards with even more queens are examined before examining other possible boards with only k queens. This is okay but sometimes it is desirable to find the simplest solutions before trying more complex ones.

            Depth first search checks each node in a search tree for some property. The search tree might look like this: 

            The algorithm searches the tree by going down as far as possible and then backtracking when necessary, making a sort of outline of the tree as the nodes are visited. Pictorially, the tree is traversed in the following manner: 

            Complexity

            Suppose there are d decisions that must be made. (In this case d=n, the number of columns we must fill.) Suppose further that there are C choices for each decision. (In this case c=n also, since any of the rows could potentially be chosen.) Then the entire search will take time proportional to cd, i.e., an exponential amount of time. This scheme requires little space, though: since it only keeps track of as many decisions as there are to make, it requires only O(d) space.

            Sample Problem: Knight Cover [Traditional]

            Place as few knights as possible on an n x n chess board so that every square is attacked. A knight is not considered to attack the square on which it sits.

            Breadth First Search (BFS)

            In this case, it is desirable to try all the solutions with only k knights before moving on to those with k+1 knights. This is called breadth first search. The usual way to implement breadth first search is to use a queue of states: 

             1 process(state)
             2     for each possible next state from this one
             3         enqueue next state 

             4 search()
             5     enqueue initial state
             6     while !empty(queue)
             7         state = get state from queue
             8         process(state)

            This is called breadth first search because it searches an entire row (the breadth) of the search tree before moving on to the next row. For the search tree used previously, breadth first search visits the nodes in this order: 

            It first visits the top node, then all the nodes at level 1, then all at level 2, and so on.

            Complexity

            Whereas depth first search required space proportional to the number of decisions (there were n columns to fill in the n queens problem, so it took O(n) space), breadth first search requires space exponential in the number of choices.

            If there are c choices at each decision and k decisions have been made, then there are ck possible boards that will be in the queue for the next round. This difference is quite significant given the space restrictions of some programming environments.

            [Some details on why ck: Consider the nodes in the recursion tree. The zeroeth level has 1 nodes. The first level has c nodes. The second level has c2 nodes, etc. Thus, the total number of nodes on the k-th level is ck.]

            Depth First with Iterative Deepening (ID)

            An alternative to breadth first search is iterative deepening. Instead of a single breadth first search, run D depth first searches in succession, each search allowed to go one row deeper than the previous one. That is, the first search is allowed only to explore to row 1, the second to row 2, and so on. This ``simulates'' a breadth first search at a cost in time but a savings in space. 

             1 truncated_dfsearch(hnextpos, depth)
             2     if board is covered
             3         print solution and exit 

             4     if depth == 0
             5         return 

             6     for i from nextpos to n*n
             7         put knight at i
             8         truncated_dfsearch(i+1, depth-1)
             9         remove knight at i 

            10 dfid_search
            11     for depth = 0 to max_depth
            12        truncated_dfsearch(0, depth)

            Complexity

            The space complexity of iterative deepening is just the space complexity of depth first search: O(n). The time complexity, on the other hand, is more complex. Each truncated depth first search stopped at depth k takes ck time. Then if d is the maximum number of decisions, depth first iterative deepening takes c0 + c1 + c2 + ... + cd time.

            If c = 2, then this sum is cd+1 - 1, about twice the time that breadth first search would have taken. When c is more than two (i.e., when there are many choices for each decision), the sum is even less: iterative deepening cannot take more than twice the time that breadth first search would have taken, assuming there are always at least two choices for each decision.

            Which to Use?

            Once you've identified a problem as a search problem, it's important to choose the right type of search. Here are some things to think about.

            In a Nutshell
            SearchTimeSpaceWhen to use
            DFSO(ck)O(k)Must search tree anyway, know the level the answers are on, or you aren't looking for the shallowest number.
            BFSO(cd)O(cd)Know answers are very near top of tree, or want shallowest answer.
            DFS+IDO(cd)O(d)Want to do BFS, don't have enough space, and can spare the time.
            d is the depth of the answer 
            k is the depth searched 
            d <= k

            Remember the ordering properties of each search. If the program needs to produce a list sorted shortest solution first (in terms of distance from the root node), use breadth first search or iterative deepening. For other orders, depth first search is the right strategy.

            If there isn't enough time to search the entire tree, use the algorithm that is more likely to find the answer. If the answer is expected to be in one of the rows of nodes closest to the root, use breadth first search or iterative deepening. Conversely, if the answer is expected to be in the leaves, use the simpler depth first search.

            Be sure to keep space constraints in mind. If memory is insufficient to maintain the queue for breadth first search but time is available, use iterative deepening.

            Sample Problems

            Superprime Rib [USACO 1994 Final Round, adapted]

            A number is called superprime if it is prime and every number obtained by chopping some number of digits from the right side of the decimal expansion is prime. For example, 233 is a superprime, because 233, 23, and 2 are all prime. Print a list of all the superprime numbers of length n, for n <= 9. The number 1 is not a prime.

            For this problem, use depth first search, since all the answers are going to be at the nth level (the bottom level) of the search.

            Betsy's Tour [USACO 1995 Qualifying Round]

            A square township has been partitioned into 2 square plots. The Farm is located in the upper left plot and the Market is located in the lower left plot. Betsy takes a tour of the township going from Farm to Market by walking through every plot exactly once. Write a program that will count how many unique tours Betsy can take in going from Farm to Market for any value of n <= 6.

            Since the number of solutions is required, the entire tree must be searched, even if one solution is found quickly. So it doesn't matter from a time perspective whether DFS or BFS is used. Since DFS takes less space, it is the search of choice for this problem.

            Udder Travel [USACO 1995 Final Round; Piele]

            The Udder Travel cow transport company is based at farm A and owns one cow truck which it uses to pick up and deliver cows between seven farms A, B, C, D, E, F, and G. The (commutative) distances between farms are given by an array. Every morning, Udder Travel has to decide, given a set of cow moving orders, the order in which to pick up and deliver cows to minimize the total distance traveled. Here are the rules:

            • The truck always starts from the headquarters at farm A and must return there when the day's deliveries are done.
            • The truck can only carry one cow at a time.
            • The orders are given as pairs of letters denoting where a cow is to be picked up followed by where the cow is to be delivered.

            Your job is to write a program that, given any set of orders, determines the shortest route that takes care of all the deliveries, while starting and ending at farm A.

            Since all possibilities must be tried in order to ensure the best one is found, the entire tree must be searched, which takes the same amount of time whether using DFS or BFS. Since DFS uses much less space and is conceptually easier to implement, use that.

            Desert Crossing [1992 IOI, adapted]

            A group of desert nomads is working together to try to get one of their group across the desert. Each nomad can carry a certain number of quarts of water, and each nomad drinks a certain amount of water per day, but the nomads can carry differing amounts of water, and require different amounts of water. Given the carrying capacity and drinking requirements of each nomad, find the minimum number of nomads required to get at least one nomad across the desert.

            All the nomads must survive, so every nomad that starts out must either turn back at some point, carrying enough water to get back to the start or must reach the other side of the desert. However, if a nomad has surplus water when it is time to turn back, the water can be given to their friends, if their friends can carry it.

            Analysis: This problem actually is two recursive problems: one recursing on the set of nomads to use, the other on when the nomads turn back. Depth-first search with iterative deepening works well here to determine the nomads required, trying first if any one can make it across by themselves, then seeing if two work together to get across, etc.

            Addition Chains

            An addition chain is a sequence of integers such that the first number is 1, and every subsequent number is the sum of some two (not necessarily unique) numbers that appear in the list before it. For example, 1 2 3 5 is such a chain, as 2 is 1+1, 3 is 2+1, and 5 is 2+3. Find the minimum length chain that ends with a given number.

            Analysis: Depth-first search with iterative deepening works well here, as DFS has a tendency to first try 1 2 3 4 5 ... n, which is really bad and the queue grows too large very quickly for BFS.


            posted @ 2010-10-10 10:58 simplyzhao 閱讀(267) | 評論 (0)編輯 收藏
            問題:
            http://ace.delos.com/usacoprob2?a=NAqufR1Vt6H&S=calfflac

            思路:
            不是很難,枚舉,但需要注意很多細(xì)節(jié)
            另外,要注意存在奇數(shù)與偶數(shù)長度的回文這兩種情況
            完全參考ANALYSIS,學(xué)習(xí)到很多純指針操作字符串的寫法

            代碼:
             1 /*
             2 ID: simplyz2
             3 LANG: C
             4 TASK: calfflac
             5 */
             6 #include<stdio.h>
             7 #include<stdlib.h>
             8 #include<string.h>
             9 #include<assert.h> /* void assert(int exp); */
            10 #include<ctype.h>
            11 #define MAX_LEN 21000
            12 char text[MAX_LEN], fulltext[MAX_LEN];
            13 char *pal;
            14 int pallen;
            15 
            16 void
            17 solve()
            18 {
            19     int len;
            20     char *fwd, *bkwd, *end, *p;
            21     pallen = 0;
            22     end = text + strlen(text);
            23     for(p=text; *p; p++) {
            24         for(fwd=p, bkwd=p; fwd<end && bkwd>=text && *fwd==*bkwd; fwd++, bkwd--); /* odd: middle, such as 'aba' */
            25         bkwd++;
            26         len = fwd - bkwd;
            27         if(len > pallen) {
            28             pallen = len;
            29             pal = bkwd;
            30         }
            31         for(fwd=p+1, bkwd=p; fwd<end && bkwd>=text && *fwd==*bkwd; fwd++, bkwd--); /* even: left middle, such as 'abba' */
            32         bkwd++;
            33         len = fwd - bkwd;
            34         if(len > pallen) {
            35             pallen = len;
            36             pal = bkwd;
            37         }
            38     }
            39 }
            40 
            41 void
            42 output()
            43 {
            44     int i, n;
            45     char *p; 
            46     n = pal - text;
            47     printf("%d\n", pallen);
            48     for(i=0, p=fulltext; *p; p++) {
            49         if(isalpha(*p))
            50             ++i;
            51         if(i > n)
            52             break;
            53     }
            54     for(i=0; i<pallen && *p; p++) {
            55         fputc(*p, stdout);
            56         if(isalpha(*p))
            57             ++i;
            58     }
            59     printf("\n");
            60 }
            61 
            62 int
            63 main(int argc, char **argv)
            64 {
            65     char *p, *q;
            66     int c;
            67     freopen("calfflac.in""r", stdin);
            68     freopen("calfflac.out""w", stdout);
            69     p = fulltext;
            70     q = text;
            71     while((c=getc(stdin)) != EOF) { /* operation on each char */
            72         if(isalpha(c))
            73             *q++ = tolower(c); 
            74         /* '++''s priority is higher than '*', and '++' first return 'p', than move the pointer forward */
            75         *p++ = c;
            76     }
            77     *= '\0';
            78     *= '\0';
            79     solve();
            80     output();
            81     return 0;
            82 }
            posted @ 2010-10-09 17:05 simplyzhao 閱讀(200) | 評論 (0)編輯 收藏
            僅列出標(biāo)題
            共21頁: First 6 7 8 9 10 11 12 13 14 Last 

            導(dǎo)航

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久亚洲精品无码蜜桃| 久久精品一区二区| 久久丝袜精品中文字幕| 国产精品欧美久久久久无广告| 精品国产热久久久福利| 久久久久99这里有精品10| 国产精品一区二区久久不卡| 亚洲午夜久久久精品影院| 久久久久久午夜精品| 亚洲成人精品久久| 久久久久se色偷偷亚洲精品av | 久久综合亚洲色一区二区三区| 97精品国产97久久久久久免费| 国产精品久久久久久搜索| 青青草原综合久久大伊人导航| 久久久久亚洲AV无码网站| 久久人人爽人爽人人爽av| 久久中文字幕一区二区| 久久久久久久久久久| 久久av高潮av无码av喷吹| 2021久久国自产拍精品| 99蜜桃臀久久久欧美精品网站| 精品人妻伦一二三区久久| 97久久国产亚洲精品超碰热| 国产精品成人久久久| 亚洲国产精品综合久久网络| 亚洲国产精品热久久| 成人久久综合网| 久久久久无码精品国产不卡| 狠狠综合久久综合88亚洲| 香蕉久久夜色精品国产2020| 成人午夜精品久久久久久久小说 | 麻豆精品久久久一区二区| 国产亚洲美女精品久久久久狼| 久久香综合精品久久伊人| 亚洲中文字幕无码一久久区| 久久久SS麻豆欧美国产日韩| 囯产精品久久久久久久久蜜桃| 99久久精品免费看国产一区二区三区 | 久久精品国产亚洲Aⅴ香蕉| 精品久久久久久亚洲|