简单的测试题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%的分数