Z_L_G

题解

总结(8) 训练赛(3)

/ 注册

全部文章 / 题解（共48篇）

算法入门-Tree Decoration

题意以p(父亲),c(需要挂的最少装饰物个数),t(挂一个装饰物需要的时间)的形式输入每一个树上的节点。问满足每一个节点的装饰物需求最少需要多少时间思路对于叶子节点i，他上面至少悬挂c[i]个装饰物对于其它节点j，如果他的子节点累计挂的装饰物已经大于等于c[j]，则什么都不用做，如果...

深度优先搜索树

2025-04-14

0 11

算法入门-[SCOI2009]生日快乐

题意 x*y蛋糕，切成n块等面积的，要求最大块的(长边/短边)最小思路对于每一块，切的时候切的位置总为当前块长度或者宽度/当前块要切成的块数，这样才能保证每一块面积相等你也就是对于(x,y,n)横着切切的一定是x/n的倍数，并且若倍数为i，则一边应该且成i块，另一边应该切成n-i块于是...

深度优先搜索

2025-04-13

0 10

算法入门-[CQOI2007]矩形RECT

题意把一个a*b个小正方形组成的大正方形切成两块有多少种切法？思路爆搜，对于正方形a*b转化为点阵图坐标为[0,a][0,b] 其中(0,0)(a,0)(0,b)不能作为起点，对于每个起点，找可能的终点即可由于对称性，两条对边方案重合，所以只搜索一组邻边即可 DFS要从不在边上的点开始...

深度优先搜索

2025-04-13

0 14

算法入门-[SCOI2010]游戏

题意有n个二元组，每个二元组可以选取一个值，组成一个长为n的序列，问从1开始的最大连通能到几思路并查集，对于单一二元组，我们总希望选择其中小的对于一个连通块：一定属于下述两种情况之一 n个数的连通块，有n-1条边，则最大的元素选不到 n个数的连通块，有超过n-1条边，则所有元素...

并查集广度优先搜索思维

2025-04-12

0 11

算法入门-魔法数字

题意把数字n变为数字m，可以进行如下三种操作：+1，-1，平方，问最少需要几步思路 bfs每一步的所有可能，记录一个数最早出现的时间对于步数：最大不会超过n-m步（从n不断+1变为m），同理，如果平方后的数大于等于2m-n，说明减回m的步数一定比从n加到m还多，直接舍去 int sol...

广度优先搜索

2025-04-12

0 10

算法入门-Ocean Currents-01BFS

01BFS 走的时候有两种走法，维护双端队列，一种走法代价是0，进入队首，另一种走法代价是？，放入队尾题意给定地图，给定n次起点和终点，每次输出最短时间特别的，一个点可以向八个方向走，且向其中一个方向走不耗时，其他方向耗时为1 思路与maze那道题类似，都需要处理队列中时间最短的，...

广度优先搜索

2025-04-10

0 14

算法入门-生日蛋糕

题意给定蛋糕层数，蛋糕总体积，求解最最小表面积对于蛋糕每层的半径和高度都是整数，且对于第i层，半径和高度都不小于i 思路对于每一层，枚举可能的高度和半径，计算体积和表面积对于枚举顺序，从最底下一层往上枚举，因为上面的层数越多，受限越多对于每一层，半径和高度的下界都是层数，上界都是上一...

深度优先搜索剪枝优化

2025-04-10

0 11

算法入门-maze-优先队列广搜（恶心！

题意走迷宫，迷宫中有传送门，使用传送门需要花费三秒，求解从起点到终点的最短时间思路相较于传统搜索，出现的问题是对于一个点可能有多个到达时间，我们希望记录这多个时间中最短的时间对于传送门，由于同一个点可能有多个传送门，所以不能使用点对点的映射，使用点对数组的映射，map<int,v...

广度优先搜索搜索剪枝

2025-04-09

0 17

算法入门-小木棍-剪枝

题意给定n根短棍，将其拼成若干等长的长棍，求能拼成的长棍的最短长度是多少思路枚举长棍的长度，深搜判断能否拼成（将每一个棍尝试摆上去，如果摆上去不大于枚举长度就深搜下一层，超过的就跳过，最终判断所有棍用完的时候，最后一根长棍是否刚好拼完）优化一：对于枚举，枚举区间为最长的棍的长度到所有棍...

深度优先搜索搜索剪枝

2025-04-09

0 16

算法入门-字串变换-双向广搜

题意给定两个字符串a，b，不超过6条变换规则，,如果能在十步以内使用变换规则将a变换为b，输出步数，否则输出NO ANSWER! 思路对于最优极限情况，每一步内a可用6次变换规则，总复杂度为6^10 只要超过两种规则出现重复使用，单项搜索就会TLE 所以使用双向搜索，维护两个队列，一个从a...

双向bfs

2025-04-07

0 14