- 博客(46)
- 收藏
- 关注
RSS订阅原创 洛谷P1731生日蛋糕 Java解法
题目出处说明：以下文字中把最上层当作第1层，最下层当作第M层，和代码一致思路：首先明确要对什么东西搜索，很明显题目告诉我们了，要对R和H搜，顺便记一下每一次的层数、体积、面积 只要层数到达最后一层记录面积就完事了比较容易想到的剪枝：1、面积大于min,return 2、体积大于n,return但是仅仅这么两个简单的剪枝只有30分。后来经过观察发现最上面一层最小体积为111，第二层及以上最小体积为222+111。因此我们有了新的剪枝：①已有体积+此层及以上最小体积大于n,returnj既然体积
2020-08-09 12:31:18
664
原创 洛谷P1074 靶形数独 Java解法
题目点这里思路：我选择一行一行搜，搜到每一行的最后一列就到下一行原则：①能优化就优化 ②能剪枝就剪枝③少用循环~~呜呜呜~注意：因为我们用的是Java，所以要务必小心随时TLE的风险~1、玩过数独的都知道从数字多的那一行开始填2、尽量别用for循环来求和，判断行列宫是否重复啥的3、求和可以打表，虽然还是要for循环，但少了判断也是极好的4、可以用布尔数组hang[i][shuzi]表示第i是否有shuzi，列同理，宫我实在懒得想5、如果你用for循环判断是否行列重复，极大可能会T（我就T了
2020-08-08 16:38:58
208
原创 洛谷P1825 Java解法
题目出处点这里思路：就是普通的广搜，不过要事先想办法把传送点相应的位置记录下来，值得注意的是此题中传送走过传送点时不用记录此点的访问状态，因为可以来回传送。分析完之后代码就很简单了：package search;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class P1852 { static int N, M, x0, y0, x1, y1; static i
2020-08-04 12:04:27
248
原创 洛谷P1434 Java解法
题目出处思路：记忆化DFS，把每个点搜到的最大长度记录下来，这样如果在下一个点搜到以前点的话，直接加上那个点的最大长度即可，但还是要注意一些细节，比如有可能在一次搜索里多次碰到以前的点，这时候就不能无脑加长度，而是要判断哪个加了以前的长度后最大，必须每次记录最大长度代码如下：package search;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;impo
2020-08-03 12:58:57
373
原创 洛谷P1406 Java解法
题目出处思路：dfs+剪枝。dfs:从头到尾把每种组合都搜一遍，如果遇到满足条件就疯狂return,但最后一个点TLE剪枝：稍加思索就发现，每一行之和必须是所有数之和除以n，只要不满足这 个条件就return，这样就不会TLE了代码简单易懂(最好不要在dfs里写上面的那个剪枝的判断，这样的话java很容易MLE)：package search;import java.util.Arrays;import java.util.Scanner;public class P1406 { s
2020-08-02 13:41:39
165
原创 洛谷 CF510B Java解法
题目链接思路：比较明显的深搜，当然广搜也可以，但可能比较麻烦判断是否成环，因此我们用DFS,一条路搜到底，如果搜到的下一个点是起点而且搜的个数大于等于4，那么就可以判断以此点为起点可以搜到环，要注意的是每次要把不能搜到环的起点置为访问过，因为它搜不到环就证明此点不是组成环的一部分，所以下次就不用搜这个点，再者如果不加这句话就会WA（我也没弄明白为什么，真的很疑惑，如果有懂得大佬麻烦解答一下），加了就可以AC下面是代码:(疑惑点有标注)package search;import java.util
2020-08-01 11:53:18
155
原创 洛谷P1025 Java解法
题目出处思路：DFS，开一个数组arr[]存储每次满足条件的k个值，每当数组满了且数组里所有数的和等于n时就分法++，不过如果单纯这样暴力搜肯定会TLE，因此我们注意到每一次存入数组里的数必须大于等于前一个数，所以我们设置一个变量zz每次存储当前数，以后每一次从zz开始搜即可。但是我们发现这样还是会TLE，因为我们只确定了每一次存入数组大的下限，而没有规定上限，注意到总和必须为n，因此我们每次搜到的数肯定不能大于n减去前面已经搜过的数的和，这样一来就完成了基础的剪枝。代码十分易懂：package s
2020-07-31 10:22:13
338
原创 洛谷P1683 Java解法
题目出处点这里思路：从起点开始广搜，因为要求得出能走的最多的砖块数，所以每走一步就+1即可。代码：package search;import java.awt.Point;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class P1683 { static int W, H, x, y, sum = 1; static int[] xx = { 0, 0, 1
2020-07-29 13:44:49
284
原创 洛谷P1141 Java解法
题目出处点这里思路①：对每一个m点进行广搜，输出搜到的结果即可思路②：很明显思路①会MLE或TLE，我们发现有可能多个m点会在同一个区域（这里的区域指前面的m点搜过的区域），如果再次搜索无疑会造成大量时间的浪费，因此我们可以标记每一次搜过的区域为已访问并用另一个二维数组temp[ ][ ]把该区域的所有点的值赋值为相应可以走到的格数即可，并在每次输入m点时判断此点是否被访问过，如果被访问过就直接输出temp里相应点的值即可，如果没有被访问过就对该点广搜即可。不过要注意读入方式和输出方式，适当的方法会节
2020-07-29 12:40:06
340
原创 洛谷P1451 Java解法
题目出处点这里思路：BFS。按顺序逐个对矩阵非零元素且未访问过的元素进行广搜，每一次广搜将此次可以走到的元素标记为已访问，最后记录bfs次数的就是细胞数。代码如下：package search;import java.awt.Point;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class P1451 { static int n, m, sum; stat
2020-07-28 14:50:39
201
原创 洛谷P1332 Java解法
题目出处点这里思路①：可以分别对每个领主所在地进行广搜,搜到第一个感染源时就是被感染时间，但是用java会MLE，因此行不通思路②：可以同时对每个感染源所在地进行广搜，并把每一次的每一个感染源在每一层搜到相应的地点的所需时间记录在n*m的数组里，这样得到的数组就是各个地点被感染的时间，最后输出各个领主所在地的感染时间就行了，这种方法比思路①快很多，空间也节省很多。package search;import java.awt.Point;import java.io.BufferedReader
2020-07-28 13:32:27
292
原创 洛谷P2298 Java解法
题目出处点这里很明显又是广搜模板题代码：package search;import java.awt.Point;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class P2298 { static char[][] arr; static int n, m, x, y; static int[] xx = { 0, 0, 1, -1 }; static
2020-07-28 11:05:40
243
原创 洛谷P1746 Java解法
题目出处思路：很明显又是广搜，加一个为1的地方不能走的判断即可。不过还是要注意每找到一个可以走的地方就要标记为走过，如果不标记就会浪费大量时间重复走过的坐标，甚至可能TLE。代码如下：package search;import java.awt.Point;import java.util.List;import java.util.Scanner;import java.util.Vector;public class P1746 { static int n, x1, y1,
2020-07-26 12:47:23
241
原创 洛谷P1747 Java解法
题目出处思路：很明显用广搜，一层一层的搜，每一次用队列把走到相应坐标和步数记录下来，最后只要搜到就把步数输出即可。package search;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class P1747 { static int x1, y1, x2, y2; static int[] xx = { 1, 1, -1, -1, 2, 2, -2, -2,
2020-07-26 10:01:17
166
原创 洛谷P1162 Java解法
题目出处其实这题代码很简单，可能就思路比较难想(虽然题目标签是bfs，但我想不出来bfs思路是什么，所有这里我们使用dfs)思路：在整个方阵外层套一圈0，然后把闭合圈外的0都变成-1即可，剩下的0就是闭合圈内的0。最后输出时把-1输出为0，1输出为1，0输出为2.OVER代码里注释很详细：package search;import java.util.Scanner;public class P1162 { static int n, arr[][]; static int[] x
2020-07-25 11:59:50
176
原创 洛谷P2404 Java解法
题目出处思路：肯定打表啊！ 用一个数组arr[]存储每次拆分的结果，满足条件就输出，不断再原来数组基础上进行搜索即可，不过要注意输出的数是从小到大的，因此我们可以用一个变量zz记录每次存进arr[]的数，下一次搜索从这个数开始即可，这样就解决了从小到大的问题。代码一看就懂：package search;import java.util.Scanner;public class P2404 { static int n,arr[];//arr存储不同拆分方式的数组 public s
2020-07-24 15:19:42
190
原创 洛谷P1101 Java解法
题目出处思路：最好用dfs，但这里我选择暴力解决此题1、首先找到每个y，然后判断以此y为头可不可以找到完整的yizhong，把找到的yizhong的相应坐标用别的数组记录下来2、然后输出即可，不会TLE3、代码很简单，容易理解4、有时间我再加上dfs的解法package search;import java.util.Scanner;public class P1101 { static int n; static char[][] arr, resArr;//resArr表示最
2020-07-24 12:01:59
214
原创 洛谷P1019 Java解法
题目出处点这里思路：dfs暴力搜出所有情况记录长度最大值即可找到每一个可以作为头的字符串不断与其他字符串进行拼接，然后把拼接后的字符串接着与其它字符串不断拼接，取所有情况的长度最大值。值得注意的是有可能你找到·了一个可以当头的字符串，但是它不能和任何字符串进行拼接，可是它的长度就是最大的，因此不管头字符串能不能拼接成功，我们都要判断头字符串的长度是不是最大的。代码一看就懂(超详细的注释)：package search;import java.util.Arrays;import java.u
2020-07-23 17:08:22
622
原创 洛谷P1605 Java解法
题目出处点这里思路：深度优先搜索，走不通就返回上一步接着找，走法有上下左右四种方案，代码很简单代码有解释(详细)：package search;import java.util.Scanner;public class P1605 { static int N, M, T, SX, SY, FX, FY, sum;// sum代表方案总数 static int[][] chess;//表示棋盘 public static void main(String[] args) { S
2020-07-23 13:54:22
257
1
原创 洛谷P1135 Java
题目出处点这里思路：很明显可以使用dfs和bfs，这里我选择dfs，当然还有一点小技巧，比如当到达B楼时接收的按钮次数ans都是目前为止的最小值；比如还没到达B楼时，但此时的按钮次数sum已经大于等于之前已经走到B楼的走法的ans，就可以断定这不是最佳走法，直接return即可。相反，如果不加这些判断条件，很可能会TLE甚至栈溢出！代码里得解释还是很详细的：package search;import java.util.Scanner;public class P1135 { stati
2020-07-22 12:41:24
244
原创 洛谷P1443 Java解法
题目出处思路：既然题目标签是广搜,那么我们就用BFS做即可(事实证明此题广搜比深搜快不少)BFS:全称广度优先搜索，顾名思义，一层一层的遍历DFS:全程深度优先搜索，顾名思义，一条路走到黑，完事再回来走别的路对于此题（选择一层一层遍历也就是BFS）：1、找到所有可以通过起始位置走到的下一步,并标记为1,那么第一层遍历就完成了2、开始第二层,找到在第一层的所有位置可以走到的下一步,标记为2，那么第二层就完成了3、以此类推，这就是广度优先搜索，属实神奇（但是代码肯定要更细节一些）喜闻乐见的代码
2020-07-21 17:42:38
332
1
原创 洛谷P1219 Java解法
题目出处代码里有解释(深搜)：package search;import java.util.Scanner;public class P1219 { static int n, sum = 0;// sum记录输出次数 static int[] arr;// 用一维数组表示皇后的位置,下标代表行,值代表列 public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.
2020-07-20 13:24:17
235
原创 洛谷P3853 Java解法
题目出处点这里可以先做做下面这道题：洛谷P2678 P2678的题解思路几乎一模一样,只不过需要注意间距除mid如果除得尽则需要减一,代码有解释代码有解释：package binaryFindAndAnswer;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.StreamTokenizer;public class P
2020-07-19 12:49:22
235
原创 洛谷P2678 Java解法
题目出处点这里## 思路：形如求最小值的最大值以及求最大值的最小值都可以二分求解。就像这道题,求最短的跳跃距离尽可能长(就是求最小值的最大值)，注意到跳跃距离肯定在1至L之间,于是问题就变为在1~L之间求可行解的最大值,可行解就是跳跃距离的最小值,如果照着题目的思路思考,我们的思维可能会被只能移走M快岩石限制住,因此我们可以逆向思考,从结果入手:每次取1-L中mid的值,把每次的mid当作跳跃距离,然后判断跳跃距离为mid时需要移动的岩块sum为多少。如果sum<=M,那就说明这个最大值mid
2020-07-19 12:02:42
297
原创 洛谷P1182 Java
题目出处点这里思路：因为都是正整数,所以不同段和的最大值的最小值肯定大于数组里最大的那个(可以自己想想,其实很好证明)，将其设为L，肯定小于数组里所有数字的和(这个是显然的)，将其设为R，因此在L和R之间进行二分答案即可。check函数:判断当最小值为mid时可以分成的段数d是否大于M。d大于M的话就说明最小值是大于mid的,所以在mid右边搜；d小于M的话就说明最小值是小于mid的,所以在mid左边搜。注意：如果check函数看不懂的可以先试试这个题：洛谷P1181代码如下：package b
2020-07-18 17:53:00
153
原创 洛谷P1181 Java
题目出处点这里思路：每一段的和要尽量接近M，也就是说第一段的和尽量接近M,第二段的和尽量接近M,第三段的和尽量接近M…代码如下：package greedy;import java.util.Scanner;public class P1181 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextIn
2020-07-18 16:35:01
152
原创 洛谷P1678 Java
题目出处点这里思路：二分。注意：当学生分数大于等于学校最高录取分数线时,直接用学生分-学校分即可；当学生分数小于等于学校最低录取分数线时,直接用学校分-学生分即可；其余情况正常二分；说实话有点不懂二分时的判断条件和返回值有什么需要讲究的地方,似乎不同条件返回的值都不一样,有时甚至可能会有索引超限,死循环的情况,不知道有没有看到这篇文章的大佬解释一下代码：package binaryFindAndAnswer;import java.io.BufferedReader;import jav
2020-07-17 15:39:06
296
原创 洛谷P1873 Java
题目出处点这里思路：二分树的高度,注意返回值即可代码：package binaryFindAndAnswer;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.StreamTokenizer;import java.util.Arrays;public class P1873 { static int[] arr; sta
2020-07-17 12:30:38
252
原创 洛谷P2249 Java
题目出处点这里思路：二分查找,不过要注意返回第一个出现目标值的索引位置。只要当arr[mid]==mubiao时也继续向左查找,最后输出left或right即可解决这个问题代码：package binaryFindAndAnswer;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.StreamTokenizer;public c
2020-07-16 12:54:16
791
原创 洛谷P1106 Java解法
题目出处点这里思路见代码：package greedy;import java.math.BigInteger;import java.util.ArrayList;import java.util.Collections;import java.util.Scanner;/** * 目标：输出最小数 * 思路： * 1、因为需要输出的是最小数,所以我们每次输出的时候尽量输出最小的那个数 * 2、比如字符串s:754381,k=4,需要按顺序输出两位数,按照排序后的数组arr{1,
2020-07-14 23:03:14
411
2
原创 洛谷P3817 Java解法
题目出处点这里思路：不断遍历相邻两个数i、i+1并取他们的和neighborSum,如果和大于x，就要吃掉tempSum=neighborSum-x个糖果,先吃第i+1个盒子里的,如果arr[i+1]>=tempSum就从arr[i+1]里减去tempSum个即可,如果arr[i+1]<tempSum,就把arr[i+1]吃光置为0,再去吃前一个的即可。如此循环i-1遍即可,最后把每个需要吃掉的糖果数tempSum相加即可。代码如下：package greedy;import java
2020-07-13 20:51:09
228
原创 洛谷P1090 Java解法
题目出处点这里思路：先将n个果堆根据重量从小到大，每次先取最小的两个求重量和并把这两个果堆从原来n个果堆中去掉，再把这个重量和放入原先堆再进行从小到大的排序，重复这个过程并把每次的重量和相加就可以得到结果注意：当果堆数为n时，需要进行的排序次数为n-1;当n比较大时，进行n-1次排序显然会TLE，因此我们用小顶堆，也就是优先队列就可以解决这一问题，减少运行时间。代码如下：package greedy;import java.util.PriorityQueue;import java.util
2020-07-13 18:45:27
286
原创 洛谷P1803 Java解法
题目出处点这里思路：先把结束时间end从小到大排序,再按end时间从小到大参加比赛约束条件：1、前一个参加的比赛的end时间必须小于等于后一个参加比赛的start时间2、前一个参加比赛的end时间必须小于后一个参加的比赛end时间代码(解法一)如下：//两个判断的先后顺序略微会影响运行时间//可能是因为洛谷的测试数据的end时间没有重复的//所以在洛谷里把第二个约束条件注释掉也可以//后面还有解法二，我觉得对数据量大且end重复较多时的测试数据起到比较好的效果,//但在洛谷测试数据会很
2020-07-12 21:46:14
290
1
原创 洛谷P2240 Java解法
题目出处点这里思路：构造一个金币类，按性价比从小到大进行排序即可，不过要注意可能有全部金币都取完了但是背包还没满的情况，此时直接输出maxPrice即可代码如下（很好理解）：package greedy;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.Scanner;public class P2240 { static Array
2020-07-11 19:39:33
548
原创 洛谷P1223 Java解法
题目出处点这里挺简单的一道题，把等待时间由小到大进行排序就行，注意稳定性即可下面是代码：package greedy;import java.util.Scanner;public class P1223 { static int[] a; static int[] b; static double sum; static void swap(int[] data, int a, int b) { int t = data[a]; data[a] = data[b];
2020-07-11 19:32:33
339
原创 洛谷P1010 Java解法
题目出处点这里思路：使用递归例如对1315进行转化：1315 = 210 + (1315 - 210)就像这样1315可以转化为210和(1315 - 210)两部分因此问题变成先转化210再转化剩下的(1315 - 210)两大步骤于是代码可以写成：先递归转化前一为2的k次幂的部分,再递归转化后一部分**代码有讲解：package reintroduction_recursion;import java.util.Scanner;public class P1010 { publ
2020-07-10 21:40:26
375
原创 洛谷P1259 Java解法
题目出处点这里思路：1、第一行为原来的状态2、第二行把第一行空格左边的中间的两个棋子与空格换位3、第三行把第二行的空格与最后两个黑棋互换（也可以看作把黑子向左移两格）4、第四行把第三行空格左边的中间的两个棋子与空格换位5、。。。。。同上据此，我们可以使用递归完成此题但是注意到从倒数第四行开始，棋子的移动开始变得扑朔迷离起来，我找了一会没找到规律，于是我们可以选择直接将其打出来代码里有注释：package reintroduction_recursion;import java.uti
2020-07-10 18:39:38
303
原创 洛谷P1990 Java
题目出处点这里动态规划，就像找规律一样，注意从每种情况中进行分类即可**代码如下：（注意每次都要取模，不然无法AC）package reintroduction_recursion;import java.util.Scanner;public class P1990 { static int res; static int[] f = new int[1000001]; static int[] g = new int[1000001]; public static voi
2020-07-09 19:30:02
175
原创 洛谷P1036 Java
题目出处点这里思路见代码：package reintroduction_recursion;import java.util.ArrayList;import java.util.Scanner;public class P1036 { static int n; static int k; static ArrayList<Integer> list;//存储满足组合的数 static int res = 0;//结果 static boolean[] isUse
2020-07-09 13:44:23
230
原创 洛谷P2437 Java
题目出处点这里思路：由于是m到n的走法，因此第一想法是开N*N的二维数组，先把6之前的走法填到里面去，如图：左下部分划掉是因为m<n，容易发现从m到n的走法实际上就是数列{1,2,3,5,8,……}的第n-m项，又因为此数列是递推数列，因此不难得出代码如下：package reintroduction_recursion;import java.math.BigInteger;import java.util.Scanner;public class P2437 { static
2020-07-09 10:37:58
187
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人