2010年12月 银组 题目翻译及解法

《2010年12月 银组 题目翻译及解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2010年12月银组题目翻译及解法USACO2010年十二月银组题目翻译1、送苹果贝西有两个又香又脆的红苹果要送给她的两个朋友。当然她可以走的C（1<=C<=200000）条“牛路”都被包含在一种常用的图中，包含了P（1<=P<=100000）个牧场，分别被标为1..P。没有“牛路”会从一个牧场又走回它自己。“牛路”是双向的，每条牛路都会被标上一个距离。最重要的是，每个牧场都可以通向另一个牧场。每条牛路都连接着两个不同的牧场P1_i和P2_i（1<=P1_i,p2_i<=P)，距离为D_i。所有“牛路”的距离之和不大于2

2、000000000。现在，贝西要从牧场PB开始给PA_1和PA_2牧场各送一个苹果（PA_1和PA_2顺序可以调换），那么最短的距离是多少呢？当然，PB、PA_1和PA_2各不相同。这里有一个样例：322[1]-----[2]------[3]-----[4]//7/43/2//[5]-----[6]------[7]12如果贝西从牧场5开始，把苹果送到牧场1和4，那么她的最佳路径是：5->6->7->4*->3->2->1*总长度12。问题名：apple输入格式：第一行：五个整数：C,P,PB,PA_1,P

3、A_2。第二行到第C+1行：第i+1行表示第i个“牛路”，包含三个整数：P1_i，P2_i，D_i。样例输入（apple.in）：97514517672472561524432123322263输出格式：贝西送苹果最佳路径的总长。样例输出（apple.out）：122、宝箱贝西和伯尼找到了一个装满了金币的宝箱！但是，作为奶牛，他们不能随便进入一家商店去买东西。所以他们决定去用这些金币玩一个游戏。这里有N（1<=N<=5000）个硬币，每个都有一个价值C_i（1<=C_i<=5000）。这些硬币被摆成了一行。贝西和伯尼每人

4、一回合。到了一只奶牛的回合时，他就要拿走最左边或者最右边的硬币。当没有硬币时，游戏结束。贝西和伯尼都想要使自己拿到的金币价值尽量高，贝西先拿。现在贝西想要你帮帮她，算出她最多可以拿多少钱（伯尼也会尽量取到最优）。这里有一个样例：30251035那么最优方案是这样的：玩家取哪边金币价值贝西总钱数伯尼总钱数剩下的金币序列贝西右35350302510伯尼左3035302510贝西左25603010伯尼右106040--贝西最多可以拿到60。问题名：treasure输入格式：第一行：一个正整数N。第二到N+1行：第i+1行表示C

5、_i样例输入（treasure.in）：430251035输出格式：一个整数，表示贝西能拿到的最大价值。样例输出（treasure.out）：603、槽游戏农夫约翰和贝西又在玩游戏。这个游戏需要很多个槽。农夫约翰在谷仓里藏起来了N（1<=N<=20）个槽，并且他已经把其中的一些装上了食物。贝西以“在这个表里（表由贝西提供）有多少个槽里有食物？”的形式问了M（1<=M<=100）个问题。现在，贝西想知道，哪几个槽里有食物？这里有一个样例：（1）在第一个槽里有多少个槽里有食物？——1个（2）在第二个和第三个槽里有多少个槽里有

6、食物？——1个（3）在第一个和第四个槽里有多少个槽里有食物？——1个（4）在第三个和第四个槽里有多少个槽里有食物？——1个从第一个问题可以知道，第一个槽是有食物的。从第二个问题可以知道，第四个槽是没有食物的。从第三个问题可以知道，第三个槽是有食物的。从第四个问题可以知道，第二个槽是没有食物的。问题名：trough输入格式：第一行：两个整数，N和M。第二到第M+1行：表示贝西的M个问题，前N个字符表示贝西提供的表第i个字符如果是“0”，那么第i个槽不包括在表中。如果是“1”，那么第i个槽包括在表中。最后一个数表示这个问题的

7、答案。样例输入4410001011011001100111输出格式：第i个字符如果是“0”，那么第i个槽没有食物。如果是“1”，那么第i个槽有食物。如果结果自相矛盾，那么输出“IMPOSSIBLE”，如果没有足够的条件，那么输出“NOTUNIQUE”。样例输出（trough.out）：1010USACO2010年十二月银组题目解法1、送苹果这题一看就知道是最短路。题解上说是用邻接表的Dijsktra，算两次，答案为min（D（PB，PA_1），D（PB，PA_2））+D（PA_1，PA_2)。但是我写的SPFA最后两个点

8、超时了，我看到那上面交的SPFA程序最后两个点无一例外地都超时了，是不是卡了SPFA？2、宝箱不算太明显的DP。下面是题解：我们让s（i，j）代表从第i个金币一直到第j个金币的价值总和，b（i，j）代表如果在第i个金币到第j个金币这一段进行游戏，贝西能得到的最大价值。（阶段确实很难想）。那么很容易写出DP式：b(i,