①
【USACO】数三角形
时间限制：1000MS 内存限制：65536K
【试题描述】
在一只大灰狼偷偷潜入Farmer Don的牛群被群牛发现后，贝西现在不得不履行着她站岗的职责。
从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习，防止她睡着了。
想象牧场是一个X，Y平面的网格。她将N只奶牛标记为1…N (1 <= N <= 100,000)，每只奶牛的坐标为 X_i,Y_i (-100,000 <= X_i <= 100,000;-100,000 <= Y_i <= 100,000; 1 <= i <=N)。然后她脑海里想象着所有可能由奶牛构成的三角形。如果一个三角形完全包含了原点(0,0)，那么她称这个三角形为“黄金三角形”。原点不会落在任何一对奶牛的连线上。另外，不会有奶牛在原点。 给出奶牛的坐标，计算出有多少个“黄金三角形”。
顺便解释一下样例，考虑五只牛，坐标分别为(-5,0), (0,2), (11,2), (-11,-6), (11,-5)。 下图是由贝西视角所绘出的图示。 ............|............
............*..........*.
............|............
-------*----+------------
............|............
............|............
............|............
............|............
............|..........*.
.*..........|............
............|............
所有十个三角形如图下所示：
通过观察，其中有5个构成了“黄金三角形”
【输入描述】
* 第一行:一个整数: N
* 第2到第N+1行: 每行两个整数X_i，Y_i，表示每只牛的坐标
【输出描述】
* 第一行: 一行包括一个整数，表示“黄金三角形的数量”
【输入样例】
5 -5 0
0 2 11 2 -11 -6 11 -5
【输出样例】
5
【试题来源】
USACO 2010 Open Gold
②
【USACO】冲浪
时间限制：1000MS 内存限制：65536K
【试题描述】
受到秘鲁的马丘比丘的新式水上乐园的启发，Farmer John决定也为奶牛们建一个水上乐园。当然，它最大的亮点就是新奇巨大的水上冲浪。
超级轨道包含 E (1 <= E <=150,000)条小轨道连接着V (V <= 50,000)个水池，编号为1..V。每个小轨道必须按照特定的方向运行，不能够反向运行。奶牛们从1号水池出发，经过若干条小轨道，最终到达V号水池。每个水池(除了V号和1号之外，都有至少一条小轨道进来和一条小轨道出去，并且，一头奶牛从任何一个水池到达V号水池。最后，由于这是一个冲浪，从任何一个水池出发都不可能回到这个水池)
每条小轨道从水池P_i到水池Q_i (1 <= P_i <= V; 1<= Q_i <= V; P_i != Q_i)，轨道有一个开心值F_i (0 <= F_i <= 2,000,000,000)，Bessie总的开心值就是经过的所有轨道的开心值之和。
Bessie自然希望越开心越好，并且，她有足够长的时间在轨道上玩。因此，她精心地挑选路线。但是，由于她是头奶牛，所以，会有至多K (1 <= K <= 10)次的情况，她无法控制，并且随机从某个水池选择了一条轨道(这种情况甚至会在1号水池发生)
如果Bessie选择了在最坏情况下，最大化她的开心值，那么，她在这种情况下一次冲浪可以得到的最大开心值是多少？
在样例中，考虑一个超级轨道，包含了3个水池(在图中用括号表示)和4条小轨道，K的值为1(开心值在括号外表示出来，用箭头标识)
[1]
/ \\
5 -> / \\ <- 9
/ \\
[2]---3---[3]
\\__5__/
她总是从1号水池出发，抵达3号水池。如果她总是可以自己选择，就是不会发生不能控制的情况她可以选择从1到2(这条轨道开心值为5)，再从2到3(开心值为5)，总的开心值为5+5=10。但是，如过她在1号水池失去控制，直接到了3，那么开心值为9，如果她在2号水池失去控制，她总的开心值为8。
Bessie想要找到最大化开心值的方案，可以直接从1到3，这样，如果在1号水池失去控制，这样，她就不会在2号水池失去控制了，就能够得到10的开心值。因此，她的开心值至少为9
【输入描述】
* 第一行: 三个用空格隔开的整数: V, E, 和 K
* 第2到第E+1行: 第i+1行包含三个用空格隔开的整数: P_i, Q_i, and F_i
【输出描述】
* 第一行: 一个整数表示在最坏情况下最大化的开心值
【输入样例】
3 4 1 2 3 5 1 2 5 1 3 9 2 3 3
【输出样例】
9
【试题来源】
USACO 2010 Open Gold
③
【USACO】奶牛大集会
时间限制：1000MS 内存限制：65536K
【试题描述】
Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。
每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住者C_i(0 <= C_i <= 1,000)只奶牛。
在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么
总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。 考虑一个由五个农场组成的国家，分别由长度各异的道路连接起来。在所有农场中，3号和4号没有奶牛居住。
1 3 4 5
@--1--@--3--@--3--@[2]
[1] |
2
|
@[1]
2
Bessie可以在五个农场中的任意一个举办集会，下面就是在每个位置举办集会的不方便值的统计表。
集会地点 ----- 不方便程度 ------
B1 B2 B3 B4 B5 Total
1 0 3 0 0 14 17
2 3 0 0 0 16 19
3 1 2 0 0 12 15
4 4 5 0 0 6 15
5 7 8 0 0 0 15
如果Bessie在农场1举办集会，那么每个农场各自的不方便值分别是 农场 1 0 -- 到达不需要时间!
农场 2 3 -- 总的距离是 2+1=3 x 1 奶牛 = 3
农场 3 0 -- 没奶牛!
农场 4 0 -- 没奶牛!
农场 5 14 -- 总的距离是 3+3+1=7 x 2 奶牛 = 14
因此，总的不方便值是17。
最小的不方便值是15，当在3号，4号或者5号农场举办集会的时候。
【输入描述】
* 第一行：一个整数N
* 第二到N+1行：第i+1行有一个整数C_i
* 第N+2行到2*N行，第i+N+1行为3个整数：A_i,B_i和L_i。
【输出描述】
* 第一行：一个值，表示最小的不方便值。
【输入样例】
5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 3
【输出样例】
15
【试题来源】
USACO 2010 March Gold
④
植物大战僵尸
【问题描述】
Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏。Plants（植物）和Zombies（僵尸）是游戏的主角，其中Plants防守，而Zombies进攻。该款游戏包含多种不同的挑战系列，比如Protect Your Brain、Bowling等等。其中最为经典的，莫过于玩家通过控制Plants来防守Zombies的进攻，或者相反地由玩家通过控制Zombies对Plants发起进攻。
现在，我们将要考虑的问题是游戏中Zombies对Plants的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色，Plants和Zombies，每个Plant有一个攻击位置集合，它可以对这些位置进行保护；而Zombie进攻植物的方式是走到植物所在的位置上并将其吃掉。 游戏的地图可以抽象为一个N行M列的矩阵，行从上到下用0到N–1编号，列从左到右用0到M–1编号；在地图的每个位置上都放有一个Plant，为简单起见，我们把位于第r行第c列的植物记为Pr, c。 Plants分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个Plant，定义Score和Attack如下： Score[Pr, c]
Zombie击溃植物Pr, c可获得的能源。若Score[Pr, c]为
非负整数，则表示击溃植物Pr, c可获得能源Score[Pr, c]，若为负数表示击溃Pr, c需要付出能源 -Score[Pr, c]。
Attack[Pr, c] 植物Pr, c能够对Zombie进行攻击的位置集合。 Zombies必须从地图的右侧进入，且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说，对于第
r行的进攻，Zombies必须首先攻击Pr, M-1；若需要对Pr, c（0≤c Zombies的目标是对Plants的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套Zombies的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。 【输入文件】 输入文件pvz.in的第一行包含两个整数N, M，分别表示地图的行数和列数。 接下来N×M行描述每个位置上植物的信息。第r×M + c + 1行按照如下格式给出植物Pr, c的信息：第一个整数为Score[Pr, c], 第二个整数为集合Attack[Pr, c]中的位置个数w，接下来w个位置信息（r’, c’），表示Pr, c可以攻击位置第r’ 行第c’ 列。 【输出文件】 输出文件pvz.out仅包含一个整数，表示可以获得的最大能源收入。 注意，你也可以选择不进行任何攻击，这样能源收入为0。 【输入样例】 3 2 10 0 20 0 -10 0 -5 1 0 0 100 1 2 1 100 0 【输出样例】 25 【样例说明】 在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。 一个方案为，首先进攻P1,1, P0,1，此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。 【大致数据规模】 约20%的数据满足1 ≤ N, M ≤ 5； 约40%的数据满足1 ≤ N, M ≤ 10； 约100%的数据满足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000 因篇幅问题不能全部显示，请点此查看更多更全内容