题解

比赛名称：牛客练习赛73   活动具体内容   11月23日22:00-12月23日18:00，写牛客练习赛73题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在12月23日下午审核，并给每篇题解发放5-60牛币    PS:    如果题解写的非常好，会增加其获得的牛币  如果题解写的非常水，会减少获得其获得的牛币  如果题解有抄袭行为，会取消其获得牛币的资格

题号 NC51266名称 Network 来源 0x66 图论-Tarjan算法与无向图连通性 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 桥的数量显然和边双连通分量有关——按边双连通分量缩点（结果是一棵树），缩点之后的边的数量就是最开始的桥的数量。每次增加一条边x->y，就会使得缩点之后的图产生一个环，这个环就和桥无关了，把他们缩掉——把xy到的lca(x,y)之间的点和lca(x,y)合并在一起就行（并查集维护）。（题解中有同学用LCT，也是个不错的解决方法，虽然代码可...

题目中给出的字符串仅包含字符'(',')','{','}','['和']',对字符串中的每一个字符进行遍历，如果是右括号的话，需要看一下栈顶元素是不是和它匹配的左括号。如果是的话，那这两个括号是一对，让栈顶元素出栈不满足配对条件的话，就让该元素进栈如果字符串是一个合法的括号序列，那么整个字符串遍历完毕以后，栈是空的，即所有的右括号都右匹配的左括号。如果栈内还右元素，就不是合法的括号序列c++代码 class Solution { public: bool isValid(string s) { stack<char> c; for(int i = 0 ; i < s.leng...

题号 NC113026名称 Tree with Small Distances 来源 CF1029E 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 贪心，如果存在一个点离根距离大于2，显然就要给他加边，这条边连到哪里呢？只有三种选择：他儿子，他父亲，他自己。我们选择连他父亲。首先考虑没有儿子的叶节点——肯定愿意连他父亲而不是他自己，他自己就只能覆盖到自己，他父亲还有能覆盖到（存在的）兄弟。然后我们可以把连了这些边之后满足条件了的点从图上去掉，再去处理剩下树中的的叶子节点。 欢迎各位...

题号 NC112786名称 Bookshelves 来源 CF981D 戳我进入往期每日一题汇总贴~往期每日一题二期题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情每日一题QQ群:659028468 题解 简单的dp。一看是位运算就应该想到按位贪心——优先让最高位是1，之后的每一位依此类推。考虑目标数第x位为1能否成立，表示前i个数分了m组之后是否能让这一位（在前面的数已经固定了的基础上）是1，显然枚举最后一次分组是从哪里分的就可以了。当前如果要判断的数位tmp的话，转移方程为：如果存在一个k使得： 且，则否则最后看是否能为1，如果是将这一位固定为1，否则这一位只能是...

比赛名称：牛客小白月赛29 活动具体内容  11月14日22:00-12月14日12:00，写 牛客小白月赛29题目的题解，即可获得牛币~  发放牛币的数量取决于题目难度，题目数量，题解质量  比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下 活动奖励：  在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~我们将在12月14日下午审核，并给每篇题解发放5-50牛币  PS:  如果题解写的非常好，会增加其获得的牛币 如果题解写的非常水，会减少获得其获得的牛币 如果题解有抄袭行为，会取消其获得牛币的资格

比赛名称：牛客挑战赛45 活动具体内容  11月13日22:00-12月13日12:00，写牛客挑战赛45题目的题解，即可获得牛币~  发放牛币的数量取决于题目难度，题目数量，题解质量  比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下 活动奖励：  在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~我们将在12月13日下午审核，并给每篇题解发放10-100牛币  PS:  如果题解写的非常好，会增加其获得的牛币 如果题解写的非常水，会减少获得其获得的牛币 如果题解有抄袭行为，会取消其获得牛币的资格

根据题目给出的条件，  一个人可以有多个下属，但一个人最多只能有一个上级。  可以得出其实是一棵树。我们要求的其实就是从根节点到每一个节点的代价，这个代价是根节点到这个节点的边权加上这个节点的点权。所以只需要进行一次dfs，dfs的过程中记录边权，然后计算每个点的代价的时候加上这个点的点权就可以了。 #include<iostream> #include<vector> using namespace std; const int MAXN = 2e5+10; int a[MAXN]; vector<pair<int,int> > G[MAXN]...

题目要求：在有序数组 中查找第一个大于等于给定值 的位置，如果不存在，输出数组的长度 加一。先考虑这样一个问题：对于一个有序数组来说，什么情况下是不存第一个大于等于 的位置呢？即：数组中的所有数都比 小，可以写成 if(a[n-1]<v) return n+1;判完这个条件以后， 数组里就一定可以存在一个位置是答案了。这样的话，我们来设答案在闭区间之间当这个区间只剩下一个数，即的时候，就是我们答案的位置了。最开始，可能的区间为整个 数组下面我们用二分的方式对这个区间进行缩减每次拿出中间的值 和 比较，那会有三种结果:大于、等于、小于1、如果说明说明后面的那段都不可能是结果了。因为a[Mi...

收到爱豆送的牛可乐真是太幸福了@是小肖肖耶

Military Problem 选点 Tree Requests Colorful Tree 求和  Propagating tree  题解 11月9日-11月13日更新以上题目题解~温馨提醒：之前的每日一题当中有三个和本专题相关的题目，同学们可以先学习。4月7日每日一题 树7月8日每日一题 Alliances8月20日每日一题 华华和月月种树 ————————————以下是介绍以前介绍过的dfs序的分割线-————————————dfs序：每个节点在dfs深度优先遍历中的进出栈的时间序列（为了方便接下来的操作我们往往有两种不同的写法，一种是只记录进栈顺序，一种是进栈出栈都记录，视题目的具...

题目汇总：https://ac.nowcoder.com/acm/contest/8891        编号   问题名称   问题模型   转化模型     A   飞行员配对方案问题   二分图最大匹配   最大流     B   太空飞行计划问题   最大权闭合图   最小割     C   最小路径覆盖问题   有向无环图最小路径覆盖   最大流     D   魔术球问题   有向无环图最小路径覆盖   最大流     E   圆桌问题   二分图多重匹配   最大流     F   最长递增子序列问题   最多不相交路径   最大流     G   试题库问题   二分图多重匹配...

比赛名称：牛客练习赛72   活动具体内容   11月6日22:00-12月6日18:00，写牛客练习赛72题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在12月6日下午审核，并给每篇题解发放5-60牛币    PS:    如果题解写的非常好，会增加其获得的牛币  如果题解写的非常水，会减少获得其获得的牛币  如果题解有抄袭行为，会取消其获得牛币的资格