NOIP提高组 1999 & 2000 题解合集

【序言】话说我在学神奇算法的时候，基础应该也要巩固，于是打算提前把noip提高组的刷完。

具体的题目描述和提交我就在vijos上完成。

【1999.1】

给定一个信封，最多只允许粘贴n张邮票，计算在给定m（n+m<=10）种邮票的情况下（假定所有的邮票数量都足够）,如何设计邮票的面值，能得到最大max ，使得1～max之间的每一个邮资值都能得到。

例如，n=3，m＝2，如果面值分别为1分、4分，则在l分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当n=3，m＝2时，7分就是可以得到连续的邮资最大值，所以max=7，面值分别为l分、3分。

样例输入：共一行，两个整数，分表为n与m的值。

一行，分别为n,m。

两行。

第一行为m种邮票的面值，按升序排列，各数之间用一个空格隔开。

第二行为最大值。

如果有多解，输出字典序最大的一个。

各个测试点1s

noip1999

【分析】似乎很早很早以前做到过~那时候因为不太懂各种算法，就乱搞搞过去了。但是现在思维复杂起来了，时间效率考虑的太多，反而难以下手。开始想的是贪心，发现是有问题的。数据范围n+m<=10，那么我们果断爆搜。在爆搜的途中如何随时更新值？只能用背包了。1a。

【代码】

【1999.2】

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、出发点每升汽油价格p和沿途油站数n，油站i离出发点的距离d[i]、每升汽油价格p[i]。

计算结果四舍五入至小数点后两位。

如果无法到达目的地，则输出-1。

输入共n+1行，第一行为d1,c,d2,p,n，以下n行，每行两个数据，分别表示该油站距出发点的距离d[i]和该油站每升汽油的价格p[i]。两个数据之间用一个空格隔开。

1 <= n <= 100

1s

0<=n<=100

【分析】开始还以为是dp，仔细一想是贪心。因为细节没处理好，后来还下载数据调试= =。

策略：主要是采用搜索的框架（但是其实不是，每层只有一个点在操作）设当前到达的点是k。

①对于k能到的点中，找到第一个油费比k小的点p。若能找到，跳到②；否则跳到⑤。

②加上刚好去p的油，累加答案，并来到p这个状态。跳到①。

③说明在能到达的点中，k的油费最小。跳到④。

④判断k能否直接到达终点，若能累加答案并退出，否则跳到⑤。

⑤找到k能到达的点中油费最小的点，同时加满油驶向p。若已经没有点了，输出-1，否则跳到①。

但是很遗憾，还有一个小的问题：我们还要记录一下当前所剩的油量q。以上过程都要涉及q。

1999的其它两题就不必说了吧~~~

【2000.1】

jerryzhou同学经常改编习题给自己做。

这天，他又改编了一题。。。。。

设有n*n的方格图，我们将其中的某些方格填入正整数，

而其他的方格中放入0。

某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。

在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）

此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。

第一行:n (4<=n<=20)

接下来一个n*n的矩阵，矩阵中每个元素不超过80，不小于0

一行，表示最大的总和。

多进程dp

【分析】其实原题是二取方格数，不过这样更加可以练练手。dp的方法应该很熟练了，我就写了些网络流。太高兴了，建图自己就yy出来了。设超级源点s，与左上角连一条费用为0，流量为3的边；设超级汇点t，与右下角连一条同样的边。能到达的两点连一条流量为inf，费用为0的边。然后把每个点拆成两个，连一条流量为inf，费用为0的边和一条流量为1，费用为权值的边。流量的意义是路径，费用的意义是价值。然后跑一遍最大费用最大流。

【2000.2】

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

只需输出以此字母开头的最长的“龙”的长度

连成的“龙”为atoucheatactactouchoose

noip2000提高组第3题

【分析】开始还以为是dp，用f[i][j]表示连接了i个单词，且最后一个是j的最大长度，后来发现无法获知每个单词是否用过（状压dp?）。想了一会了，n<=20,果断搜索。先预处理两两单词的关系，然后爆搜~。1a。

【2000.3】

noip2000 提高组第一题

我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置的（值减1）为指数，以10为底数的幂之和的形式。例如，123可表示为1*10^2+2*10^1+3*10^0这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值-1）为指数，以2为底数的幂之和的形式。一般说来，任何一个正整数r或一个负整数-r都可以被选来作为一个数制系统的基数。如果是以r或-r为基数，则需要用到的数码为0，1,....r-1。例如，当r=7时，所需用到的数码是0，1，2, 3，4，5和6，这与其是r或-r无关。如果作为基数的数绝对值超过10，则为了表示这些数码，通常使用英文字母来表示那些大于9的数码。例如对16进制数来说，用a表示10，用b表示11，用c表示12，用d表示13，用e表示14，用f表示15。在负进制数中是用-r作为基数，例如-15（＋进制）相当于110001（-2进制），

并且它可以被表示为2的幂级数的和数：

110001=1*(-2)^5+1*(-2)^4+0*(-2)^3+0*(-2)^2+0*(-2)^1+1*(-2)^0

问题求解:

设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负进制下的数：-r∈{-2，-3，-4,....-20}

输入文件有若干行，每行有两个输入数据。

第一个是十进制数n（-32768<=n<=32767）; 第二个是负进制数的基数-r。

输出此负进制数及其基数，若此基数超过10，则参照16进制的方式处理。【具体请参考样例】

每个点1s。

每个测试数据不超过1000组。

from 玛维-影之歌

noip2000原题

【分析】说来惭愧，开始想的太复杂了=_=。当进制是负数时该怎么处理？开始想是枚举答案的位数，然后一步步的逼近~~真是麻烦。后来一拍脑袋，不是可以直接除吗？负数应该也满足整数的性质，只是除的时候要特判。1a。