USACO Feed Ratios, Magic Squares

本質上講，這兩道題都是數學題，ratios是行列式解線性方程組，squares是組合數學。可見ACMer數學基礎好确實是非常重要的。

1、Feed Ratios

所求的實際上就是一個最簡配比 x, y, z, w，使得 x(a1,b1,c1) + y(a2,b2,c2) + z(a3,b3,c3) = w(g1,g2,g3)，我線性代數也忘得差不多了，不過對克萊姆法則還有一點印象。

1. #include <fstream>
2. using  namespace std ;
3. ifstream fin ( "ratios.in" ) ;
4. ofstream fout ( "ratios.out" ) ;
5. const  int LEN  =  3 ;
6. int dest [LEN ] ;
7. int matrix [LEN ] [LEN ], backup [LEN ] [LEN ] ;
8. void cofactor ( const  int a [ ] [LEN ],  int b [ ] [LEN ],  int n,  int k )
9. {
10.      int bi  =  0, bj  =  0 ;
11.      for ( int i  =  1 ; i  < n ;  ++i )
12.      {
13.          for ( int j  =  0 ; j  < n ;  ++j ) {
14.              if (j ==k )
15.              continue ;
16.             b [bi ] [bj ]  = a [i ] [j ] ;
17.             bj ++ ;
18.          }
19.         bi ++ ;
20.         bj  =  0 ;
21.      }
22. }
23. int deter ( int a [ ] [LEN ],  int n )
24. {
25.      if (n == 1 )
26.      return a [ 0 ] [ 0 ] ;
27.      else
28.      {
29.          int sum  =  0 ;
30.          for ( int i  =  0 ; i  < n ;  ++i )
31.          {
32.              int b [LEN ] [LEN ]  =  { 0 } ;
33.             cofactor (a,b,n,i ) ;
34.              int coef  =  ( (i % 2 == 0 ) ? 1 : - 1 ) ;
35.             sum  + =  (coef *a [ 0 ] [i ] *deter (b,n - 1 ) ) ;
36.          }
37.          return sum ;
38.      }
39. }
40. void change ( int curr,  int last  =  - 1 )
41. {
42.      if (last  ! =  - 1 )
43.      {
44.          for ( int i  =  0 ; i  < LEN ;  ++i )
45.         matrix [last ] [i ]  = backup [last ] [i ] ;
46.      }
47.      for ( int i  =  0 ; i  < LEN ;  ++i )
48.     matrix [curr ] [i ]  = dest [i ] ;
49. }
50. int gcd ( int m,  int n )
51. {
52.      if  (m  ==  0 )  return n ;
53.      if  (n  ==  0 )  return m ;
54.      if  (m  < n )
55.      {
56.          int tmp  = m ;
57.         m  = n ;
58.         n  = tmp ;
59.      }
60.      while  (n  ! =  0 )
61.      {
62.          int tmp  = m  % n ;
63.         m  = n ;
64.         n  = tmp ;
65.      }
66.      return m ;
67. }
68. int main ( )
69. {
70.      for ( int i  =  0 ; i  < LEN ; i ++ )
71.         fin  >> dest [i ] ;
72.      int num ;
73.      for ( int i  =  0 ; i  <  3 ; i ++ )
74.      {
75.          for ( int j  =  0 ; j  <  3 ; j ++ )
76.          {
77.             fin  >> num ;
78.             matrix [i ] [j ]  = num, backup [i ] [j ]  = num ;
79.          }
80.      }
81.      int res1  = deter (matrix ,LEN ) ;
82.      if (res1  ==  0 )  {
83.         fout  <<  "NONE\n" ;
84.          return  0 ;
85.      }
86.     change ( 0,  - 1 ) ;
87.      int res2  = deter (matrix, LEN ) ;
88.     change ( 1,  0 ) ;
89.      int res3  = deter (matrix, LEN ) ;
90.     change ( 2,  1 ) ;
91.      int res4  = deter (matrix, LEN ) ;
92.      if (res1  <  0 )
93.      {
94.         res1  =  -res1 ;
95.         res2  =  -res2 ;
96.         res3  =  -res3 ;
97.         res4  =  -res4 ;
98.      }
99.      if (res2  <  0  || res3  <  0  || res4  <  0 )
100.      {
101.         fout  <<  "NONE\n" ;
102.          return  0 ;
103.      }
104.      int tmp  = gcd (gcd (res2, gcd (res3, res4 ) ), res1 ) ;
105.     fout  << res2 /tmp  <<  ' '  << res3 /tmp  <<  ' '  << res4 /tmp  <<  ' '  << res1 /tmp  <<  '\n' ;
106.      return  0 ;
107. }

值得一提的是求解行列式的值，也是個比較好的遞歸的示例吧，我想大學裡的《線性代數》課完全可以用程式設計來教嘛...

2、Magic Squares

這題還是蠻好的，整體思路要上考慮BFS，然後一個比較難的地方是設計一個好的HASH函數，因為BFS通常是很耗費空間的，要是HASH函數還沒有比較好的空間使用率，可能會掉鍊子，當然這道題資料量不大，8位數位闆，總共也就8! = 4W多種情況，但是你是程式員，多少得精益求精一點，是以，有了康托展開定理。

設Sn = {1,2,3,4,...,n}表示1,2,3,...,n的排列，如S3 = {1,2,3} 按從小到大排列一共6個 123 132 213 231 312 321。那麼找出S5中45231在這個排列中所在的位置可以用下面的思路：

1. 比4小的數有3個
2. 比5小的數有4個但4已經在之前出現過了是以是3個
3. 比2小的數有1個
4. 比3小的數有兩個但2已經在之前出現過了是以是1個
5. 比1小的數有0個
6. 那麼45231在這個排列中的順序是3*4!+3*3!+1*2!+1*1!+0*0!+1=94

空間還是可以的，時間表現一般吧，廣搜是一般的思路，有誰能想出來啟發式算法嗎？

1. #include <fstream>
2. #include <vector>
3. #include <deque>
4. #include <string>
5. using  namespace std ;
6. ifstream fin ( "msquare.in" ) ;
7. ofstream fout ( "msquare.out" ) ;
8. typedef vector < int > VInt ;
9. typedef  void Fun ( const VInt &, VInt & ) ;
10. typedef Fun * FunPtr ;
11. const  int MAX_NUM   =  40321 ;
12. const  int MSQUARE_SIZE  =  8 ;
13. const  int FRAC [MSQUARE_SIZE ] =  { 1,  1,  2,  6,  24,  120,  720,  5040 } ;
14. const string sFlag  =  "ABC" ;
15. bool HashTable [MAX_NUM ]  =  { 0 } ;
16. struct msquare
17. {
18.     msquare ( )  : vState (MSQUARE_SIZE ), sPath ( )  { }
19.     VInt vState ;
20.     string sPath ;
21. } ;
22. deque <msquare > Q ;
23. void SwapRow ( const VInt & vSrc, VInt & vRes )
24. {
25.     vRes. resize ( 8 ) ;
26.      int i, j  =  0 ;
27.      for (i  =  4 ; i  <  8 ;  ++i,  ++j )
28.         vRes [j ]  = vSrc [i ] ;
29.      for (i  =  0 ; i  <  4 ;  ++i,  ++j )
30.         vRes [j ]  = vSrc [i ] ;
31. }
32. void SwapColumn ( const VInt & vSrc, VInt & vRes )
33. {
34.     vRes. resize ( 8 ) ;
35.     vRes [ 0 ]  = vSrc [ 3 ] ;
36.      for ( int i  =  1 ; i  <  4 ;  ++i )
37.         vRes [i ]  = vSrc [i - 1 ] ;
38.     vRes [ 4 ]  = vSrc [ 7 ] ;
39.      for ( int i  =  5 ; i  <  8 ;  ++i )
40.         vRes [i ]  = vSrc [i - 1 ] ;
41. }
42. void RotateMiddle ( const VInt & vSrc, VInt & vRes )
43. {
44.     vRes  = vSrc ;
45.     vRes [ 1 ]  = vSrc [ 5 ] ;
46.     vRes [ 2 ]  = vSrc [ 1 ] ;
47.     vRes [ 5 ]  = vSrc [ 6 ] ;
48.     vRes [ 6 ]  = vSrc [ 2 ] ;
49. }
50. inline  int Contor (VInt & v )
51. {
52.      int ans  =  0 ;
53.      for  ( int i  =  0 ; i  <  8 ; i ++ )
54.      {
55.          int tmp  =  0 ;
56.          for  ( int j  = i + 1 ; j  <  8 ; j ++ )  if  (v [i ]  > v [j ] )  ++tmp ;
57.         ans  + = tmp  * FRAC [ 7 -i ] ;
58.      }
59.      return ans + 1 ;
60. }
61. int main ( )
62. {
63.     VInt vDest (MSQUARE_SIZE ), vStart (MSQUARE_SIZE ) ;
64.      for ( int i  =  0 ; i  <  4 ;  ++i )
65.         fin  >> vDest [i ] ;
66.      for ( int i  =  7 ; i  >=  4 ;  --i )
67.         fin  >> vDest [i ] ;
68.      for ( int i  =  0 ; i  <  4 ;  ++i )
69.         vStart [i ]  = i  +  1 ;
70.      for ( int i  =  7, j  =  4 ; i  >=  4 ;  --i,  ++j )
71.         vStart [j ]  = i  +  1 ;
72.      if (vStart  == vDest )
73.      {
74.         fout  <<  0  << endl  << endl ;
75.          return  0 ;
76.      }
77.     FunPtr funArr [ 3 ] ;
78.     funArr [ 0 ]  = SwapRow, funArr [ 1 ]  = SwapColumn, funArr [ 2 ]  = RotateMiddle ;
79.     msquare m ;
80.     m. vState  = vStart ;
81.     Q. push_back (m ) ;
82.     VInt vTmp ;
83.      int HashValue  = Contor (vStart ) ;
84.     HashTable [HashValue ]  =  true ;
85.      while ( !Q. empty ( ) )
86.      {
87.          for ( int i  =  0 ; i  <  3 ;  ++i )
88.          {
89.             m  = Q. front ( ) ;
90.             vTmp. clear ( ) ;
91.             funArr [i ] (m. vState, vTmp ) ;
92.              if (vTmp  == vDest )
93.              {
94.                 m. sPath  + = sFlag [i ] ;
95.                  size_t size  = m. sPath. size ( ), start  =  0, len ;
96.                 fout  << size  << endl ;
97.                  while ( true )
98.                  {
99.                      if (size  >  60 )
100.                      {
101.                         len  =  60 ;
102.                         start  + = len ;
103.                         size  - = len ;
104.                         fout  << string (m. sPath, start, len )  << endl ;
105.                      }
106.                      else
107.                      {
108.                         len  = size ;
109.                         fout  << string (m. sPath, start, len )  << endl ;
110.                          return  0 ;
111.                      }
112.                  }
113.              }
114.             HashValue  = Contor (vTmp ) ;
115.              if ( !HashTable [HashValue ] )
116.              {
117.                 m. vState  = vTmp ;
118.                 m. sPath  + = sFlag [i ] ;
119.                 Q. push_back (m ) ;
120.                 HashTable [HashValue ]  =  true ;
121.              }
122.          }
123.         Q. pop_front ( ) ;
124.      }
125.      return  0 ;
126. }