Z_L_G

分类

总结(19) 训练赛(12) 题解(103)

/ 注册

全部文章（共132篇）

算法入门-01背包

题意给定n个物品，每个物品由价值和体积，问装入体积为v的背包的最大价值和恰好装满的最大价值思路 01背包问题，对于每个物品考虑装和不装即可，如果不装\装不下，如果装则考虑装进来后的价值，对于每一个物品，在装和不装里取最大即可。注意到，n和val最大都可以取1000，二维数...

dp 01背包

2025-05-01

0 54

算法入门-最长公共子序列

题意给定两个字符串a,b,求a，b最长公共子串思路动态规划，最长的子串一定是由倒数第二长的子串加上两个串中一组相同的字符得来的即：（相同时）（不同） AC代码 #include<bits/stdc++.h> using namespace std; int f[5050][...

dp

2025-04-30

0 47

算法入门-[NOIP2001]装箱问题

题意 n个物品，箱子体积为v，装入物品后，箱子的最小剩余体积是多少思路动态规划对于每一个物品，考虑放或者不不放，观察体积即维护放入前i个物品能否满足体积为j (当前物品已经比需要的体积大了，放不进去) (当前物品可以放的进去，考虑放/不放) 特别的，本题有三种写法...

dp

2025-04-30

0 48

算法入门-传球游戏

题意 n个人围成环，传球m次，传回第一个人的方案数有多少种？思路结束状态为最后一步传回第一个人，上一步为m-1步传回1号左右的两个人维护即可 AC代码 #include<bits/stdc++.h> using namespace std; int n,m; int dp...

dp

2025-04-26

0 47

算法入门-滑雪

题意在n*m的地图中，每个点有权值，并且在任一点都可以向四周比自己权值小的点走动，求最多走动多少步思路对于走动最长路径的最后一个点，他一定是由上下左右中比他小且已走路径最长的点走来，对于倒数第二个点同理，故需要维护每个点可以走的最长路径，记dp[i][j]为从(i,j)开始走的最长路径，...

dp 记忆化搜索

2025-04-26

0 45

算法入门-Tree Decoration

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

深度优先搜索树

2025-04-14

0 38

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

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

深度优先搜索

2025-04-13

0 34

算法入门-[CQOI2007]矩形RECT

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

深度优先搜索

2025-04-13

0 38

算法入门-[SCOI2010]游戏

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

并查集广度优先搜索思维

2025-04-12

0 33

算法入门-魔法数字

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

广度优先搜索

2025-04-12

0 32