chenzaiyu-CSDN博客

原创洛谷 P1164 小A点菜

题目概述 uim请小A吃饭。uim由于买了一些辅（e）辅（ro）书，口袋里只剩M元（M 餐馆虽低端，但是菜品种类不少，有N种（N 小A奉行“不把钱吃光不罢休”，所以他点单一定刚好吧uim身上所有钱花完。他想知道有多少种点菜方法。由于小A肚子太饿，所以最多只能等待1秒。解题思路本题采用动态规划的思路，f[i]代表剩i元时有多少种吃法，初始化f[m]=1;

2017-02-12 15:21:55 363

原创洛谷 P1736 创意吃鱼法

题目概述回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵

2017-02-11 20:59:15 342

原创洛谷 P1889 士兵站队

题目概述在一个划分成网格的操场上， n个士兵散乱地站在网格点上。由整数坐标 (x,y) 表示。士兵们可以沿网格边上、下左右移动一步，但在同时刻任一网格点上只能有名士兵。按照军官的命令，们要整齐地列成个水平队列，即排成队列，即排成 (x,y),(x+1,y), …,(x+n -1,y) 。如何选择 x 和y的值才能使士兵们以最少的总移动步数排成一列。解题思路虽然士兵

2017-02-05 13:52:38 459

原创洛谷 P1417 烹调方案

题目概述一共有n件食材，每件食材有三个属性，ai，bi和ci，如果在t时刻完成第i样食材则得到ai-t*bi的美味指数，用第i件食材做饭要花去ci的时间。设计烹调方案使得美味指数最大。对于40%的数据1 对于100%的数据1 所有数字均小于100,000 解题思路这是一道01背包问题，但选择顺序对结果有影响。对于任意两件食材i和j，若i在j

2017-02-04 23:59:39 286

原创洛谷 P1443 马的遍历

题目概述有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步解题思路使用广搜，注意地图边界和马跳的方向即可。可以采用for代替8个if来减少要码的字。注意栈的读写。时间复杂度:O(n*m) 空间复杂度:O(n*m) 源程序 const d:array[1..2,

2017-02-04 22:44:58 444

原创洛谷 P1387 最大正方形

题目概述在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。 1 解题思路在读入的时候，如果读入了1，记下每行中到这个1之前有多少个连续的1。我采用的是模拟正方形的右下角，向上扩展，记下合法边长的最大值。合法边长为向上扩展的过程中扩展次数和扩展路径上记录值的最小值之间较小的数。注意边界，差值可能为负数。

2017-02-04 22:19:34 392

原创洛谷 P1091 合唱队形

题目概述 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1Ti+1>…>TK(1 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。其中1 解题思路

2017-02-04 21:36:25 288

原创洛谷 P1282 多米诺骨牌

题目概述多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的n个骨牌，每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置，求出最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。 1 解题思路这题采用动态规划的思路，f[i,j]代表前i个骨牌能够组成差值为j的最小翻转次数，初始化最大值，f[0,0]=0; 状态转移方程为f[i,j]

2017-02-03 23:48:45 675

原创洛谷 P1020 导弹拦截

题目概述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导

2017-02-02 22:38:22 229

原创洛谷 P1616 疯狂的采药

题目概述给定时间t，草药数n，采每组草药所需的时间a[i]和该组草药的价值b[i]，求在给定的时间内能采到的草药的最大价值。每种草药可以无限采。 n 解题思路我们知道，对于这类背包问题，时间复杂度为(n*t)在题目所给的范围内不会超时，方法与01背包一致，不过扫描的顺序相反。时间复杂度:O(n*t) 空间复杂度:O(t) 源程序 var

2017-02-02 22:18:08 242

原创洛谷 P1134 阶乘问题

题目概述给出n，求n!最右边第一位的非0数。解题思路对于一个数的阶乘，末尾的0只会以2*5的形式产生。而1到n中因数2的数量远远大于5，因此我们可以通过找因数5的方式来滤掉末尾的0; 这里还有另一个规律：除去0!和1!，本题的答案只可能是2，4，6，8。这4个数乘上末位是6的数，结果还是自己，因此可以将这种情况省略。时间复杂度:O(n)

2017-02-02 18:37:18 292

原创洛谷 P1514 引水入城

题目概述给定一个n*m的矩阵，每个格子代表高度，水只能向低处流。从最上面一排倒水，问最下面一排的每个格子是否都有水流过。若是，输出最少需在几个格子上倒水，若否，则输出最下面一排有几个格子接不到水。解题思路可以证明，如果底排每个格子都有水，那么从顶部每个格子倒下的水，在底部形成的一定是一个连续的区间。先用广搜找出从每个格子倒下水后在底部形成区间的

2017-01-31 23:20:38 280

原创洛谷 P1111 修复公路

题目概述给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路） N x 解题思路当村装能够通车时，图一定是连通的，本题可转化为求一最小生成树，使得其最大边权最小。

2017-01-14 19:57:24 338

原创洛谷 P1434 滑雪

题目概述 Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子： 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 81

2017-01-13 20:00:58 289

原创洛谷 P3390 矩阵快速幂

题目概述给定n*n的矩阵A，求A^k n<=100, k 输出时对每个元素对10^9+7取模解题思路设一n*n的矩阵为A，其元素为A[i,j](1 则A*A可用以下代码实现： for i:=1 to n do for j:=1 to n do for k:=1 to

2017-01-13 15:32:09 430

原创洛谷 P1980 计数问题

题目概述试计算在区间 1 到 n 的所有整数中，数字 x（0 ≤ x ≤ 9）共出现了多少次？例如，在 1 到 11 中，即在 1、2、3、4、5、6、7、8、9、10、11 中，数字 1 出现了 4 次。解题思路本题直接枚举即可，但我们现在讨论另一种做法。时间复杂度：O(nlog n) 空间复杂度：O(n) 源程序

2017-01-13 10:39:06 1592

原创洛谷 P1378 油滴扩展

题目概述在一个长方形框子里，最多有N(0≤N≤6)个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？(不同的油滴不会相互融合）解题思路这题就是一道纯粹的搜索。对于每个油滴，计算出它到矩形四

2017-01-12 15:16:40 324

原创 NOIP2016比赛总结

Day0 这是我参加NOIP提高组的第三年，也是学校活动被充掉的第二年(去年是校庆，今年是运动会)。我们一行人在下午两点前就到了酒店，和去年是同一间，所以像去年找不到考场之类尴尬的事就不会发生了。今天唯一值得提起的事就是吃了一碗泡面(貌似立下了很重的flag)。 Day1 第一题，惯例送分，注意不要一个一个跳，否则100000平方肯定会超时，一般情况下样例过了就能

2016-12-14 16:26:57 317

chenzaiyu的博客