NOIP2011复赛模拟卷(一)

《NOIP2011复赛模拟卷(一)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NOIP2011复赛练习卷（一）1、最优贸易(trade.pas/c/cpp)【问题描述】C国有n个大城市和m条道路，每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到C国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价

2、赚回一点旅费。设C国n个城市的标号从1~n，阿龙决定从1号城市出发，并最终在n号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有n个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来C国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。假设C国有5个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。假设1~n号城市的水晶球价格分别为4，3

3、，5，6，1。阿龙可以选择如下一条线路：1->2->3->5，并在2号城市以3的价格买入水晶球，在3号城市以5的价格卖出水晶球，赚取的旅费数为2。阿龙也可以选择如下一条线路1->4->5->4->5，并在第1次到达5号城市时以1的价格买入水晶球，在第2次到达4号城市时，以6的价格卖出水晶球，赚取的旅费数为5。现在给出n个城市的水晶球价格、m条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）），请你告诉阿龙，他最多能赚取多少旅费。【输入】(trade.in)第1行：包含2个正整数n和m，中间用一个空格隔开，分别表示城市的数目和道路的数目。第2行：n个

4、正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这n个城市的商品价格。接下来m行：每行有3个正整数x、y、z，每两个整数之间用一个空格隔开。如果z=1，表示这条道路是城市x到城市y之间的单向道路；如果z=2，表示这条道路为城市x和城市y之间的双向道路。【输出】(trade.out)1行：包含1个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出0。5【输入输出样例】trade.intrade.out555435611211412323514525【数据范围】输入数据保证1号城市可以到达n号城市。10%的数据：1≤n≤6。30%的数据：1≤n≤100。50%

5、的数据：不存在一条旅游路线，可以从一个城市出发，再回到这个城市。100%的数据：1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市水晶球价格≤100。2、Elaxia的路线(travel.pas/c/cpp)【问题描述】最近，Elaxia和Warren的关系特别好，他们很想整天在一起，但是，大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。Elaxia和Warren每天都要奔波于宿舍和实验室之间，他们希望在节约时间的前提下，一起走的时间尽可能长。现在，已知的是Elaxia和Warren所在的宿舍和实验室的编号以及学校的地图，地

6、图上有N个路口、M条路，经过每条路都需要一定的时间。具体地说，就是要求无向图中，两对点之间最短路的最长公共路径。【输入】(travel.in)第1行：两个整数N和M（含义如题中所述）。第2行：4个整数x1、y1、x2、y2(1<=x1<=N,1<=y1<=N,1<=x2<=N,1<=y2<=N)，分别表示Elaxia的宿舍和实验室及Warren的宿舍和实验室的标号（两对点分别为x1,y1,x2,y2）。接下来的M行：每行3个整数u、v、L(1<=u<=N,1<=v<=N,1<=L<=10000)，表示u和v之间有一条路，经过这条路所需的时间为L。【输出】(trave

7、l.out)1行：一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。【输入输出样例】travel.intravel.out910167812125223334239545346447235581791【数据规模】30%的数据：N<=100;60%的数据：N<=1000;100%的数据：N<=1500，输入数据保证没有重边和自环。3、间谍网络(age.pas/c/cpp)【问题描述】由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手