USACO 3.2

3.2开始是背包的介绍，然后六个题目，没有一题和背包有关系！

Factorials：比较经典的一个题。求n阶乘最右边第一个不为0的数字。因为0肯定是有一个因子2和一个因子5组合成的，而在n!中因数2的个数显然远多于5的个数。所以for一遍n，碰到因数2就加1，碰到因数5就减1。剩下的乘起来对10取mod，最后再乘一下剩下的2的个数。

 1 # include <stdio.h>
 2 
 3 
 4 int main ()
 5 {
 6     int n, ans, i, two, ii ;
 7     freopen ("fact4.in", "r", stdin) ;
 8     freopen ("fact4.out", "w", stdout) ;
 9     while (~scanf ("%d", &n))
10     {
11         ans = 1 ;
12         two = 0 ;
13         for (i = 1 ; i <= n ; i++)
14         {
15             ii = i ;
16             while (ii%2 == 0) ii/=2, two++ ;
17             while (ii%5 == 0) ii/=5, two-- ;
18             ans = (ans*ii)%10 ;
19         }
20         while (two--) ans = (ans*2)%10 ;
21         printf("%d
", ans) ;
22     }
23     return 0 ;
24 }

View Code

Stringsobits：递推加递归。递推算出对于所有的n和l，不超过l个1长度为n的字符串有几个。f[n,l] = f[n-1,l]+f[n-1,l-1]。边界要特别注意：f[n,0] = 1。之后递归，根据长度为n开头为0且1的个数不超过L的字符串个数可以确定第一位是0还是1。

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 int tab[40][40] ;
 6 
 7 
 8 int recv(int n, int l)
 9 {
10     if (l == 0) return 1 ;
11     if (l > n) return recv (n,n) ;
12     if (tab[n][l] != -1) return tab[n][l] ;
13     return tab[n][l] = (recv(n-1,l)+recv(n-1,l-1)) ;
14 }
15 
16 
17 int main ()
18 {
19     long long n, l, I, i ;
20     freopen ("kimbits.in", "r", stdin) ;
21     freopen ("kimbits.out", "w", stdout) ;
22     memset (tab, -1, sizeof(tab)) ;
23     tab[0][0] = 1 ;
24     while (~scanf ("%lld%lld%lld", &n, &l, &I))
25     {
26         for (i = n ; i > 0 ; i--)
27         {
28             n = i ;
29             if (I <= recv(n-1,l))
30                 printf ("0") ;
31             else{
32                 printf ("1") ;
33                 I -= recv(n-1,l) ;
34                 l-- ;
35             }
36         }
37         puts ("") ;
38     }
39     return 0 ;
40 }

View Code

Spinning Wheels：这题主要题意细节比较多，其他没啥。把时间从0到359枚举一次，因为超过这个时间肯定陷入周期。注意细节就可以了。

 1 # include <stdio.h>
 2 
 3 
 4 typedef struct WHEEL{
 5     int angle[360] ;
 6     int speed ;
 7     
 8 }WHEEL ;
 9 
10 
11 WHEEL wheel[5] ;
12 int buff[360] ;
13 
14 
15 void Input(WHEEL* p)
16 {
17     int i, a, b, num ;
18     for (i = 0 ; i < 360 ; i++)
19         p->angle[i] = 0 ;
20     scanf ("%d", &p->speed) ;
21     scanf ("%d", &num) ;
22     while (num--)
23     {
24         scanf ("%d%d", &a, &b) ;
25         for (i = a ; i <= a+b ; i++)
26             p->angle[i%360] = 1 ;
27     }
28 }
29 
30 
31 void Move(WHEEL* p)
32 {
33     int i ;
34     for (i = 0 ; i < 360 ; i++)
35         buff[i] = p->angle[i] ;
36     for (i = 0 ; i < 360 ; i++)
37         p->angle[i] = buff[(i-p->speed+360)%360] ;
38 }
39 
40 
41 int Judge()
42 {
43     int i, j ;
44     for (i = 0 ; i < 360 ; i++)
45     {
46         for (j = 0 ; j < 5 ; j++)
47             if (wheel[j].angle[i] == 0) break ;
48         if (j >= 5) return 1 ;
49     }
50     return 0 ;
51 }
52 
53 
54 int gao()
55 {
56     int i, j ;
57     for (i = 0 ; i < 360 ; i++)
58     {
59         if (Judge()) return i ;
60         for (j = 0 ; j < 5 ; j++)
61             Move(&wheel[j]) ;
62     }
63     return -1 ;
64 }
65 
66 
67 int main ()
68 {
69     int i, ans ;
70     freopen ("spin.in", "r", stdin) ;
71     freopen ("spin.out", "w", stdout) ;
72     for (i = 0 ; i < 5 ; i++)
73         Input(&wheel[i]) ;
74     ans = gao() ;
75     if (ans == -1) printf ("none
") ;
76     else printf ("%d
", ans) ;
77     return 0 ;
78 }

View Code

Feed Ratios：一开始没注意答案不会超过100这个条件。看到以后就知道是一个O(n^3)的暴力算法。同样是要注意细节，每次除法除数都要判断是否为0。

 1 # include <stdio.h>
 2 
 3 
 4 int judge (int a, int b)
 5 {
 6     if (b == 0 && a == 0) return 101 ;
 7     if (b == 0) return -1 ;
 8     if (a % b != 0) return -1 ;
 9     return a/b ;
10 }
11 
12 
13 int min(int a, int b){return a<b?a:b;}
14 
15 
16 int main ()
17 {
18     int i, j, k, kk ;
19     int a, b, c, ka, kb, kc, a1, a2, a3, a4 ;
20     int x[4][3] ;
21     freopen ("ratios.in", "r", stdin) ;
22     freopen ("ratios.out", "w", stdout) ;
23     for (i = 0 ; i < 4 ; i++)
24         for (j = 0 ; j < 3 ; j++)
25             scanf ("%d", &x[i][j]) ;
26     a4 = 1000 ;
27     for (i = 0 ; i <= 100 ; i++)
28         for (j = 0 ; j <= 100 ; j++)
29             for (k = 0 ; k <= 100 ; k++)
30             {
31                 if (i == 0 && j == 0 && k == 0) continue ;
32                 a = i * x[1][0] + j * x[2][0] + k * x[3][0] ;
33                 b = i * x[1][1] + j * x[2][1] + k * x[3][1] ;
34                 c = i * x[1][2] + j * x[2][2] + k * x[3][2] ;
35                 if (b * x[0][0] != a * x[0][1]) continue ;
36                 if (c * x[0][0] != a * x[0][2]) continue ;
37                 ka = judge(a, x[0][0]) ;
38                 if (ka < 0) continue ;
39                 kb = judge(b, x[0][1]) ;
40                 if (kb < 0) continue ;
41                 kc = judge(c, x[0][2]) ;
42                 if (kc < 0) continue ;
43                 if (ka > 100 && kb > 100 && kc > 100) continue ;
44                 kk = min(ka, min(kb, kc)) ;
45                 if (ka > 100) ka = kk ;
46                 if (ka != kk) continue ;
47                 if (kb > 100) kb = kk ;
48                 if (kb != kk) continue ;
49                 if (kc > 100) kc = kk ;
50                 if (kc != kk) continue ;
51                 if (kk < a4) a1 = i, a2 = j, a3 = k, a4 = kk ;
52             }
53     if (a4 > 100) puts ("NONE") ;
54     else printf ("%d %d %d %d
", a1,a2,a3,a4) ;
55     return 0 ;
56 }

View Code

Magic Squares：标准BFS解，没啥好说的。值得一提的是hash的时候，可以像我这样直接拿拼出来的数字取mod，也可以用最完美的逆序数哈希算法。这题的代码稍加变形就可以拿来A八数码问题。

  1 # include <stdio.h>
  2 # include <string.h>
  3 
  4 
  5 # define HASH_MAX 50021
  6 
  7 
  8 int hash[HASH_MAX+10] ;
  9 int a[8], start, end ;
 10 int q[HASH_MAX+10], fa[HASH_MAX+10], step[HASH_MAX+10] ;
 11 char path[HASH_MAX+10] ;
 12 char tab[] = "ABC" ;
 13 
 14 
 15 int A(int x)
 16 {
 17     int i, t ;
 18     for (i = 7 ; i >= 0 ; i--)
 19         a[i] = x%10, x /= 10 ;
 20     for (i = 0 ; i < 4 ; i++)
 21         t = a[i], a[i] = a[7-i], a[7-i] = t ;
 22     for (i = 0, x = 0 ; i < 8 ; i++)
 23         x = x * 10 + a[i] ;
 24     return x ;
 25 }
 26 
 27 int B(int x)
 28 {
 29     int i, t ;
 30     for (i = 7 ; i >= 0 ; i--)
 31         a[i] = x%10, x /= 10 ;
 32     t = a[3], a[3] = a[2], a[2] = a[1], a[1] = a[0], a[0] = t ;
 33     t = a[4], a[4] = a[5], a[5] = a[6], a[6] = a[7], a[7] = t ;
 34     for (i = 0, x = 0 ; i < 8 ; i++)
 35         x = x * 10 + a[i] ;
 36     return x ;
 37 }
 38 
 39 
 40 int C(int x)
 41 {
 42     int i, t ;
 43     for (i = 7 ; i >= 0 ; i--)
 44         a[i] = x%10, x /= 10 ;
 45     t = a[2], a[2] = a[1], a[1] = a[6], a[6] = a[5], a[5] = t ;
 46     for (i = 0, x = 0 ; i < 8 ; i++)
 47         x = x * 10 + a[i] ;
 48     return x ;
 49 }
 50 
 51 
 52 int hashash(int x)
 53 {
 54     int i ;
 55     for (i = x % HASH_MAX ; hash[i] != 0; i=(i+1)%HASH_MAX)
 56         if (hash[i] == x) return 1 ;
 57     return 0 ;
 58 }
 59 
 60 
 61 void Hash(int x)
 62 {
 63     int i ;
 64     for (i = x % HASH_MAX ; hash[i] != 0 ; i = (i+1)%HASH_MAX) ;
 65     hash[i] = x ;
 66 }
 67 
 68 
 69 int bfs ()
 70 {
 71     int i, front = 0, rear = 1, x, xx ;
 72     int (*fun[3])(int) = {A, B, C} ;
 73     q[0] = start ;
 74     Hash(start) ;
 75     step[0] = 0 ;
 76     while (front != rear)
 77     {
 78         x = q[front++] ;
 79         if (x == end) return front-1 ;
 80         for (i = 0 ; i < 3 ; i++)
 81         {
 82             xx = (*fun[i])(x) ;
 83             if (!hashash(xx))
 84             {
 85                 Hash(xx) ;
 86                 path[rear] = tab[i] ;
 87                 fa[rear] = front-1 ;
 88                 step[rear] = step[front-1] + 1 ;
 89                 q[rear++] = xx ;
 90             }
 91         }
 92     }
 93 }
 94 
 95 
 96 void PrtPath(int idx){
 97     if (idx == 0) return ;
 98     PrtPath(fa[idx]) ;
 99     printf ("%c", path[idx]) ;
100 }
101 
102 
103 int main ()
104 {
105     int i, idx ;
106     freopen ("msquare.in", "r", stdin) ;
107     freopen ("msquare.out", "w", stdout) ;
108     while (~scanf ("%d %d %d %d %d %d %d %d", 
109                     &a[0], &a[1], &a[2], &a[3],
110                     &a[4], &a[5], &a[6], &a[7]))
111     {
112         memset (hash, 0, sizeof(hash)) ;
113         end = 0 ;
114         for (i = 0 ;i < 8 ; i++) end = end*10+a[i] ;
115         start = 12345678 ;
116         idx = bfs () ;
117         printf ("%d
", step[idx]) ;
118         PrtPath(idx) ;
119         printf ("
") ;
120     }
121     return 0 ;
122 }

View Code

Sweet Butter：很容易想到枚举每个点作为“中点”，剩下的问题就是单源最短路径问题。值得注意的是点的个数是800，边数是1450，是一个很稀疏的图，可以用Dijstra+堆优化（O((V+E)lgV)）或者SPFA算法。这里用的是Dijkstra+堆优化的方法过的。本题是这章里面代码量最大的。某些小朋友偷懒不好好写堆，用STL的优先队列来写，也是可以的- -。

  1 # include <stdio.h>
  2 # include <stdlib.h>
  3 # include <string.h>
  4 
  5 
  6 typedef struct EDGE{
  7     int s, e, w ;
  8 }EDGE ;
  9 
 10 
 11 typedef struct VERTEX{
 12     int idx, dist ;
 13 }VERTEX ;
 14 
 15 
 16 EDGE edge[3100] ;
 17 int vidx[810], vnum[810], num[810] ;
 18 int INF = 0x3f3f3f3f ;
 19 
 20 
 21 int dist[810], vis[810], inheap[810] ;
 22 VERTEX heap[810] ;
 23 int heap_len ;
 24 
 25 
 26 void heapify(int idx)
 27 {
 28     VERTEX tmp ;
 29     int lidx = idx ;
 30     if (idx*2 <= heap_len && heap[idx*2].dist < heap[lidx].dist)
 31         lidx = idx*2 ;
 32     if (idx*2+1 <= heap_len && heap[idx*2+1].dist < heap[lidx].dist)
 33         lidx = idx*2+1 ;
 34     
 35     if (lidx != idx){
 36         inheap[heap[idx].idx] = lidx ;
 37         inheap[heap[lidx].idx] = idx ;
 38         tmp = heap[idx], heap[idx] = heap[lidx], heap[lidx] = tmp ;
 39         heapify (lidx) ;
 40     }
 41 }
 42 
 43 
 44 VERTEX pop()
 45 {
 46     VERTEX rtn = heap[1] ;
 47     heap[1] = heap[heap_len--] ;
 48     if (heap_len)
 49     {
 50         inheap[heap[1].idx] = 1 ;
 51         heapify(1) ;
 52     }
 53     return rtn ;
 54 }
 55 
 56 
 57 void update (int vidx, int d)
 58 {
 59     VERTEX tmp ;
 60     int i ;
 61     if (inheap[vidx] == 0)
 62         heap[heap_len+1].idx = vidx, heap[heap_len+1].dist = d, 
 63         inheap[vidx] = heap_len+1, heap_len++ ;
 64     else heap[inheap[vidx]].dist = d ;
 65     
 66     for (i = inheap[vidx] ; i != 1 ; i /= 2)
 67     {
 68         if (heap[i/2].dist > heap[i].dist)
 69         {
 70             inheap[heap[i/2].idx] = i ;
 71             inheap[heap[i].idx] = i/2 ;
 72             tmp = heap[i/2], heap[i/2] = heap[i], heap[i] = tmp ;
 73         }
 74         else break ;
 75     }
 76 }
 77 
 78 
 79 void dijkstra(int sv, int n)
 80 {
 81     VERTEX v ;
 82     int i, ii;
 83     memset (vis, 0, sizeof(vis)) ;
 84     memset (dist, 0x3f, sizeof(dist)) ;
 85     memset (inheap, 0, sizeof(inheap)) ;
 86     heap[1].idx = sv, heap[1].dist = 0, inheap[sv] = 1, heap_len = 1 ;
 87     for (ii = 1 ; ii < n ; ii++)
 88     {
 89         v = pop() ;
 90         dist[v.idx] = v.dist ;
 91         vis[v.idx] = 1 ;
 92         for (i = 0 ; i < vnum[v.idx] ; i++) if (vis[edge[vidx[v.idx]+i].e] == 0)
 93             if (edge[vidx[v.idx]+i].w + v.dist < dist[edge[vidx[v.idx]+i].e])
 94             {
 95                 dist[edge[vidx[v.idx]+i].e] = edge[vidx[v.idx]+i].w + v.dist ;
 96                 update (edge[vidx[v.idx]+i].e, dist[edge[vidx[v.idx]+i].e]) ;
 97             }
 98     }
 99 }
100 
101 
102 int gao(int sv, int n)
103 {
104     int i, ans = 0 ;
105     dijkstra(sv, n) ;
106     for (i = 1 ; i <= n ; i++)
107         ans += (num[i] * dist[i]) ;
108     return ans ;
109 }
110 
111 
112 int min(int a, int b){return a<b?a:b;}
113 
114 
115 int cmp(const void *a, const void *b)
116 {
117     EDGE *p = (EDGE*)a, *q = (EDGE*)b ;
118     if (p->s != q->s) return p->s - q->s ;
119     if (p->e != q->e) return p->e - q->e ;
120     return p->w - q->w ;
121 }
122 
123 
124 int main ()
125 {
126     int n, p, c, ans, x ;
127     int i, s, e, w ;
128     freopen ("butter.in", "r", stdin) ;
129     freopen ("butter.out", "w", stdout) ;
130     while (~scanf ("%d%d%d", &n, &p, &c))
131     {
132         memset (num,0,sizeof(num)) ;
133         while (n--)
134             scanf ("%d", &x), num[x]++ ;
135         for (i = 0 ;i < c ; i++)
136         {
137             scanf ("%d%d%d", &s, &e, &w) ;
138             edge[2*i].s = s, edge[2*i].e = e, edge[2*i].w = w ;
139             edge[2*i+1].s = e, edge[2*i+1].e = s, edge[2*i+1].w = w ;
140         }
141         qsort(edge, 2*c, sizeof(edge[0]), cmp) ;
142         memset (vnum, 0, sizeof(vnum)) ;
143         memset (vidx, -1, sizeof(vidx)) ;
144         for (i = 0 ; i < 2*c ; i++)
145         {
146             vnum[edge[i].s]++ ;
147             if (vidx[edge[i].s] == -1) vidx[edge[i].s] = i ;
148         }
149         ans = INF ;
150         for (i = 1 ; i <= p ; i++)
151             ans = min(ans, gao(i, p)) ;
152         printf ("%d
", ans) ;
153     }
154     return 0 ;
155 }

View Code

UP:用SPFA实现了一个，时间上比Dijstra要快上一些。而且SPFA好写啊！

  1 # include <stdio.h>
  2  # include <stdlib.h>
  3  # include <string.h>
  4  
  5  
  6  typedef struct EDGE{
  7      int s, e, w ;
  8  }EDGE ;
  9  
 10  
 11  typedef struct VERTEX{
 12      int idx, dist ;
 13  }VERTEX ;
 14  
 15  
 16  EDGE edge[3100] ;
 17  int vidx[810], vnum[810], num[810] ;
 18  int INF = 0x3f3f3f3f ;
 19  
 20  
 21  int dist[810], inqueue[810], q[6000] ;
 22  
 23  
 24  void spfa(int sv, int n)
 25  {
 26      int f, r, v, vv, i ;
 27      memset (dist, 0x3f, sizeof(dist)) ;
 28      memset (inqueue, 0, sizeof(inqueue)) ;
 29      dist[sv] = 0, q[3000] = sv, inqueue[sv] = 1 ;
 30      for (f = 3000, r = 3001 ; f < r ; f++)
 31      {
 32          v = q[f] ;
 33          inqueue[v] = 0 ;
 34          for (i = vidx[v] ; i < vidx[v]+vnum[v] ; i++)
 35          {
 36              vv = edge[i].e ;
 37              if (dist[vv] > dist[v]+edge[i].w)
 38              {
 39                  dist[vv] = dist[v]+edge[i].w ;
 40                  if (inqueue[vv] == 0)
 41                  {
 42                      inqueue[vv] = 1 ;
 43                      if (dist[vv] < dist[q[f]])
 44                          q[--f] = vv ;
 45                      else q[r++] = vv ;
 46                  }
 47              }
 48          }
 49      }
 50  }
 51  
 52  
 53  int gao(int sv, int n)
 54  {
 55      int i, ans = 0 ;
 56      spfa(sv, n) ;
 57      for (i = 1 ; i <= n ; i++)
 58          ans += (num[i] * dist[i]) ;
 59      return ans ;
 60  }
 61  
 62  
 63  int min(int a, int b){return a<b?a:b;}
 64  
 65  
 66  int cmp(const void *a, const void *b)
 67  {
 68      EDGE *p = (EDGE*)a, *q = (EDGE*)b ;
 69      if (p->s != q->s) return p->s - q->s ;
 70      if (p->e != q->e) return p->e - q->e ;
 71      return p->w - q->w ;
 72  }
 73  
 74  
 75  int main ()
 76  {
 77      int n, p, c, ans, x ;
 78      int i, s, e, w ;
 79      freopen ("butter.in", "r", stdin) ;
 80      freopen ("butter.out", "w", stdout) ;
 81      while (~scanf ("%d%d%d", &n, &p, &c))
 82      {
 83          memset (num,0,sizeof(num)) ;
 84          while (n--)
 85              scanf ("%d", &x), num[x]++ ;
 86          for (i = 0 ;i < c ; i++)
 87          {
 88              scanf ("%d%d%d", &s, &e, &w) ;
 89              edge[2*i].s = s, edge[2*i].e = e, edge[2*i].w = w ;
 90              edge[2*i+1].s = e, edge[2*i+1].e = s, edge[2*i+1].w = w ;
 91          }
 92          qsort(edge, 2*c, sizeof(edge[0]), cmp) ;
 93          memset (vnum, 0, sizeof(vnum)) ;
 94          memset (vidx, -1, sizeof(vidx)) ;
 95          for (i = 0 ; i < 2*c ; i++)
 96          {
 97              vnum[edge[i].s]++ ;
 98              if (vidx[edge[i].s] == -1) vidx[edge[i].s] = i ;
 99          }
100          ans = INF ;
101          for (i = 1 ; i <= p ; i++)
102              ans = min(ans, gao(i, p)) ;
103          printf ("%d
", ans) ;
104      }
105      return 0 ;
106  }

View Code