简单的测试题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只鸡($C\le100,000$),编号为$1\ldots C$, 而且,每只鸡i只有恰好在时间$T_i$时才会愿意帮助牛们。

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

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

输入格式(helpcross.in)

第一行包含整数C和N

接下来C行包含$T_1\ldots T_C$

接下来N行每行包含$A_j$和$B_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,N\le10$。
  • 对于60%的数据,$C,N\le500$。
  • 对于100%的数据,$C,N\le100,000$,$0\le T_i,A_j,B_j\le1,000,000,000$,不保证$T_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个正整数($N\le262,144$),每个整数都在范围$1\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%的数据,$N\le20$。
  • 对于65%的数据,$N\le248$。
  • 对于100%的数据,$N\le262,144$。

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

题目描述

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

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

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

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

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

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

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

考虑一个当树为一条链时的例子,并且只有一个$T_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号田地,三个整数$P_i,C_i,M_i$

接下来K行包含$T_i$

输出格式(bottleneck.out)

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

输入样例

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

输出样例

1
25

数据范围

  • 对于30%的数据,$T_i\le2,000$
  • 对于70%的数据,$N,K\le2,000$
  • 对于100%的数据,$N,K\le100,000,T_i\le1,000,000,000$

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

本题为原创题

题目描述

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

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

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

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

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

输入格式(gpsduel.in)

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

接下来M行,每行四个整数$A_i,B_i,T1_i,T2_i$,表示一条道路

接下来W行,每行四个整数$A_i,B_i,T1_i,T2_i$,表示一个虫洞

输出格式(gpsduel.out)

三个整数$d_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,$d_1$=-10+5-100=-105。

在第二套GPS系统中,从城镇1到城镇6的最短路为1-3-5-6,$d_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%的数据,$N\le2,000$,$M,W\le10,000$
  • 另有40%的数据,数据随机生成
  • 对于100%的数据,$N,W\le100,000$,$M\le500,000$,$T_i\le10,000,000$

部分分

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