假設車的容量是C

1、第A題 A Tough Trip假設車的容量是C, 允許在起點加油 n 次, 那么車的最大行程就是 C + C/3 + C/5 + . + C/(2*n - 1), 有興趣的同學可以證明一下.第B題 Billiard bounces 簡單題目。注意球的初始位置在桌的中心。將球的速度分解成兩個方向，分別求出兩個方向的碰撞次數(shù)，相加就可以了。第C題 A Simple Problem本題題意簡單，將一個數(shù)用階乘的形式表示出來。算法也比較容易，可以按一般的超遞增性求解（先求出112的階乘，從大往小依次確定系數(shù)），也可以按一般進制數(shù)的取模方法求解。下面介

2、紹取模的方法：設n= An-1*(n-1)! + An-2*(n-2)! + . + A3 * 3! + A2 * 2! + A1 * 1!(由題意i!前面的系數(shù)Ai小于等于i，故0!只能用來表示0了，非零數(shù)用不上)n/2 = An-1*(n-1)!/2 + An-2*(n-2)!/2 + . + A3 * 3!/2 + A2（2!/21）-余數(shù)為A1在除3：n/(2*3) = An-1*(n-1)!/(2*3) + An-2*(n-2)!/(2*3) + . + A3-余數(shù)為A2依次類推可以求出所有的系數(shù)。求解代碼如下：/ans存相應的系數(shù)。i = 0;while(n>0)ansi =

3、 n%(i+2);n = n/(i+2);i +;接下來便是將結(jié)果輸出了：flag = 0;while(i>0)if(ansi-1 > 0)if(flag = 1) printf(" + ");else flag = 1 ;if(ansi-1>1)printf("%d*%d!",ansi-1,i);elseprintf("%d!",i);i -;比賽中一些問題：現(xiàn)場賽很多人都采用的是超遞增形式求解的，求解過程如果處理不好可能溢出整數(shù)范圍。這點需要注意。還有就是輸出問題，一些隊可能由于初次做ACM的題目，輸出遇到了不小

4、問題。不過總體說來題目還算比較簡單的。第D題 Drew line game本題來自國家集訓隊2007年原創(chuàng)題，作者為王棟。題目的大意為：在m*n的方格紙上畫線，一步可以連接相鄰兩點的連線，已畫過的線不能重復?？紤]先畫出閉路的人獲勝，和先畫出閉路的人輸兩種情況。求你的獲勝策略（你可以選擇先畫或者后畫）本題中規(guī)定了Bob先畫。analysis1.連接出現(xiàn)閉路獲勝我們假設連接ab后出現(xiàn)閉路當且僅當為連接時，a到b已經(jīng)有通路，雙方均應避免造成這種危險狀態(tài)。采取對稱畫法可以達到這個目的。若你畫完每一步圖形都是中心對稱得，那么就不會造成危險態(tài)；若你造成危險態(tài)，則根據(jù)對稱性，對方早已經(jīng)到

5、達危險態(tài)。當m與n同奇偶，紙的中心不在任意單位格子邊內(nèi)，故乙方獲勝。當m與n不同奇偶，對稱中心在一邊內(nèi)，先手第一部連接這條線，必勝。2.后連出閉路獲勝圖上有(m+1)*(n+1)個頂點時，當連線數(shù)少于l=(m+1)(n+1)-1時，必有兩個相鄰頂點a和b之間無通路，連接a b是活步。但如果連接l條線而尚未出現(xiàn)閉路。下一步無論怎么連必出現(xiàn)閉路。當m, n同為偶數(shù)，則l為偶數(shù)，乙必勝。反之，甲必勝。致勝策略：每步連接未通的相鄰點。第E題 Entry組合數(shù)學題目，分析方法有多種，下面介紹一種容易想到的方法：第1輛車有m種選擇方案，第2輛車可以有m+1種選擇方案。這是因為當它選擇與第1輛車相同的入口時

6、，可以選擇第1輛車在前的方案，還有就是它在第1輛車之前的方案。第3輛車則有m+2種方案，以此類推，可得：方案數(shù)為 m*(m+1)*(m+2)*(m+n-1)=(n+m-1)!/(m-1)!可以自己證明一下, 也可以參考組合數(shù)學書后面三個題目是USACO GOLD 里面的題目, 有一定的難度, 下面是USACO給出的英文解題報告,寫得比較詳細第F題 Face The Right WaySuppose we try to just lay out the cows one at time, from 1 to N. Initially we could start b

7、y putting each cow as far away from the previous ones as legal, but eventually this could lead to problems because the like and dislike constraints would be incompatible. So we'd like a way to prevent this up front. Suppose i < j < k. If i and k like each other and want to be at most A apa

8、rt, while j and k dislike each other and want to be at least B apart. Then i and j must be placed within A - B of each other. A similar deduction can be made for the mirror situation. If we loop downwards over all k (with inner loops over i and j), we can determine enough extra constraints that eith

9、er some of these constraints are directly contradictory, or else we can start placing cows without fear of running into a local contradiction (don't forget that the cows are in a fixed order, which introduces extra constraints). This algorithm is O(N3), which is too slow. Looking at an implement

10、ation of the above, one might see echos of Warshall's algorithm. In fact the problem can be done in terms of shortest paths. The constraints can all be written in the form Y <= X + c (for some cow positions X and Y and constant c). In the case of dislikes, c will be negative. If we have const

11、raints Y <= X + c and Z <= Y + d, then we get the new constraint Z <= X + (c + d) - and in general constraints can be chained together. The eventual goal is a constraint relating cow 1 and cow N (of the form cowN <= cow1 + C), so we want to consider the chain that yields the smallest con

12、stant - but that is just the shortest path. Because there are negative edges, we cannot use Dijkstra's algorithm. Instead, we use Bellman-Ford, which has O(N.(ML+MD) running time. Some extra tricks are needed to handle the two special cases: if there are any negative cycles in the graph then lay

13、out is impossible (Bellman-Ford has a mechanism to detect such cycles), otherwise if there is no path then cowN is unbounded. 第G題 Gold Balanced LineupConsider the partial sum sequence of each of the k features built by taking the sum of all the values up to position i. The problem is equiv

14、alent to:Given an array snk, find i,j, with the biggest separation for which sil-sjl is constant for all l. The problem is now to do this efficiently. Notice that sil-sjl being constant for all l is equivalent to sil-sjl=si1-sj1 for all l, which can be rearranged to become sil-si1=sjl-sj1 for all l.

15、 Therefore, we can construct another array ank where aij=sij-si1 and the goal is to find i and j with the biggest separation for which ail=ajl for all l. This can be done by sorting all the ai entries, which takes O(nklogn) time (although in practice rarely will all k elements be compared). Another

16、alternative is to go by hashing, giving an O(nk) solution. Both solutions are fairly straightforward once the final array is constructed.第H題 Ranking the CowsTo simplify notation, we use X->Y to denote the existence of a path of queries leading from a to b, from which we could deduce cow

17、 X is ranked higher than cow Y. An obvious upper bound for the number of queries to ask is the number of pairs of cows for which we have neither of X->Y and Y->X. It's slightly less obvious that this is also the lower bound. Suppose there exist a set of queries in which the relationship be

18、tween X and Y is not queried and from the original data we could not deduce X->Y or Y->X. Then we could answer the queries in a way so X and Y's ranking end up being adjacent to each other (by making all other cows rank either lower or higher than both of X and Y). In such a case, it's clear a compar