Bernard5
Bernard5
全部文章
题解
作业(2)
学习笔记(17)
技术教程(45)
期末应试(57)
未归档(17)
赛后分析(7)
题集(15)
归档
标签
去牛客网
登录
/
注册
some model useful
我亦是行人
全部文章
/ 题解
(共7篇)
2022 团体程序设计天梯赛 L2-3
来自专栏
题意 给定一棵无向树,m次标记点,标记点的同时询问从根出发访问所有点的最短路径和。走到最后一个点不用返回。 思路 逆向思维,考虑加入一个点的时候,可以走的最优方案。 对于一个新加入的点,如果可以从计划访问的点,走到这个新的点,那么是较优的选择。 考虑从新加入的点逐级回溯,如果可以到达某个计划访问的点...
dfs
2022-04-23
1
1291
红与蓝 DFS 染色
来自专栏
叶子节点之与父亲有边相连,所以叶子节点必然与父亲同色。 而父亲节点已经和叶子节点同色,所以叶子节点必然与爷爷节点异色。 爷爷的颜色确定后,如果爷爷还与一条边相连,那么标记爷爷的相邻点颜色也确定。对于任何一条路径,可以这样递归上去。 所以统计同色(友)信息然后再跑一边DFS染色即可 #include...
DFS
思维
2021-02-02
7
847
图 DFS
来自专栏
tarjan做法显然是违背出题人意图的。 本题限制了每个点只有一条出边,所以不存在复杂回路,如果成环,只存在简单环。 于是可以直接DFS,如果成环,就把整个回路都置为回路上点的数量。 #include <bits/stdc++.h> #define sc(x) scanf("%lld"...
DFS
2021-01-31
0
438
Magical Number 暴力出奇迹
来自专栏
magical number是越走越窄的,在就已经结束了。 所以直接dfs即可,只是不敢写。 最大的可行魔法数消耗木棍139,故可打表。 然而根本不需要打表,就硬搜就能过。 打表代码 #include <bits/stdc++.h> #define sc(x) scanf("%lld",...
DFS
暴力
2021-01-21
3
936
Graph Coloring I DFS
来自专栏
本题其实考察了一个基础知识: 可以将图的结点用两种颜色染色,满足相邻点不同色的图,称为二分图。而在不满足二分图构成条件的图里,一定可以找到一个简单奇环。 在明确这一点的基础上,就可以使用dfs对图结构进行染色。在dfs的过程中,用栈保存点结构的遍历信息,从而检索出现奇数环的情况。 #includ...
DFS
二分图
图论
2020-12-01
5
613
我是 A 题
来自专栏
从叶子节点开始考虑:对于每一个叶子节点,如果它本身可以被K整除,那么肯定可以直接对它和它父亲做切割。也就是说,在这种情况下,父子相连的边是一定要删掉的。 而如果不满足这一条件,这条父子相连的边最后一定会加入答案,由于需要让每一个联通块的点权之和都满足,所以如果叶子,就把叶子的点权加到父节点上即可。 ...
DFS
图论
2020-11-14
3
547
车辆调度
来自专栏
因为数据很小,我们都意识到了暴力搜索,DFS可以更简单地解决。 这题的主要难点在于编码难度,我在写这道题的时候认为每搜索一次重新开辟一个二维数组太蠢,又没想清楚如何动态管理车辆的位置信息,其实不需要管理车辆信息,每次重新搜索就可以了。 详细注释: #include <bits/stdc++.h...
DFS
2020-05-13
0
839