冲刺NOIP2011模拟试题11

1、多米诺骨牌（domino.pas）

Jzabc对多米诺骨牌有很大的兴趣，然而他的骨牌比较特别，只有黑色的和白色的两种。他觉得如果存在连续三个骨牌是同一种颜色，那么这个骨牌排列便是不美观的。现在他有n个骨牌要来排列，他想知道不美观的排列的个数。由于数字较大，数学不好的他不会统计，所以他请你来帮忙。希望你在一秒内求出不美观的排列的个数。 【输入】

只有一个正整数，即要排列的骨牌个数 【输出】

一个数，即不美观的排列个数 【样例输入】 4

【样例输出】 6

【样例解释】

有四种不美观的排列

黑黑黑黑 白白白白 黑黑黑白 白白白黑 黑白白白 白黑黑黑 【数据范围】

20%的数据 n≤60 50%的数据 n≤600 100%的数据 n≤10000

2、超车（overtaking.pas）

Jzabc除了对多米诺骨牌感兴趣外，对赛车也很感兴趣。上周末他观看了一场赛车比赛，他总是能想出许多稀奇的问题。某一时刻，他看到有n辆车（总是匀速行驶）在同一直线上，并且处在一个无限长度的直道上，而且n辆车有严格的先后之分。他通过特殊的器材测出了每一辆车的速度。那么问题出现了，如果有两辆车A车和B车，A车在B车的后面，并且A车的速度比B车快，那么经过一段时间后，A车一定会超过B车。我们称之为一次超车。那么他想请你帮忙计算超车总数。我们记车道起点的坐标为0.没有两辆车的坐标是相同。 【输入】

第一行 一个数n ，车辆总数。以下n行为n两辆车的信息

第二行至第n+1行 每行有两个正整数x,y， x和y之间有一个空格 X为车的坐标，y为车的速度 0＜x，y≤1000000000 【输出】 一行，超车总数 【样例输入】 2 5 6 2 8 【样例输出】 1

【数据范围】

20%的数据 n≤300 50%的数据 n≤3000 100%的数据 n≤300000

3、最小奖励（minaw.pas）

Jzabc更是一个狂热的旅行爱好者。这次他想去一个诡异的地方。这个地方有n个村庄，编号为1到n。此刻他在1号村庄，他想去n号村庄。这n个村庄之间有m条单向道路。通过某些道路时，可能会花费一些钱作为“买路钱”，可能通过一些道路时，不仅不需要交“买路钱”，而且会得到一些奖励（这就是诡异的地方）。当然两个村庄之间可能有多条直接相连的道路。但是每一条路只能通过一次。这些村庄有这样的特性，从任何一个村庄出发，沿着任一条路径走都不会回到出发点。找到一条路径从1号村庄到n号村庄后，他需要计算一共得到多少奖励，一共交了多少“买路钱”。如果得到的总奖励钱数大于交的“买路钱”，那么称走这一条路径可以得到奖励；相反，如果前者小于后者，那么称走这一条路径需要花费。如果两者相等，那么jzabc不会选这一条路径（我也不知道他为什么不选这一条路径）。不会出现所有的路径两者都相等。他又需要你的帮助，让你找到一条路径，使他得到的奖励最小（为什么不是最大的奖励？），并输出最小的奖励。如果找不到一条路径能使他得到奖励，那么就找一条路径使他得到的花费最大（为什么就不是最小的花费？），并输出最大花费。 【输入】

第一行

两个正整数n , m，中间用空格隔开 N是村庄总数，m是道路总数

以下m行，每行三个正整数x,y,w 描述一条道路的信息，中间用空格隔开 X是此条道路的起点，y是终点

若w为正，则是通过此条道路得到的奖励钱数 若w为负，则是通过此条道路交的“买路钱”数 W不为0，并且︱w︱≤10 【输出】

一个整数，若有最小奖励，则输出，否则输出最大花费。 【样例1输入】 3 4

1 2 2 2 3 -1 2 3 3 1 3 -1

【样例1输出】 1

【样例2输入】 4 4 1 2 2 2 3 -3 2 3 -5

1 3 -2

【样例2输出】

3

【数据范围】

20%的数据 n≤20 m≤200 50%的数据 n≤50 m≤2000 100%的数据 n≤100 m≤20000