平凡的小白

未归档

题解(64)

/ 注册

全部文章 / 未归档（共6篇）

【每日一题】Rinne Loves Edges 来自专栏

戳我传送题意：这个题意是关键，首先n个点n-1条无向边边，接触过树的同学应该都知道这是一颗树，而度就是与这个点相连的边的数量，度为1就是叶子结点了，现在问题就变成了：在以S为根的树上删掉权值之和尽量小的一些边使得根和每一个叶子节点都不连通。思路：这是一个典型的树型dp，而树型dp本质上可以说是个搜索...

树状dp

2020-05-04

1 645

【牛客练习赛62】

A、牛妹的游戏题目描述：在二维空间上有若干个点，有两队（蓝方和绿方），每队都可以占边。而当有其中一队占的边有可能有三条首尾相连就输出"yes"，否则输出"no"。思路：1.拉姆塞结论--点数超过5的图或者对应补图必有度数为3的环.不会证明(只会举例子)...

规律题数学组合数学暴力枚举拉姆塞理论树状dp

2020-05-02

1 642

【每日一题】Treepath 来自专栏

戳我传送思路：方法一：因为每条边的权值都是一样，所以可以用LCA求得每个结点想对于根结点1的深度，在这里深度就是距离。从偶数层到偶数层和从奇数层到奇数层的路径都是偶数。这里可以用链式向前星存图，然后dfs统计有多少个奇数层a和偶数层b，不必要区分偶数层和奇数层，答案就是 + 。如果1e5...

树状数组 DFS LCA dp 树状dp

2020-04-16

0 599

牛客算法周周练2

前面的碎碎念菜鸡被碾压的一场比赛，就会一题。比赛传送门 A、相反数思路：签到题，直接枚举每一位， (n)能过，我写这一题的时候居然慌了。 Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);ci...

dp 打表贪心 DFS 模拟树状dp 二分

2020-04-15

1 650

【每日一题 4.13】Accumulation Degree 和树学来自专栏

Accumulation Degree 题意：不知道题目讲什么真的要命，水从根结点往下流，流量不能超过边的权值,sum[i]表示i结点最多可以流出多少水（流量），这个需要从叶子节点一直回溯来求，父结点的流量sum[u]+=min(w,sum[v]),w表示u和v边的权值，特别的当v是叶子结点的时候，...

换根树状dp

2020-04-14

1 663

【每日一题】黑白树来自专栏

黑白树思路： 1.当一个点没有被下方已经选了的点覆盖到的时候，我们选择一个它或者它下方的能向上覆盖的最远的点。2.另外，其实我们也并不关心这个点选的哪个，只需要知道往上能覆盖多远就行了，这个值其实可以直接维护到k数组里面，实际操作就是：首先处理的一定是叶子结点y，它的k值就是题目输入的值，它父亲结...

DFS 贪心树状dp

2020-04-08

0 578