dfs – Tgotp-Blog

2500: 幸福的道路

先两遍dfs处理出对于每个点能达到的最大幸福度,

然后问题转化为求序列  最长子段区间最大值与最小值差 <= m的长度

先用st表预处理出 就可以o(n)解决。

c++代码如下:

 

3391: [Usaco2004 Dec]Tree Cutting网络破坏

dfs后 o(n)判断去掉当前点后是否有超过n/2大小的联通块

c++代码如下:

 

P1461 海明码 Hamming Codes

直接爆搜,然后判断与之前存下的数的差距是否有d

c++代码如下:

 

T14967 交通

题目背景

黄金大神国的首都位于 oier 河中的一座岛屿。一道上班的时候,成千上万辆汽车通过岛屿从西

岸的住宅区(由桥连接岛的西部)到东岸的工业区(由桥连接岛的东部)。

题目描述

黄金大神国的首都位于 oier 河中的一座岛屿。一道上班的时候,成千上万辆汽车通过岛屿从西

岸的住宅区[......]

Read more

T7952 花花的森林

没开o2成功挂掉。

我们都知道,一个树删边永远比添边困难,所以说,对于这道题,我们考虑从后往前做。

先统计出最后的答案ans。这个肯定是固定的。

然后对于对于每次更新,其实更改的只是涉及的两棵不同的树(直接暴力dfs),所以说,对于每次的更新,我们直接除以两个旧数再乘以新数。[......]

Read more

P1092 虫食算

题目描述

所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子:

43#9865#045

+8468#6633

44445509678

其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两个数字分别是5[......]

Read more

[SCOI2005]王室联邦 bzoj1086 && luogu 2325

算法:树分块;

思路:首先,对于整个树dfs,当子树的大小大于 b 时,就将它们分在一块,同时令首都为当前这个点,容易想到:对于根,可能会剩下一些点,于是将这些点分在最后一个块里,容易发下,最后这一堆与那一块之和一定小于3b,正确性得证。

ok c++代码如下:
[crayon-5c1[......]

Read more

2386 Lake Counting

dfs搜索,没了。

 

Educational Codeforces Round 22 C

题面

C. The Tag Game
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

[......]

Read more