终于做到第三章了。

3.1开始是最小生成树的介绍文章，给出了Prim算法的伪代码（写的挺好）。之后有6个题目，其实只有第一个题目和最小生成树有关- -。

 

Agri-Net：裸最小生成树。

1 # include 
      
        2  3  4 int ans, n, INF = 0x0f0f0f0f ; 5 int g[110][110] ; 6 int intree[110], d[110] ; 7  8  9 void mst()10 {11     int ts, pos, i, treecost ;12     ans = -1 ;13     for (i = 0 ; i < n ; i++)14         d[i] = INF, intree[i] = 0 ;15     ts = 1 ;16     treecost = 0 ;17     intree[0] = 1 ;18     for (i = 0 ; i < n ; i++) d[i] = g[0][i] ;19     while (ts < n)20     {21         pos = -1 ;22         for (i = 0 ; i < n ; i++) if (intree[i]==0)23             if (pos == -1 || d[pos] > d[i]) pos = i ;24         if (pos == -1) return ;25         ts ++ ;26         treecost += d[pos] ;27         intree[pos] = 1 ;28         for (i = 0 ; i < n ; i++) if (intree[i] == 0)29             if (d[i] > g[pos][i]) d[i] = g[pos][i] ;30     }31     ans = treecost ;32 }33 34 35 int main ()36 {37     int i, j ;38     freopen ("agrinet.in", "r", stdin) ;39     freopen ("agrinet.out", "w", stdout) ;40     while (~scanf ("%d", &n))41     {42         for (i = 0 ; i < n ; i++)43             for (j = 0 ; j < n ; j++)44                 scanf ("%d", &g[i][j]) ;45         mst () ;46         printf ("%d\n", ans) ;47     }48     return 0 ;49 }
      

 

Score Inflation：裸完全背包。

1 # include 
      
        2  3  4 int dp[10010] ; 5  6  7 int main () 8 { 9     int n, m, v, w, i ;10     freopen ("inflate.in", "r", stdin) ;11     freopen ("inflate.out", "w", stdout) ;12     while (~scanf ("%d%d", &m, &n))13     {14         for (i = 0 ; i <= m ; i++) dp[i] = 0 ;15         while (n--)16         {17             scanf ("%d%d", &v, &w) ;18             for (i = w ; i <= m ; i++)19                 if (dp[i]
      

 

Humble Numbers：经典dp！很多OJ上都有这题！

1 # include 
      
        2  3  4 int p[110], idx[110] ; 5 int humble[100010] = {
    1} ; 6  7  8 int main() 9 {10     int n, k, i, j, pos ;11     freopen ("humble.in", "r", stdin) ;12     freopen ("humble.out", "w", stdout) ;13     while (~scanf ("%d%d", &k, &n))14     {15         for (i = 0 ; i < k ; i++)16             scanf ("%d", &p[i]), idx[i] = 0 ;17         for (i = 1 ; i <= n ; i++)18         {19             pos = 0 ;20             for (j = 1 ; j < k ; j++)21                 if (p[j]*humble[idx[j]] < p[pos]*humble[idx[pos]]) pos = j ;22             humble[i] = p[pos]*humble[idx[pos]] ;23             for (j = 0 ; j < k ; j++)24                 if (p[j]*humble[idx[j]] == humble[i]) idx[j]++ ;25         }26         printf ("%d\n", humble[n]) ;27     }28     return 0 ;29 }
      

 

Shaping Regions：麻烦题。可可教了一个递归的方法，还挺快，不过感觉复杂度无从分析。。。

1 # include 
      
        2 # include 
       
         3  4  5 int x1[1010], y1[1010], x2[1010], y2[1010], color[1010] ; 6 int col_hash[3000], n ; 7  8  9 int min(int a, int b){
    return a
        
         b?a:b;}11 12 13 int dfs(int a, int b, int c, int d, int idx)14 {15     int i, j, ans = 0 ;16 //    printf ("%d,%d,%d,%d,%d\n", a, b, c, d, idx) ;17     if (a >= c || b >= d) return 0 ;18     if (idx == n) return (c-a)*(d-b) ;19     int aa[] = {a, min(c,max(a,x1[idx])), max(a, min(c,x2[idx])), c}, 20         bb[] = {b, min(d,max(b,y1[idx])), max(b, min(d,y2[idx])), d} ;21         22     for (i = 0 ; i < 3 ; i++)23         for (j = 0 ; j < 3 ; j++) if (i != 1 || j != 1)24         ans += dfs (aa[i], bb[j], aa[i+1], bb[j+1], idx+1) ;25     return ans ;26 }27 28 29 int main ()30 {31     int a, b, i ;32     freopen ("rect1.in", "r", stdin) ;33     freopen ("rect1.out", "w", stdout) ;34     while (~scanf ("%d%d%d", &a, &b, &n))35     {36         memset (col_hash, 0, sizeof(col_hash)) ;37         for (i = 0 ; i < n; i++)38             scanf ("%d%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i], &color[i]) ;39         col_hash[1] += dfs (0,0,a,b,0) ;40         for (i = 0 ; i < n; i++)41             col_hash[color[i]] += dfs (x1[i], y1[i], x2[i], y2[i], i+1) ;42         43         for (i = 1 ; i <= 2500 ; i++) if (col_hash[i] != 0)44             printf ("%d %d\n", i, col_hash[i]) ;45     }46     return 0 ;47 }
        
       
      

 

Contact：暴力题。各种犯2，算错上界，看漏条件，4A。。。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4  5  6 typedef struct NODE{ 7     int num, val ; 8 }NODE ; 9 10 11 char str[200010] ;12 int dp[70000] ;13 NODE ans[70000] ;14 15 16 void Add(int len, int num){dp[(len<<12) + num] ++ ;}17 int cmp(const void *a, const void *b)18 {19     NODE *p = (NODE*)a, *q = (NODE*)b ;20     if (p->num != q->num) return q->num - p->num ;21     return p->val - q->val ;22 }23 24 25 void prt(int val)26 {27     int i, len = val>>12 ;28     val &= ((1<<12)-1) ;29     for (i = len-1 ; i >= 0 ; i--)30         printf ("%d", (val>>i) & 1) ;31 }32 33 34 void output(int n)35 {36     int i, j, cc ;37     int ccc = 0 ;38     for (i = 0, j=0 ; i < 54000 ; i++) if (dp[i] != 0)39     {40         ans[j].num = dp[i] ;41         ans[j].val = i ;42         j++ ;43     }44     cc = j ;45     qsort(ans, cc, sizeof(ans[0]), cmp) ;46     for (i = 0, j = 0 ; j < cc ; j++)47     {48         if (j == 0)49         {50             printf ("%d\n", ans[j].num) ;51             prt(ans[j].val) ;52             ccc = 1 ;53         }54         else if (ans[j].num != ans[j-1].num)55         {56             i++ ;57             if (i >= n) break ;58             printf ("\n%d\n", ans[j].num) ;59             prt(ans[j].val) ;60             ccc = 1;61         }62         else{63             if (ccc == 6) printf ("\n"), ccc = 0 ;64             else printf (" ") ;65             prt(ans[j].val) ;66             ccc++ ;67         }68     }69 }70 71 72 int main ()73 {74     int a, b, len, num, n, j, slen ;75     freopen ("contact.in", "r", stdin) ;76     freopen ("contact.out", "w", stdout) ;77     scanf ("%d%d%d", &a, &b, &n) ;78     str[0] = '\0' ;79     while (~scanf ("%s", str+strlen(str))) ;80     slen = strlen(str) ;81     {82         memset (dp, 0, sizeof(dp)) ;83         for (len = a ; len <= b  && len <= slen ; len++)84         {85             for (j = 0, num = 0 ; j < len ; j++)86                 num = num*2 + str[j]-'0' ;87             Add(len, num) ;88             for (j = len ; str[j] ; j++)89             {90                 num = num*2 + str[j]-'0' ;91                 num &= (1<
        
       
      

 

Stamps：简单dp。

1 # include 
      
        2  3  4 int v[55] ; 5 int dp[2000010] ; 6  7  8 int max(int a, int b){
    return a>b?a:b;} 9 int min(int a, int b){
    return a
       
        = 0)28                     dp[i] = min(dp[i], dp[i-v[j]]+1) ;29             }30             if (dp[i] > k) break ;31         }32         printf ("%d\n", i-1) ;33     }34     return 0 ;35 }