假设车的容量是C

1、第A题 A Tough Trip假设车的容量是C, 允许在起点加油 n 次, 那么车的最大行程就是 C + C/3 + C/5 + . + C/(2*n - 1), 有兴趣的同学可以证明一下.第B题 Billiard bounces 简单题目。注意球的初始位置在桌的中心。将球的速度分解成两个方向，分别求出两个方向的碰撞次数，相加就可以了。第C题 A Simple Problem本题题意简单，将一个数用阶乘的形式表示出来。算法也比较容易，可以按一般的超递增性求解（先求出112的阶乘，从大往小依次确定系数），也可以按一般进制数的取模方法求解。下面介

2、绍取模的方法：设n= An-1*(n-1)! + An-2*(n-2)! + . + A3 * 3! + A2 * 2! + A1 * 1!(由题意i!前面的系数Ai小于等于i，故0!只能用来表示0了，非零数用不上)n/2 = An-1*(n-1)!/2 + An-2*(n-2)!/2 + . + A3 * 3!/2 + A2（2!/21）-余数为A1在除3：n/(2*3) = An-1*(n-1)!/(2*3) + An-2*(n-2)!/(2*3) + . + A3-余数为A2依次类推可以求出所有的系数。求解代码如下：/ans存相应的系数。i = 0;while(n>0)ansi =

3、 n%(i+2);n = n/(i+2);i +;接下来便是将结果输出了：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 -;比赛中一些问题：现场赛很多人都采用的是超递增形式求解的，求解过程如果处理不好可能溢出整数范围。这点需要注意。还有就是输出问题，一些队可能由于初次做ACM的题目，输出遇到了不小

4、问题。不过总体说来题目还算比较简单的。第D题 Drew line game本题来自国家集训队2007年原创题，作者为王栋。题目的大意为：在m*n的方格纸上画线，一步可以连接相邻两点的连线，已画过的线不能重复。考虑先画出闭路的人获胜，和先画出闭路的人输两种情况。求你的获胜策略（你可以选择先画或者后画）本题中规定了Bob先画。analysis1.连接出现闭路获胜我们假设连接ab后出现闭路当且仅当为连接时，a到b已经有通路，双方均应避免造成这种危险状态。采取对称画法可以达到这个目的。若你画完每一步图形都是中心对称得，那么就不会造成危险态；若你造成危险态，则根据对称性，对方早已经到

5、达危险态。当m与n同奇偶，纸的中心不在任意单位格子边内，故乙方获胜。当m与n不同奇偶，对称中心在一边内，先手第一部连接这条线，必胜。2.后连出闭路获胜图上有(m+1)*(n+1)个顶点时，当连线数少于l=(m+1)(n+1)-1时，必有两个相邻顶点a和b之间无通路，连接a b是活步。但如果连接l条线而尚未出现闭路。下一步无论怎么连必出现闭路。当m, n同为偶数，则l为偶数，乙必胜。反之，甲必胜。致胜策略：每步连接未通的相邻点。第E题 Entry组合数学题目，分析方法有多种，下面介绍一种容易想到的方法：第1辆车有m种选择方案，第2辆车可以有m+1种选择方案。这是因为当它选择与第1辆车相同的入口时

6、，可以选择第1辆车在前的方案，还有就是它在第1辆车之前的方案。第3辆车则有m+2种方案，以此类推，可得：方案数为 m*(m+1)*(m+2)*(m+n-1)=(n+m-1)!/(m-1)!可以自己证明一下, 也可以参考组合数学书后面三个题目是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