描述 Description
魔术师的桌子上有 n 个杯子排成一行,编号为 1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花费 c_ij 元,魔术师就会告诉你杯子 i,i+1,…,j 底下藏有球的总数的奇偶性。
采取最优的询问策略,你至少需要花费多少元,才能保证猜出哪些杯子底下藏着球?
Read More魔术师的桌子上有 n 个杯子排成一行,编号为 1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花费 c_ij 元,魔术师就会告诉你杯子 i,i+1,…,j 底下藏有球的总数的奇偶性。
采取最优的询问策略,你至少需要花费多少元,才能保证猜出哪些杯子底下藏着球?
Read More奶牛贝茜被雇去建设 N(2≤N≤1000) 个牛棚间的互联网.她已经勘探出 M(1≤M≤20000) 条可建的线路,每条线路连接两个牛棚,而且会苞费 C(1≤C≤100000).农夫约翰吝啬得很,他希望建设费用最少甚至他都不想给贝茜工钱. 贝茜得知工钱要告吹,决定报复.她打算选择建一些线路,把所有牛棚连接在一起,让约翰花费最大.但是她不能造出环来,这样约翰就会发现.
Read MoreFarmer John 变得非常懒, 他不想再继续维护供奶牛之间供通行的道路. 道路被用来连接 N (5 <= N <= 10,000)个牧场, 牧场被连续地编号为 1..N. 每一个牧场都是一个奶牛的家. FJ 计划除去 P(N-1 <= P <= 100,000)条道路中尽可能多的道路, 但是还要保持牧场之间的连通性. 你首先要决定那些道路是需要保留的 N-1 条道路. 第 j 条双向道路连接了牧场 S_j 和 E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j), 而且走完它需要 L_j (0 <= L_j <= 1,000)的时间. 没有两个牧场是被一条以上的道路所连接. 奶牛们非常伤心, 因为她们的交通系统被削减了. 你需要到每一个奶牛的住处去安慰她们. 每次你到达第 i 个牧场的时候 (即使你已经到过), 你必须花去 C_i (1 <= C_i <= 1,000) 的时间和奶牛交谈. 你每个晚上都会在同一个牧场 (这是供你选择的) 过夜, 直到奶牛们都从悲伤中缓过神来. 在早上起来和晚上回去睡觉的时候, 你都需要和在你睡觉的牧场的奶牛交谈一次. 这样你才能完成你的交谈任务. 假设 Farmer John 采纳了你的建议, 请计算出使所有奶牛都被安慰的最少时间. 对于你前 10 次的提交, 你的程序会在一部分正式的测试数据上运行, 并且返回运行的结果.
Read MoreThe cows have run out of hay, a horrible event that must be remedied immediately. Bessie intends to visit the other farms to survey their hay situation. There are N (2 <= N <= 2,000) farms (numbered 1..N); Bessie starts at Farm 1. She’ll traverse some or all of the M (1 <= M <= 10,000) two-way roads whose length does not exceed 1,000,000,000 that connect the farms. Some farms may be multiply connected with different length roads. All farms are connected one way or another to Farm 1. Bessie is trying to decide how large a waterskin she will need. She knows that she needs one ounce of water for each unit of length of a road. Since she can get more water at each farm, she’s only concerned about the length of the longest road. Of course, she plans her route between farms such that she minimizes the amount of water she must carry. Help Bessie know the largest amount of water she will ever have to carry: what is the length of longest road she’ll have to travel between any two farms, presuming she chooses routes that minimize that number? This means, of course, that she might backtrack over a road in order to minimize the length of the longest road she’ll have to traverse.
牛们干草要用完了!贝茜打算去勘查灾情.
有 N(2≤N≤2000) 个农场,M(≤M≤10000) 条双向道路连接着它们,长度不超过 109.每一个农场均与农场 1 连通.贝茜要走遍每一个农场.她每走一单位长的路,就要消耗一单位的水.从一个农场走到另一个农场,她就要带上数量上等于路长的水.请帮她确定最小的水箱容量.也就是说,确定某一种方案,使走遍所有农场通过的最长道路的长度最小,必要时她可以走回头路.
Read More国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络;每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。
任意两个配备了一条卫星电话线路的哨所(两边都拥有卫星电话)均可以通话,无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D,这是受收发器的功率限制。收发器的功率越高,通话距离 D 会更远,但同时价格也会更贵。
收发器需要统一购买和安装,所以全部哨所只能选择安装一种型号的收发器。换句话说,每一对哨所之间的通话距离都是同一个 D。
你的任务是确定收发器必须的最小通话距离 D,使得每一对哨所之间至少有一条通话路径(直接的或者间接的)。
Read More