1 _XERIN

尚未进行身份认证

我要认证

未填写

等级
TA的排名 22w+

洛谷P1731生日蛋糕 Java解法

题目出处说明:以下文字中把最上层当作第1层,最下层当作第M层,和代码一致思路:首先明确要对什么东西搜索,很明显题目告诉我们了,要对R和H搜,顺便记一下每一次的层数、体积、面积 只要层数到达最后一层记录面积就完事了比较容易想到的剪枝:1、面积大于min,return 2、体积大于n,return但是仅仅这么两个简单的剪枝只有30分。后来经过观察发现最上面一层最小体积为111,第二层及以上最小体积为222+111。因此我们有了新的剪枝:①已有体积+此层及以上最小体积大于n,returnj既然体积

2020-08-09 12:31:18

洛谷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

洛谷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

洛谷P1434 Java解法

题目出处思路:记忆化DFS,把每个点搜到的最大长度记录下来,这样如果在下一个点搜到以前点的话,直接加上那个点的最大长度即可,但还是要注意一些细节,比如有可能在一次搜索里多次碰到以前的点,这时候就不能无脑加长度,而是要判断哪个加了以前的长度后最大,必须每次记录最大长度代码如下:package search;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;impo

2020-08-03 12:58:57

洛谷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

洛谷 CF510B Java解法

题目链接思路:比较明显的深搜,当然广搜也可以,但可能比较麻烦判断是否成环,因此我们用DFS,一条路搜到底,如果搜到的下一个点是起点而且搜的个数大于等于4,那么就可以判断以此点为起点可以搜到环,要注意的是每次要把不能搜到环的起点置为访问过,因为它搜不到环就证明此点不是组成环的一部分,所以下次就不用搜这个点,再者如果不加这句话就会WA(我也没弄明白为什么,真的很疑惑,如果有懂得大佬麻烦解答一下),加了就可以AC下面是代码:(疑惑点有标注)package search;import java.util

2020-08-01 11:53:18

洛谷P1025 Java解法

题目出处思路:DFS,开一个数组arr[]存储每次满足条件的k个值,每当数组满了且数组里所有数的和等于n时就分法++,不过如果单纯这样暴力搜肯定会TLE,因此我们注意到每一次存入数组里的数必须大于等于前一个数,所以我们设置一个变量zz每次存储当前数,以后每一次从zz开始搜即可。但是我们发现这样还是会TLE,因为我们只确定了每一次存入数组大的下限,而没有规定上限,注意到总和必须为n,因此我们每次搜到的数肯定不能大于n减去前面已经搜过的数的和,这样一来就完成了基础的剪枝。代码十分易懂:package s

2020-07-31 10:22:13

洛谷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

洛谷P1141 Java解法

题目出处点这里思路①:对每一个m点进行广搜,输出搜到的结果即可思路②:很明显思路①会MLE或TLE,我们发现有可能多个m点会在同一个区域(这里的区域指前面的m点搜过的区域),如果再次搜索无疑会造成大量时间的浪费,因此我们可以标记每一次搜过的区域为已访问并用另一个二维数组temp[ ][ ]把该区域的所有点的值赋值为相应可以走到的格数即可,并在每次输入m点时判断此点是否被访问过,如果被访问过就直接输出temp里相应点的值即可,如果没有被访问过就对该点广搜即可。不过要注意读入方式和输出方式,适当的方法会节

2020-07-29 12:40:06

洛谷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

洛谷P1332 Java解法

题目出处点这里思路①:可以分别对每个领主所在地进行广搜,搜到第一个感染源时就是被感染时间,但是用java会MLE,因此行不通思路②:可以同时对每个感染源所在地进行广搜,并把每一次的每一个感染源在每一层搜到相应的地点的所需时间记录在n*m的数组里,这样得到的数组就是各个地点被感染的时间,最后输出各个领主所在地的感染时间就行了,这种方法比思路①快很多,空间也节省很多。package search;import java.awt.Point;import java.io.BufferedReader

2020-07-28 13:32:27

洛谷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

洛谷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

洛谷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

洛谷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

洛谷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

洛谷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

洛谷P1019 Java解法

题目出处点这里思路:dfs暴力搜出所有情况记录长度最大值即可找到每一个可以作为头的字符串不断与其他字符串进行拼接,然后把拼接后的字符串接着与其它字符串不断拼接,取所有情况的长度最大值。值得注意的是有可能你找到·了一个可以当头的字符串,但是它不能和任何字符串进行拼接,可是它的长度就是最大的,因此不管头字符串能不能拼接成功,我们都要判断头字符串的长度是不是最大的。代码一看就懂(超详细的注释):package search;import java.util.Arrays;import java.u

2020-07-23 17:08:22

洛谷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

洛谷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

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。