Z_L_G

题解

总结(19) 训练赛(13)

/ 注册

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

算法入门-可爱の星空

题意多组数据每组数据给出一个图中点的个数n，链接任意一条边需要的代价是这个边所连的两个联通块的大小的差值，使这n个点联通所需的最小代价是多少思路贪心的思考，想让价值最小，每一步合并的两个块得大小接近最终都会合成一个联通图，逆序思考深搜即可代码 #include<bit...

深度优先搜索

2025-06-27

0 17

算法入门-花店橱窗

题意花店有f朵花，v个盆，每个花放每个盆有不同的美观度，求如何摆放能使美观度最大特别的，给花编上号，花必须按照顺序摆放，编号小的的花不能放在编号大的花的后面思路由于必须按照顺序摆放，所以新的一盆花可放的盆一定是上一盆花放的盆的后面初始化:对于最开始，每朵花放在自己编号的盆里，其它...

dp

2025-06-27

0 21

算法入门-免费馅饼

题意在一个W*H的长方形平面内，有若干块饼下坠，每块饼会有{下坠时间，下坠位置，下坠速度，价值}四个信息人最初站在中间，可以移动(-2,-1,0,1,2)，请输出最多获得的价值以及开始后每一秒的操作思路这题有很多坑点显然是一个动态规划，状态转移方程坑点1:由于起点强制锁定在中间，但...

dp

2025-06-27

0 22

算法入门-舔狗舔到最后一无所有

题意每天可以从三家店中选一家，不能连续三天选同一家，t次询问，每次询问连续选n天有多少种不同的选择方案思路简单动态规划，显然第i天的可选择方案数取决于第i-1和第i-2天对于任意一个店，第i天可以选它的情况是第i-1天选另外两家，不用考虑第i-2天第i-1天选它，第i-2天只能...

dp

2025-06-24

0 29

算法入门-方块与收纳盒

题意走楼梯，斐波那契换了个描述思路水题，代码 #include<bits/stdc++.h> using namespace std; /** * dp[i]=dp[i-1]+dp[i-2] */ vector<long long> dp(100); in...

dp

2025-06-23

0 30

算法入门-第k大数

题意给定若干组数组，每组数组给出长度n和询问k 输出第k大的数思路水题，直接硬模拟+排序即可注意输入量很大，需要使用快读 inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch &l...

模拟‘ 排序快读快写

2025-06-23

0 28

算法入门-NOIP2009分数线划定

题意 n个人参加考试录取m个人，分数线划在m*150%的地方输出有多少人录取，录取分数线，录取的人思路水题，直接硬模拟+排序即可注意如果从0开始存储m乘完要减一名代码 #include<bits/stdc++.h> using namespace std; #defi...

模拟

2025-06-23

0 43

算法入门-树上子链

题意一颗有n个结点的树，每个结点具有权值，求解最长（权值最大）的一条子链思路对于某一个结点来思考，他能构成的最长子链无非下列集中情况之一包含他的最长链+最长的包含他一个儿子的最长链所有结点均为负值，最长子链自身的权值他自己的一条最长链（另一条全负）因此我们维护一个dp数组，...

树形dp dp 深度优先搜索

2025-05-19

0 49

算法入门-二叉苹果树(边权转点权)(补：两种做法)

题意对于一个有n个结点的二叉树，根的编号一定为1，每条边有权值求保留q条边时，最多能获得多少权值 tip:分析样例可以知道，这棵树的根是必须保留的，“剪枝行为”一定是保留根含有根的子树思路（法一）由于输入是无规律的输入每一条边，所以应当先建立起二叉树，从根开始深搜建树由于边权是较难处...

dp 树形dp 深度优先搜索

2025-05-16

0 45

算法入门-(USACO 2008 Jan G)Cell Phone Network(最小支配集)

最小支配集选择一个点，可以覆盖相邻的点，覆盖所有点所需最小选点题意给定一颗n个结点的树，求最小支配集思路考虑每一个点，他可能被支配的方式有：被父亲支配，选自己，被儿子支配，维护一个二维dp数组记录点和状态：自己：父亲：儿子：对于自己和父亲，状态方程很显然可以推出，对于...

dp 树形dp 深度优先搜索最小支配集

2025-05-16

0 39