落谷NIOP历年(2015~2018)题目思路

落谷NIOP历年水题思路

蒟蒻的第一篇题解，不好勿喷

P1909 买铅笔

简述：3种物品，每种物品有无数个，其价值为ci，花费为wi，在你只买一种物品的情况下，满足价值之和大于等于n的情况下，所花费费用最小。

思路：由于只有3种物品，只需求出每种物品满足条件的最小花费即可。

P2010 回文日期

简述：两个合法8位日期，年，月，日, 输出其中间（包括它本身）所有合法日期且回文的个数。

思路：先枚举两个日期之间合法的月，日，然后翻转求出年，再判断年是否在数据里面，最后统计输出。

P2058 海港

简述：n条船，每条来的时间为ti,船上有m个人，每个人来自其他的国家（有可能相同）求当一条船来了时，其前24小时，所到达的船上人的国籍之和。

思路：两个数组，分别存船到来的时间和船上的国籍，每来一艘船就a[国籍]++就行，。最后判断前24小时所来的船上国籍的人数，用for循环过一遍，统计并输出。

P2119 魔法阵

简述：n个数（有可能几个相同），从中选取4个做为a,b,c,d。当满足a​<b​<c​<d​,b​−a​=2(d​−Xc​)，b−a<(c−b)/3，b-a<(c-b)/3b​−a​<(c​−b​)/3。这个物品作为a或b或c或d的次数就多一次，最后输出n行，每行4个数，表示这个数作为a,b,c,d的个数。

思路：先双重for循环，枚举a，b两个物品，当枚举b时，如果a,b,满足条件，就进入下一重循环枚举c，由a，b，c,算出d,开个结构体存入最后输出。

P2669 金币

简述：一个数n，求出1+2+2+3+3+3+4+4+4+4+…这个数列前n项之和。

思路：三个数，cnt,l,m。cnt用来存前n项只和，l记录这个数是否出现了m次，如果是就将m++，l清零从新记录，cnt每次叠加m最后输出。

P2670 扫雷游戏

简述：两个数n，m。表示nm的矩阵，每个格子里存得是“？” 表示空格，或“”表示地雷，问你每个空格周围3*3中地雷个数之和。

思路：非常水先双重for循环枚举每个格子，如果这个格子为“？”就判断它的八方是否为“*”累加在数组里,最后输出。

P2671 求和

简述：一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色color_i用[1,m]当中的一个整数表示，并且写了一个数字number_i。定义一种特殊的三元组：(x,y,z)，其中x,y,zx,y,zx,y,z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

xyz是整数,x<y<z,y−x=z−yx<y<z

colorx=colorx=colorz

满足上述条件的三元组的分数规定为(x+z)×(number_x+number_z)(x+z) \times (number_x+number_z)(x+z)×(number_x+number_z)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10007所得的余数即可。

思路：运用分组思想，把每个颜色分为一组，再在每个颜色中按奇偶分组，所以一共有2m组，设一个分组里有k个数，这个分组中的数分别是x[1],x[2]……x[k]，下标分别是y[1],y[2]……y[k]
那么可得：答案=(x[1]+x[2])(y[1]+y[2])+(x[1]+x[3])(y[1]+y[3])+……+(x[1]+x[k）(y[1]+y[k])+(x[2]+x[3])(y[2]+y[3])+(x[2]+x[4])(y[2]+y[4])+……+(x[2]+x[k])*(y[2]+y[k])
+……然后事先将y[1]+y[2]+……+y[k]求出，用的时候调用就行。

P2672 推销员

简述：一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为S_i米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。你每走1米就会积累1点疲劳值，向第i家住户推销产品会积累A_iA点疲劳值。对于不同的X，在不走多余的路的前提下，你最多可以积累多少点疲劳值。

思路：开一个结构体存Si和ai，用si作为基准排序，两个for寻环算出从出口到第i户所得到距离长,最大的疲劳值，再算出从出口到第i户所得的最大疲劳值，最后一个for循环每次比较，是跳过这一家好还是不跳过，最后输出数组[n]即是最优的答案。

P3954 成绩

简述：三个数a,b,c,求出a×20%+b30%+c50%非常水！。

思路：。。。直接表达式上:cout<<a×20%+b30%+c50%;不过注意是double类型。

P3955 图书管理员

简述：有n个图书编码，这个图书编码是一个正整数。 有q个需求码，这个需求码也是一个正整数。如果一本书的图 书编码恰好以需求码结尾，那么这本书就是所需要的。 出q_i书中图书编码最小的那本书，如果没有，请输出−1。

思路：一个字符串类型的集合，每次存这个编码，再在输入需求码式，查找这个集合有没有包含的，再来一个maxn做最小的编码的比较再输出。

P3956 棋盘

简述：有一个m×m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费1个金币。另外， 你可以花费 2个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？

思路：记忆化dfs搜索，tx,ty,d,m表示下一个坐标，上一次是否用了魔法，总共话费金币个数，每找到一次路径就更新minn，再开一个map存从起点到现在最小话费的金币个数，如果现在算出来的话费比之前所算出的话费还大就直接剪枝。最后输出minn。

P3957 跳房子

未完待续~~~

P5015 标题统计

简述：一个字符串（可能有空格，求出除空格外字符串的个数）。

思路：水！但我的一个朋友比赛时脑残写成cin用getline再来for循环如果不为空格就++最后输出。

P5016 龙虎斗

简述：n个数，一个m，s1,p1,p2，在第s1个增加p1。从1到m-1计算出m左边的气势（具体公式详见题目）从m+1道n计算出m右边的气势，问你再s2里加入p2，使左右两边气势项减的绝对值最小。

思路：for循环枚举在第i个放s2,所得的气势绝对值之和跟minn比较，如果比之前的还小就更新s2=i。最后输出s2。(记得开long long,不然会炸！！！)。

P5017 摆渡车

作者太蒻了，讲不出来 未完待续~~~

P5018 对称二叉树

膜拜神犇 未完待续~~~