简单的测试题2

题目来源或改编自USACO月赛,顺序与难度无关。

题目概述

项目名称 穿越马路 2048 瓶颈 GPS的决斗
文件名 helpcross.* 2048.* bottleneck.* gpsduel.*
时间限制 1s 2s 1s 3s
空间限制 512MB 512MB 512MB 512MB
优化选项 -O2
测试点数量 10 20 10 10
测试点分数 10 5 10 10
比较方式 SPJ 全文 全文 SPJ
部分分

注意事项

  1. 请注意题目的数据大小,根据情况适当地使用输入/输出优化。
  2. 数据范围中,如果没有说明,前面的数据满足后面的要求
  3. 对于有部分分的题目,如果你只做了其中一问,也要按照格式要求输出所有内容;否则无法保证得分。

1.穿越马路(helpcross.c/cpp/pas)

背景描述

农夫约翰的牛们正在尝试去学会高效地穿越马路。熟知经典的笑话“为什么鸡要过马路?”,他们想到鸡一定是过马路的专家,便动身寻找能够帮助它们的鸡。

题目描述

牛们发现,鸡是一种特别繁忙的动物,并且只有一定的时间来帮助它们。农场上共有C只鸡(C100,000C\le100,000),编号为1C1\ldots C, 而且,每只鸡i只有恰好在时间TiT_i时才会愿意帮助牛们。

而从不慌张的牛们,有更加灵活的时间安排。农场上共有N只牛(N100,000N\le100,000),也被编号为1N1\ldots N,牛j在时间AjA_jBjB_j之间可以穿过马路。每只牛j会愿意找到一只鸡i来帮助它穿过马路;为了使它们的时间表不冲突,i和j必须满足AjTiBjA_j\le T_i\le B_j

如果每只牛可以与至多一只鸡结伴,并且每只鸡与至多一只牛,请帮助计算可构造的牛-鸡配对数量的最大值,以及任意一种配对方案(有SPJ)。

输入格式(helpcross.in)

第一行包含整数C和N

接下来C行包含T1TCT_1\ldots T_C

接下来N行每行包含AjA_jBjB_j

输出格式(helpcross.out)

第一行包含最大的可行牛-鸡配对数Ans

接下来Ans行每行包含i和j

输入样例

1
2
3
4
5
6
7
8
9
10
5 4
7
8
6
2
9
2 5
4 9
0 3
8 13

输出样例

1
2
3
4
3
5 2
2 4
4 3

显然,配对方案不唯一。

数据范围

  • 对于30%的数据,C,N10C,N\le10
  • 对于60%的数据,C,N500C,N\le500
  • 对于100%的数据,C,N100,000C,N\le100,0000Ti,Aj,Bj1,000,000,0000\le T_i,A_j,B_j\le1,000,000,000,不保证Ti,Aj,BjT_i,A_j,B_j唯一。

部分分

  • 如果Ans正确,得到测试点30%的分数
  • 如果方案正确,得到测试点70%的分数

你可以使用sample目录下的spj.exe来计算你的样例得分,格式为spj.exe helpcross.in helpcross.ans helpcross.out。spj.exe将你的得分显示在stdout,范围为0~1。

2.2048(2048.c/cpp/pas)

背景描述

奶牛贝西喜欢在它的手机上下载游戏来玩,尽管它发现它的蹄子太大,在小的触摸屏上显得十分笨拙。

题目描述

它对它正在玩的一个游戏尤其感兴趣,这个游戏类似于一维的2048。游戏一开始有N个正整数(N262,144N\le262,144),每个整数都在范围1401\ldots40中。在一步中,贝西可以选择相邻的两个相同的数,并把这两个数替换成一个值大1的数(例如,它可以把两个相邻的7替换成一个8)。

游戏的目标是最大化游戏结束时剩下的最大数。请帮助贝西来得到尽可能高的分数,不要求游戏结束时只剩下一个数。

输入格式(2048.in)

第一行包含N

接下来N行,每行一个整数,表示游戏开始时的N个数

输出格式(2048.out)

请输出贝西最大能得到的数

输入样例

1
2
3
4
5
4
1
1
1
2

输出样例

1
3

样例解释

在这个样例中,贝西首先合并第2个1和第3个1,得到数列1 2 2.然后它把2个2合并成1个3.注意合并前面的2个2不是最优的。

数据范围

  • 对于20%的数据,N20N\le20
  • 对于65%的数据,N248N\le248
  • 对于100%的数据,N262,144N\le262,144

3.瓶颈(bottleneck.c/cpp/pas)

题目描述

农夫约翰正在聚集奶牛们。他的牧场包含了N个田地(N100,000N\le100,000),编号1N1\ldots N。这些田地被N-1条单向道路连接,从任何一个田地都可以到达1号田地。也就是说,这些田地和道路组成了一颗树

对于每个田地i(i>1),都有一条单向道路通往PiP_i(Pi1NP_i\in1\ldots N),并且当前包含了CiC_i只奶牛(Ci1,000,000,000C_i\le1,000,000,000)。在单位时间内,只有不超过MiM_i只奶牛(Mi1,000,000,000M_i\le1,000,000,000)能从田地i到达田地PiP_i

农夫约翰想让所有的奶牛都集中到1号田地(每个田地都能容纳无限只奶牛)。有以下规则:

  • 任何给定的奶牛都可以在一个单位时间内通过多条道路,但是必须满足每条道路的上限MiM_i
  • 奶牛从不离开1号田地。

换句话说,在每个单位时间,每只奶牛可以选择其中之一:

  • 留在它当前的田地
  • 经过若干条道路向1号田地移动,只要不超过每条道路的瓶颈

农夫约翰想知道有多少只奶牛可以在特定的时刻到达1号田地。特别的,他有一个包含K个(K100,000K\le100,000)时间TiT_i(Ti1,000,000,000T_i\le1,000,000,000)的列表,并且他想知道,对于列表中的每个TiT_i,如果采用最优策略最多能有多少只奶牛在这个时刻到达1号田地。

考虑一个当树为一条链时的例子,并且只有一个Ti=5T_i=5,奶牛的分布如下:

1
2
3
Locn:	1---2---3---4	<-- 田地的标号
C_i: 0 1 12 12 <-- 当前奶牛的数量
M_i: 5 8 3 <-- 道路的限制,1号田地没有限制

以下是方案,目标是把牛移动到1号田地:

1
2
3
4
5
6
7
Tree:	1---2---3---4
t=0 0 1 12 12 <-- 初始状态
t=1 5 4 7 9 <-- 1号田地有来自2号和3号田地的牛
t=2 10 7 2 6
t=3 15 7 0 3
t=4 20 5 0 0
t=5 25 0 0 0

答案是25:所有的25只牛可以在时刻t=5到达1号田地。这也是样例的解释。

输入格式(bottleneck.in)

第一行两个整数N和K

第2到N行,第i行描述了i号田地,三个整数Pi,Ci,MiP_i,C_i,M_i

接下来K行包含TiT_i

输出格式(bottleneck.out)

K行包含在时刻TiT_i到达1号田地的牛数量

输入样例

1
2
3
4
5
4 1
1 1 5
2 12 7
3 12 3
5

输出样例

1
25

数据范围

  • 对于30%的数据,Ti2,000T_i\le2,000
  • 对于70%的数据,N,K2,000N,K\le2,000
  • 对于100%的数据,N,K100,000,Ti1,000,000,000N,K\le100,000,T_i\le1,000,000,000

4.GPS的决斗(gpsduel.c/cpp/pas)

本题为原创题

题目描述

农夫约翰把农场搬到了一个遥远的地方,这个地方有N个城镇(N100,000N\le100,000),M条双向道路把这些城镇连接起来(M500,000M\le500,000)。每一条道路i连接AiA_iBiB_i(Ai,Bi1NA_i,B_i\in1\ldots N),可以在TiT_i的时间内(0Ti10,000,0000\le T_i\le10,000,000)从AiA_i到达BiB_i或从BiB_i到达AiA_i。可能存在重边或自环。

有趣的是,这里还有W个虫洞(W100,000W\le100,000)连接城镇。第i个虫洞连接AiA_iBiB_i,通过后时间将加上TiT_i(Ti10,000,000\left\vert T_i\right\vert\le10,000,000),注意TiT_i可以是负数,因此可以通过虫洞回到过去。为了安全考虑,虫洞有以下限制:

  • 只能单向通行,即只能从AiA_i到达BiB_i
  • 保证没有任何路径从BiB_i到达AiA_i,即不可能从BiB_i经过一些道路和虫洞到达AiA_i

不幸的是,由于某些原因,农夫约翰无法找到当地确切的地图。但是,他有两套GPS系统,这两套系统中的道路和虫洞是一致的,但是TiT_i却不一定相同。具体的,两套系统中分别为T1i,T2iT1_i,T2_i

农夫约翰想要从城镇S到达城镇T,请计算出在两套系统中的最短路径长度d1,d2d_1,d_2。然而,他在路上会同时打开两套系统,因此,如果他从某个城镇X到Y走的不在一套系统认为的从X到T的最短路上,那么就会得到一次警告。如果走的路不是两套系统认为的最短路,则会得到两次警告。农夫约翰还想知道从城镇S到城镇T最少要得到的警告次数cnt。

输入格式(gpsduel.in)

第一行五个整数N,M,W,S,T

接下来M行,每行四个整数Ai,Bi,T1i,T2iA_i,B_i,T1_i,T2_i,表示一条道路

接下来W行,每行四个整数Ai,Bi,T1i,T2iA_i,B_i,T1_i,T2_i,表示一个虫洞

输出格式(gpsduel.out)

三个整数d1,d2,cntd_1,d_2,cnt

如果不存在从S到T的路径,对于d输出"inf"(不包含引号),对于cnt输出-1.

输入样例

1
2
3
4
5
6
7
6 3 3 1 6
1 2 5 10
3 4 5 10
5 6 10 5
1 3 -10 -100
3 5 -100 -10
4 6 -100 -10

输出样例

1
-105 -105 1

样例解释

在第一套GPS系统中,从城镇1到城镇6的最短路为1-3-4-6,d1d_1=-10+5-100=-105。

在第二套GPS系统中,从城镇1到城镇6的最短路为1-3-5-6,d2d_2=-100-10+5=-105。

农夫约翰按照1-3-4-6的路线,1-3在两套系统中都没有警告。而3-4则会得到第二套系统的警告,因为它认为3-4不在3-6的最短路上。而4-6也不会得到警告,因为在两套系统中4-6都在4-6的最短路上。

也就是说,到达一个城镇后,系统会重新计算当前城镇到城镇T的最短路。

数据范围

  • 对于30%的数据,N2,000N\le2,000M,W10,000M,W\le10,000
  • 另有40%的数据,数据随机生成
  • 对于100%的数据,N,W100,000N,W\le100,000M500,000M\le500,000Ti10,000,000T_i\le10,000,000

部分分

  • 如果d1,d2d_1,d_2都正确,得到测试点30%的分数
  • 如果cnt正确,得到测试点70%的分数