冲刺NOIP模拟试题与解析 提高组

《冲刺NOIP模拟试题与解析 提高组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、冲刺NOIP模拟试题与解析（十一）学校：河南省焦作一中出题人：刘晓刚《NOI导刊》2011年9月第7期题目一览题目多米诺骨牌超车最小奖励文件名dominoovertakingminaw输入文件.in.in.in输出文件.out.out.out题目类型传统传统传统测试数目101010时间限制1s1s1s内存限制128m128m128m【多米诺骨牌DOMINO】【题目描述】Jzabc对多米诺骨牌有很大的兴趣，然而他的骨牌比较特别，只有黑的和白的。他觉得如果存在连续三个骨牌是同种颜色的，那这个骨牌排列就是不美观的。现在他有N个骨牌要排列，他想知道不美观的排列的个数。他想请你

2、帮忙进行统计不美观排列的个数。【输入格式】只有一个正整数，即要排列的骨牌的个数。【输出格式】一个数，即不美观的排列的个数。【输入样例】4【输出样例】6解释：有6中不美观的排列。【数据规模】对于20%的数据，满足N<=60对于50%的数据，满足N<=600对于100%的数据，满足N<=20000对于%的数据，满足。【超车OVERTAKING】【题目描述】Jzabc对赛车也很感兴趣，在参观车展是，想到这样一个问题，在某时刻，他看到n辆车（总是匀速行驶）在同一直线上，且处于一个无限长的直道上，而且n辆车有严格的先后之分，。他通过特殊的器材测出了每辆车的速度，那么问题出现了，

3、如果有车A和车B，A在B的后面，且A的速度快于B的，那么经过一段时间后，A一定会超过B，我们称之为一次超车。那么他想请你帮忙计算超车总数。我们记车道起点的坐标为0，没有两辆车的坐标相同。【输入格式】第一行，一个数N，表示车辆总数。以下n行为N辆车的信息；第二行至第N+1行，每行有两个正整数X、Y，X和Y之间有一个空格，其中X为车的坐标，Y为车的速度。0<=X,Y<=1000000000【输出格式】一行，超车总数【输入样例】25628【输出样例】1【数据规模】对于20%的数据，满足N<=300对于50%的数据，满足N<=3000对于100%的数据，满足N<=300000

4、对于%的数据，满足。【最小奖励MINAW】【题目描述】Jzabc更是一个狂热的“驴友”，这次他想去一个诡异的地方。这个地方有n个村庄，编号为1到n。此刻他在1号村，他想到n号村。这n个村子之间有m条单向道路。通过某些道路时，可能需要花费一些钱作为“买路钱”，可是通过一些道路时不仅不用交钱反而会得到某些奖励。当然两个村庄之间可能有多条直接相连的道路，但是每条道路只能通过一次。这些村庄有这样的特性，从任何一个村庄出发，沿着任一条路径走都不会回到出发点。找到一条路径从1号到n号，他需要计算一共得到多少奖励，一共交了多少过路钱。如果奖励的钱数大于交的过路钱数，那么称这样一套路

5、径可以得到奖励，反之如果前者小于后者，那么这样的路径需要花费，如果二者相等，那么Jzabc不会选择。不会出现所有的路径两者都相等，现在请你帮忙找到一条路径，使得到的奖励最小（为什么不是奖励最大？或花费最少？花费最大？），并输出最小奖励。如果找不到一条路径使其得到奖励，那么就找一条路径使其得到的花费最大（为何不是最小花费？），并输出最大花费。【输入格式】第一行，两个用空格隔开的正整数n和m；以下m行，每行三个正整数x,y,w，描述一条路的信息，中间用空格隔开，其中x表示道路的起点，y表示终点；若w为负，则是通过磁条道路交的买路钱数目，若w为正，则表示这条路奖励的钱数；w

6、不为零，且其绝对值不大于10。【输出格式】一个整数，若有最小奖励则输出，否则输出最大花费；【输入样例】3412223-123313-1【输出样例】1【输入样例】3412223-323-513-2【输出样例】3【数据规模】对于20%的数据，满足n<=20,m<=200对于50%的数据，满足n<=50,m<=2000对于100%的数据，满足n<=100,m<=20000对于%的数据，满足。【多米诺骨牌】【题目大意或抽象出的数理模型】【解法或分析】递推我们不妨计算一下美观的情况（问题转化，寻求解题突破口）用f[I]表示。我们默认已经推到第I个，那么前I个都是满足题意的，在第

7、I的位置上放置一个与第I-1相同颜色的骨牌，则情况数为F[I-2]，否则为F[I-1]，然后F[I]=F[I-1]+F[I-2]；再求出所有情况用排列组合的思想，每一位都可以是白的和黑的，所以美观与否的总的排列数目为ans=2^n，最后的ans=ans-F[I]，即得到所求。因为数据量很大，需要使用高精度，还需要用到高精度的优化（万进制优化）。【参考程序】（在FP中编辑、编译之后再复制过来）【出题目的】【分析二】【一句话题意】求所有n位二进制中存在连续3位相同的个数。【考察知识点】动态规划/递推/高精度【思路】考虑美观的情况，设f[i]为i个骨牌的排