本质上讲,这两道题都是数学题,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),我线性代数也忘得差不多了,不过对克莱姆法则还有一点印象。
- #include <fstream>
- using namespace std ;
- ifstream fin ( "ratios.in" ) ;
- ofstream fout ( "ratios.out" ) ;
- const int LEN = 3 ;
- int dest [LEN ] ;
- int matrix [LEN ] [LEN ], backup [LEN ] [LEN ] ;
- void cofactor ( const int a [ ] [LEN ], int b [ ] [LEN ], int n, int k )
- {
- int bi = 0, bj = 0 ;
- for ( int i = 1 ; i < n ; ++i )
- {
- for ( int j = 0 ; j < n ; ++j ) {
- if (j ==k )
- continue ;
- b [bi ] [bj ] = a [i ] [j ] ;
- bj ++ ;
- }
- bi ++ ;
- bj = 0 ;
- }
- }
- int deter ( int a [ ] [LEN ], int n )
- {
- if (n == 1 )
- return a [ 0 ] [ 0 ] ;
- else
- {
- int sum = 0 ;
- for ( int i = 0 ; i < n ; ++i )
- {
- int b [LEN ] [LEN ] = { 0 } ;
- cofactor (a,b,n,i ) ;
- int coef = ( (i % 2 == 0 ) ? 1 : - 1 ) ;
- sum + = (coef *a [ 0 ] [i ] *deter (b,n - 1 ) ) ;
- }
- return sum ;
- }
- }
- void change ( int curr, int last = - 1 )
- {
- if (last ! = - 1 )
- {
- for ( int i = 0 ; i < LEN ; ++i )
- matrix [last ] [i ] = backup [last ] [i ] ;
- }
- for ( int i = 0 ; i < LEN ; ++i )
- matrix [curr ] [i ] = dest [i ] ;
- }
- int gcd ( int m, int n )
- {
- if (m == 0 ) return n ;
- if (n == 0 ) return m ;
- if (m < n )
- {
- int tmp = m ;
- m = n ;
- n = tmp ;
- }
- while (n ! = 0 )
- {
- int tmp = m % n ;
- m = n ;
- n = tmp ;
- }
- return m ;
- }
- int main ( )
- {
- for ( int i = 0 ; i < LEN ; i ++ )
- fin >> dest [i ] ;
- int num ;
- for ( int i = 0 ; i < 3 ; i ++ )
- {
- for ( int j = 0 ; j < 3 ; j ++ )
- {
- fin >> num ;
- matrix [i ] [j ] = num, backup [i ] [j ] = num ;
- }
- }
- int res1 = deter (matrix ,LEN ) ;
- if (res1 == 0 ) {
- fout << "NONE\n" ;
- return 0 ;
- }
- change ( 0, - 1 ) ;
- int res2 = deter (matrix, LEN ) ;
- change ( 1, 0 ) ;
- int res3 = deter (matrix, LEN ) ;
- change ( 2, 1 ) ;
- int res4 = deter (matrix, LEN ) ;
- if (res1 < 0 )
- {
- res1 = -res1 ;
- res2 = -res2 ;
- res3 = -res3 ;
- res4 = -res4 ;
- }
- if (res2 < 0 || res3 < 0 || res4 < 0 )
- {
- fout << "NONE\n" ;
- return 0 ;
- }
- int tmp = gcd (gcd (res2, gcd (res3, res4 ) ), res1 ) ;
- fout << res2 /tmp << ' ' << res3 /tmp << ' ' << res4 /tmp << ' ' << res1 /tmp << '\n' ;
- return 0 ;
- }
值得一提的是求解行列式的值,也是个比较好的递归的示例吧,我想大学里的《线性代数》课完全可以用编程来教嘛...
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在这个排列中所在的位置可以用下面的思路:
- 比4小的数有3个
- 比5小的数有4个但4已经在之前出现过了所以是3个
- 比2小的数有1个
- 比3小的数有两个但2已经在之前出现过了所以是1个
- 比1小的数有0个
- 那么45231在这个排列中的顺序是3*4!+3*3!+1*2!+1*1!+0*0!+1=94
空间还是可以的,时间表现一般吧,广搜是一般的思路,有谁能想出来启发式算法吗?
- #include <fstream>
- #include <vector>
- #include <deque>
- #include <string>
- using namespace std ;
- ifstream fin ( "msquare.in" ) ;
- ofstream fout ( "msquare.out" ) ;
- typedef vector < int > VInt ;
- typedef void Fun ( const VInt &, VInt & ) ;
- typedef Fun * FunPtr ;
- const int MAX_NUM = 40321 ;
- const int MSQUARE_SIZE = 8 ;
- const int FRAC [MSQUARE_SIZE ] = { 1, 1, 2, 6, 24, 120, 720, 5040 } ;
- const string sFlag = "ABC" ;
- bool HashTable [MAX_NUM ] = { 0 } ;
- struct msquare
- {
- msquare ( ) : vState (MSQUARE_SIZE ), sPath ( ) { }
- VInt vState ;
- string sPath ;
- } ;
- deque <msquare > Q ;
- void SwapRow ( const VInt & vSrc, VInt & vRes )
- {
- vRes. resize ( 8 ) ;
- int i, j = 0 ;
- for (i = 4 ; i < 8 ; ++i, ++j )
- vRes [j ] = vSrc [i ] ;
- for (i = 0 ; i < 4 ; ++i, ++j )
- vRes [j ] = vSrc [i ] ;
- }
- void SwapColumn ( const VInt & vSrc, VInt & vRes )
- {
- vRes. resize ( 8 ) ;
- vRes [ 0 ] = vSrc [ 3 ] ;
- for ( int i = 1 ; i < 4 ; ++i )
- vRes [i ] = vSrc [i - 1 ] ;
- vRes [ 4 ] = vSrc [ 7 ] ;
- for ( int i = 5 ; i < 8 ; ++i )
- vRes [i ] = vSrc [i - 1 ] ;
- }
- void RotateMiddle ( const VInt & vSrc, VInt & vRes )
- {
- vRes = vSrc ;
- vRes [ 1 ] = vSrc [ 5 ] ;
- vRes [ 2 ] = vSrc [ 1 ] ;
- vRes [ 5 ] = vSrc [ 6 ] ;
- vRes [ 6 ] = vSrc [ 2 ] ;
- }
- inline int Contor (VInt & v )
- {
- int ans = 0 ;
- for ( int i = 0 ; i < 8 ; i ++ )
- {
- int tmp = 0 ;
- for ( int j = i + 1 ; j < 8 ; j ++ ) if (v [i ] > v [j ] ) ++tmp ;
- ans + = tmp * FRAC [ 7 -i ] ;
- }
- return ans + 1 ;
- }
- int main ( )
- {
- VInt vDest (MSQUARE_SIZE ), vStart (MSQUARE_SIZE ) ;
- for ( int i = 0 ; i < 4 ; ++i )
- fin >> vDest [i ] ;
- for ( int i = 7 ; i >= 4 ; --i )
- fin >> vDest [i ] ;
- for ( int i = 0 ; i < 4 ; ++i )
- vStart [i ] = i + 1 ;
- for ( int i = 7, j = 4 ; i >= 4 ; --i, ++j )
- vStart [j ] = i + 1 ;
- if (vStart == vDest )
- {
- fout << 0 << endl << endl ;
- return 0 ;
- }
- FunPtr funArr [ 3 ] ;
- funArr [ 0 ] = SwapRow, funArr [ 1 ] = SwapColumn, funArr [ 2 ] = RotateMiddle ;
- msquare m ;
- m. vState = vStart ;
- Q. push_back (m ) ;
- VInt vTmp ;
- int HashValue = Contor (vStart ) ;
- HashTable [HashValue ] = true ;
- while ( !Q. empty ( ) )
- {
- for ( int i = 0 ; i < 3 ; ++i )
- {
- m = Q. front ( ) ;
- vTmp. clear ( ) ;
- funArr [i ] (m. vState, vTmp ) ;
- if (vTmp == vDest )
- {
- m. sPath + = sFlag [i ] ;
- size_t size = m. sPath. size ( ), start = 0, len ;
- fout << size << endl ;
- while ( true )
- {
- if (size > 60 )
- {
- len = 60 ;
- start + = len ;
- size - = len ;
- fout << string (m. sPath, start, len ) << endl ;
- }
- else
- {
- len = size ;
- fout << string (m. sPath, start, len ) << endl ;
- return 0 ;
- }
- }
- }
- HashValue = Contor (vTmp ) ;
- if ( !HashTable [HashValue ] )
- {
- m. vState = vTmp ;
- m. sPath + = sFlag [i ] ;
- Q. push_back (m ) ;
- HashTable [HashValue ] = true ;
- }
- }
- Q. pop_front ( ) ;
- }
- return 0 ;
- }