题号 NC23049名称 华华给月月准备礼物来源 牛客小白月赛12戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 直接算显然不现实，我们可以考虑枚举答案验证——从大到小枚举最终的木棍长度，判断是不是所有的原来的木棍都切成这个长度之后够不够K，当枚举到第一个可以的长度的时候就可以停止了。通过这个暴力的方法我们可以发现其实可行性关于小棍的长度是“单调的”，即如果我们把答案设为ans，那么当最终的木棍长度小于等于ans就都是可行的，而当其大于ans的时候，就不可行了。有了这样的性质就可以考虑二分了（会二分的同学后面就不用看了）—...

题号 NC14731名称 逆序对来源 Wannafly挑战赛6戳我进入往期每日一题汇总贴~ 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题非常简单...任意一对都会对逆序对贡献一个1，我们可以考虑任选两个位置前一个放1后一个放0，那么剩下的位置不管怎么放，都能贡献一对逆序对，也就是说这样的方案有多少就有多少逆序对。任选两个位置的方案数是，其他n个位置随便放的方案数是，所以总逆序对数就是。注意n=1的时候需要特判。有的同学用的另外的公式可能n=3的时候也需要特判（最开始数据没这些情况，现已加强）。下面说一下快速幂（会的同学就可以跳过啦）。快速幂是快速的求a在模...

题号 NC14248名称 Treepath来源 Wannafly挑战赛1戳我进入往期每日一题汇总贴~ 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 这其实是个水题，我看到题解里有同学用树型dp的，也挺好，只要能ac都是好算法！我先说说本题最简单的做法，题面求长度为偶数的路径，显然，偶数层的点到偶数层的点长度是偶数，奇数层到奇数层的点的路径长度也是偶数，而奇数层的点到偶数层的点路径长度就算奇数了。于是我们只需要统计奇数层有多少个点，偶数层有多少个点就行了，这个写个dfs就行了。为什么层数奇偶性一样路径长度就是偶数呢？我们可以考虑先让两个点里深度深的那个往上走，走到...

比赛名称：牛客算法周周练2 赛后补题可以让自己变的更强 活动具体内容 4月14日21:30-4月20日中午12:00，写牛客算法周周练2 题目的题解，即可获得牛币~ 建议将题目分开写，在发表博客的时候类别选择题解，并输入本题地址，这样在题库刷题的小伙伴也可以看到你的题解~ 发放牛币的数量取决于题目难度，题目数量，题解质量 活动奖励： 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月20日下午审核，并给参与活动的同学发放10-80牛币 PS: ...

题号 NC14247名称 Xorto来源 Wannafly挑战赛1戳我进入往期每日一题汇总贴~注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题目描述 给定一个长度为 的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为 。 输入描述 第一行一个数 表示数组长度；第二行 个整数表示数组； ,。 输出描述 一行一个整数表示答案。 示例1 输入 30 0 0 输出 5 说明 ([1,1],[2,2]),([1,1],[3,3]),([1,1],[2,3]),([1,2],[3,3]),([2,2],[3,3]) 题解 暴力是枚举...

比赛名称：JOI 2019-Final比赛真题（重现赛） 赛后补题可以让自己变的更强 活动具体内容 4月12日18:00-4月17日中午12:00，写JOI 2019-Final比赛真题（重现赛） 题目的题解，即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量 活动奖励： 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月17日下午审核，并给参与活动的同学发放10-100牛币 PS: 如果题解写的非常好，@王清楚 将会增加其获得的牛...

题号 NC51180名称 Accumulation Degree来源 《算法竞赛进阶指南》0x54如果不会做的话可以先去学习另外一个题：201400 树学写这两道题目中的任意题目，都可以获得牛币，写两篇题解可能获得更多牛币~ 戳我进入往期每日一题汇总贴~ 感谢@Alan233 同学推荐题目如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 先看201400树学这个题 本题是要你任选一个点为根使得树上的所有点深度之和最小。 首先考虑如果是指定根节点你会不会做：已知根节点的话，我们只需要一遍dfs（或者bfs）就可以求出每个点的深度，然后求和就可以了。 然后我们考虑如果我...

比赛名称： 牛客练习赛61 出题人：米咔 戳我进入官方题解， 有问题可以回帖询问出题人~  赛后补题可以让自己变的更强 活动具体内容 4月10日22:00-4月17日12:00，写牛客练习赛61 题目的题解，即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量 小建议：比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下 活动奖励： 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月17日下午审核，并给参与活...

题号 NC13229名称 二分图染色来源 美团2017年CodeM大赛-初赛A轮 戳我进入往期每日一题汇总贴~ 注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 今天这个题看来是偏难了…… 这个题的第一个难点也是它设计得最巧妙的一个点，在于要把找个二分完全图的染色问题向二维棋盘格子上的行列覆盖转化。（如果你学过二分图匹配并做过一些相关的练习，其实你是应该能想到的——二分图匹配相关的问题往往是：棋盘格子上的行列覆盖转化成二分完全图匹配，1*2的小骨牌覆盖转化为棋盘格子黑白染色之后的二分图匹配，这个题只是反过来转换了。） 原题是左右两边各有n个点的完全二分图每条边选一...

题号 NC50940名称 Running Median来源 《算法竞赛进阶指南》0x05戳我进入往期每日一题汇总贴~ 注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐~ 点击查看详情 这算是个经（套）典（路）题了，也存在不少高端做法，比如说你想练练平衡树写法什么的都可以，这里讲解一种简单的做法——堆。 我们在之前的每日一题中给大家讲过堆这种数据结构（https://ac.nowcoder.com/discuss/390428 ），这里不再介绍。 我们可以建一个大根堆，一个小根堆，大根堆存目前数列中较小的那一半数字，小根堆存目前数列中较大的一半数字，那么中位数不是在小根堆的堆顶就是在大根堆...

比赛名称：牛客算法周周练1 赛后补题可以让自己变的更强 活动具体内容 4月7日21:30-4月13日中午12:00，写牛客算法周周练1 题目的题解，即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量 活动奖励： 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月13日下午审核，并给参与活动的同学发放10-80牛币 PS: 如果题解写的非常好，@王清楚 将会增加其获得的牛币 如果题解写的非常水，@王清楚 会减少获得其...

题号 NC13249名称 黑白树来源 美团2017年CodeM大赛-初赛B轮戳我进入往期每日一题汇总贴~注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐~ 点击查看详情 看到树想一边搜一边处理大概率都是可以的（也有例外，比如昨天那个题就根本和这棵树的样子没什么关系。）首先，我们可以很容易的知道：由于每个点都是向上覆盖的，所以凡是不能被下面的点覆盖上的点都必须要选，而能被子孙节点覆盖的点就一定不选了吗？不一定，反例如图1叶子节点6一定得选，这个时候5和4都在他的覆盖范围内，如果都不选，3没被覆盖，要选，2要选1要选，一共选了4个点，但是事实上我们选6和5就行了。 （知道了这个贪心策略不对之后...

题号 NC13611名称 树来源 牛客练习赛1戳我进入往期每日一题汇总贴~ 这个题表面上看起来像是个树上dp，但是你会发现，当xy同色的时候要求x到y的路径上所有点颜色一样这个事情非常难办——如果我们考虑颜色一个一个的涂，同色这个条件父亲节点有三个子树为例，可能其中两个子树和这个父亲节点是同样的颜色，而另外一个子树是另一个颜色，这就非常难办了。 我们考虑把树上的东西转化到线性结构上——这样的操作当然是使用dfs序啦。 ----------------------以下是介绍dfs序的分割线----------------------- dfs序：每个节点在dfs深度优先遍历中的进出栈的时间...

比赛名称：牛客OI周赛15-提高组 出题人：wxyww 戳我进入官方题解~ 有问题可以回帖询问出题人 赛后补题可以让自己变的更强 活动具体内容 4月4日21:30-4月11日中午12:00，写牛客OI周赛15-提高组 题目的题解，即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量 活动奖励： 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月10日下午审核，并给参与活动的同学发放10-100牛币 PS: 如果题解写的非常...