Z_L_G
Z_L_G
全部文章
题解
总结(9)
训练赛(6)
归档
标签
去牛客网
登录
/
注册
又活一天?
你怎么可能做和别人相同的事情又同时超过别人呢?
全部文章
/ 题解
(共72篇)
算法入门-舔狗舔到最后一无所有
题意 每天可以从三家店中选一家,不能连续三天选同一家,t次询问,每次询问连续选n天有多少种不同的选择方案 思路 简单动态规划,显然第i天的可选择方案数取决于第i-1和第i-2天 对于任意一个店,第i天可以选它的情况是 第i-1天选另外两家,不用考虑第i-2天 第i-1天选它,第i-2天只能...
dp
2025-06-24
0
13
算法入门-方块与收纳盒
题意 走楼梯,斐波那契换了个描述 思路 水题, 代码 #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
8
算法入门-第k大数
题意 给定若干组数组,每组数组给出长度n和询问k 输出第k大的数 思路 水题,直接硬模拟+排序即可 注意输入量很大,需要使用快读 inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch &l...
模拟‘
排序
快读快写
2025-06-23
0
14
算法入门-NOIP2009分数线划定
题意 n个人参加考试录取m个人,分数线划在m*150%的地方 输出有多少人录取,录取分数线,录取的人 思路 水题,直接硬模拟+排序即可 注意如果从0开始存储m乘完要减一名 代码 #include<bits/stdc++.h> using namespace std; #defi...
模拟
2025-06-23
0
12
算法入门-树上子链
题意 一颗有n个结点的树,每个结点具有权值,求解最长(权值最大)的一条子链 思路 对于某一个结点来思考,他能构成的最长子链无非下列集中情况之一 包含他的最长链+最长的包含他一个儿子的最长链 所有结点均为负值,最长子链自身的权值 他自己的一条最长链(另一条全负) 因此我们维护一个dp数组,...
树形dp
dp
深度优先搜索
2025-05-19
0
32
算法入门-二叉苹果树(边权转点权)(补:两种做法)
题意 对于一个有n个结点的二叉树,根的编号一定为1,每条边有权值 求保留q条边时,最多能获得多少权值 tip:分析样例可以知道,这棵树的根是必须保留的,“剪枝行为”一定是保留根含有根的子树 思路(法一) 由于输入是无规律的输入每一条边,所以应当先建立起二叉树,从根开始深搜建树 由于边权是较难处...
dp
树形dp
深度优先搜索
2025-05-16
0
33
算法入门-(USACO 2008 Jan G)Cell Phone Network(最小支配集)
最小支配集 选择一个点,可以覆盖相邻的点,覆盖所有点所需最小选点 题意 给定一颗n个结点的树,求最小支配集 思路 考虑每一个点,他可能被支配的方式有:被父亲支配,选自己,被儿子支配,维护一个二维dp数组记录点和状态: 自己: 父亲: 儿子: 对于自己和父亲,状态方程很显然可以推出,对于...
dp
树形dp
深度优先搜索
最小支配集
2025-05-16
0
30
算法入门-Strategic game(最小点覆盖)
最小点覆盖 选择一个点,覆盖所有相邻边,最少选几个点能覆盖所有边 题意 给定一棵n个结点的树,选定一个结点后即可覆盖他的所有邻边,求覆盖所有邻边的最少选定结点数 思路 动态规划 对于每一个结点,由于覆盖边,所以自己考虑选和不选两种情况,且父亲没选,自己就一定得选,父亲选了,自己就可选可不选...
dp
树形dp
深度优先搜索
最小点覆盖
2025-05-15
0
25
算法入门-小G有一个大树
题意 对于一棵树,我们希望找到一个点,使得删除这个点之后,最大子树的结点数最小 以边的形式输入,输出被删除的点的编号和删除后最大子树的结点数 思路 考虑用无根树描述,对于树的某一个结点,删掉后,整棵树变为两部分 这个结点的父亲所属的树 这个结点的若干子树 故另表示删除这个点后最大子树结点...
dp
树形dp
深度优先搜索
2025-05-14
0
28
算法入门-没有上司的舞会
题意 给定一颗n个结点的树,结点编号1~n,每个结点有权值,一个点选择以后,它的父亲就不可以被选,输出能选出的最大权值 思路 对于每个点,都有选和不选两种情况,当一个点选的时候,所有的儿子都不能选,当一个点不选的时候,每个儿子取选和不选的最大值即可,维护一个二维dp数组,状态转移方程如下 注...
dp
树形dp
深度优先搜索
2025-05-14
0
32
首页
上一页
1
2
3
4
5
6
7
8
下一页
末页